Fix an effective numbering of the partial computable functions with a universal partial computable function and the parameter compilation supplied by the S-m-n theorem. For every total computable function , there is a program index such thatHere means equality as partial functions, including the inputs on which computation diverges. The conclusion concerns a program's behavior, not equality of program indices: has no numerical fixed point, but still has this semantic fixed point.[ref]
Introduction to the Theory of Computation by Jean Gallier (2017). Section10.5, Theorem10.22, printed pp.276–277
For a proof, the S-m-n theorem gives a total computable function compiling into a program that, on input , first computes and then runs the program with that resulting index on . Thuswhere both sides diverge if the inner computation does. Choose an index for the total computable function . Setting givesThe theorem makes rigorous a program's ability to use a description of itself. For example, let compile a program that ignores its input and prints . Its semantic fixed point is a program that prints its own index. This does not require a program to read its source file.
Articles by others on the same topic
Kleene's recursion theorem, named after mathematician Stephen Cole Kleene, is a fundamental result in the field of computability theory. It addresses the existence of computable functions that can be defined recursively. The theorem states that for any total computable function \( f \), there exists a program (or particular index in the sense of the arithmetical hierarchy) that produces itself as an output when given its own index (or code) as input.