I am now a lecturer at Victoria University of Wellington. My homepage has moved there.

Recent Posts
Archives
Categories
Meta
I am now a lecturer at Victoria University of Wellington. My homepage has moved there.
The standard proof of the recursion theorem is slick but unintuitive. This is my attempt to give a proof that is easier to understand.
Theorem (Kleene)
If is a recursive function, then there exists an such that the Turing machine indexed by is equivalent to the Turing machine indexed by i.e. .
Proof
Fix a recursive function . Our plan is to build a computable sequence of Turing machines so that each machine in this sequence attempts to do two things. First the machine ‘tries’ to determine its own index by running a computation. Secondly if the machine obtains an answer to this computation, then the machine emulates the machine numbered . Note that if machine correctly determines its own index, then and so .
How should the machine attempt to guess its own index? Well assuming that the function defined by is recursive, there is some such that and so obviously . This indicates that machine should guess that its index is . Hence let be a Turing machine that first computes , then, if this computation terminates, emulates the machine indexed by . The function defined by is recursive because can be computed from the quadruples of a universal machine, an index for in this machine, and the quadruples that write a sequence of ‘s of length onto the tape.
Let be an index for . Let . Machine is the machine that computes then emulates . But is an index for and . Hence emulates and we are done.
Or simply define to be a recursive function such that . Let be an index for then .
To show that there is a computable fixed point, observe that an index for the function is computable in an index for the function .