Kleene's recursion theorem

The Rekursionssatz or fixed-point theorem of Kleene is a set of theoretical computer science, more precisely computability theory.

It deals with the algorithmic modification of program source code. In block a program f comes before that, when you give him the source code of another program, this modifies according to a fixed scheme or algorithm.

The Rekursionssatz now states that you can outsmart each modification program: At a given modification program you can always find a source text, which do not mind the modification. That is, the source code is changed, but it has for the function of this program, which is represented by this code, no effect. One can imagine, for example, that the modification is made only in a part of the program that is not executed at all. Since, therefore, does not change the semantics of the program, one also speaks of a fixed-point semantics of the syntactic program transformation.

Formal version

For all total computable functions exist, so that, with the -th program with respect to any Gödel numbering. is thus a fixed point of the semantic Modifikatorfunktion.

Here is the modified program and as it were the source code of the program is modified.

Alternative formulation and proof

For computable functions that represent descriptions of Turing machines on descriptions of Turing machines, there is a Turing machine so.

Evidence

Define a computable function that maps again descriptions of Turing machines on descriptions of Turing machines such that, if a correct description of a Turing machine. Otherwise let. It is the Turing machine, which performs the sequential execution of the two computable functions and. The desired fixed point of is now, because.

Others

There is not only a fixed point for each function, but there are always infinitely many fixed points. There is even a function that these fixed points are calculated ( effective variant of the fixed-point theorem ).

Applications

The Rekursionssatz is often used as a lemma in evidence if you want to show the existence of a certain computable function (for example, Quine, a program that prints its own source). Therefore one is the Modifikatorfunktion so that the unknown function is a fixed point. In the case of Quine's the Modifikatorfunktion would be eg the function that returns a program that prints just input source code ( pseudo code):

F ( x ): return "return" x The fixed point is then a Quine.