Kleene's recursion theorem: Difference between revisions

Revision as of 10:54, 18 December 2023

Revision as of 10:55, 18 December 2023

Line 42:

Let <math>f: \mathbb{N} \rightarrow \mathbb{N}</math> be a total computable function. Then, there exists a program <math>e_0 \in \mathbb{N} </math> such that <math>\phi_{e_0} = \phi_{(f_(e_0))}</math>.

This essentially means that if we take a program, we apply an [[Effectiveness|effective]] transformation in an extensional way [(say, replace instructions such as successor, jump, remove lines]), there will always be a program which is not changed by the transformation of the function, even before andor after it.

This theorem can therefore be interpreted in the following manner “given any effective procedure to transform programs, there is always a program such that, when modified by the procedure, it does exactly what it did before, or it's impossible to write a program that changes the extensional behaviour of all other programs”.