Theorem of recursion of Kleene

For an enumeration of recursive function

If $\ varphi$ is a acceptable Enumération recursive functions and $f$ a recursive partial Fonction then there exists a Indice ${\ mathbf {E}}$ such as

$\ varphi_ {\ mathbf {E}} (X) =f (\ mathbf {E}, X)$ .

For a computer programming language

If $\ varphi$ is a acceptable Computer programming language and $f$ a semi-calculable Fonction then it ${\ mathbf {E}}$ such as for all $x$ exists a program

$\ varphi_ {\ mathbf {E}} (X) =f (\ mathbf {E}, X)$ .

Another forms

This theorem can be declined in various forms of which one of most famous is due to H. Rogers. One considers a acceptable Computer programming language $\ varphi$ .

Form of Rogers

If $f$ is a calculable Fonction then it ${\ mathbf {E}}$ such as for all $x$ exists a program $\ varphi_ {\ mathbf {E}} (X) = \ varphi_ {F (\ mathbf {E})}(X)$ .

Paramétrisée

There exists a calculable Fonction $n$ such as for all $x$ and $y$ . $\ varphi_ {N (Z)}(X) = \ varphi_ {\ varphi_ {Z} (N (Z))}(X)$ .

Récursion doubles

If $f$ and $g$ are calculable functions then it exists two programs ${\ mathbf {e_1}}$ and ${\ mathbf {e_2}}$ such as for all $x$

$\ varphi_ {\ mathbf {e_1}} (X) = \ varphi_ {F (\ mathbf {e_1}, \ mathbf {e_2})}(X)$

$\ varphi_ {\ mathbf {e_2}} (X) = \ varphi_ {G (\ mathbf {e_1}, \ mathbf {e_2})}(X)$ .

One owes the double theorem of recursion to R. Smullyan.

Notice

The demonstration of this theorem uses the Auto-référence $s (X, X)$ produced by the Théorème of iteration (theorem s-m-n). This concept of autoreference is very deep and was largely treated by John von Neumann within the framework of the cellular automats car-reproducers.

Applications

This theorem is recognized like the best tool making it possible to produce pathological counterexamples and cases. In particular, it provides the existence of programs calculating their own codes. By taking $f$ the first projection, $f (there, X) =y$ and by applying the theorem one obtains a program ${\ mathbf {E}}$ such as for all $x$

$\ varphi_ {\ mathbf {E}} (X) = \ mathbf {E}$ .

The execution of the program $\ mathbf {E}$ produces its own code. Such programs are commonly called quine S.

Random links: