The Recursion Theorem

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 {f: \omega \rightarrow \omega} is a recursive function, then there exists an x \in \omega such that the Turing machine indexed by x is equivalent to the Turing machine indexed by f(x) i.e. \{x\} \simeq \{f(x)\}.

Proof
Fix a recursive function f. Our plan is to build a computable sequence of Turing machines \{\varphi_{e_i}\}_{i \in \omega} so that each machine in this sequence attempts to do two things. First the machine ‘tries’ to determine its own index e_i by running a computation. Secondly if the machine obtains an answer x to this computation, then the machine emulates the machine numbered f(x). Note that if machine e_i correctly determines its own index, then x=e_i and so \{e_i\} \simeq \{f(e_i)\}.

How should the machine e_i attempt to guess its own index? Well assuming that the function g defined by g(i) =e_i is recursive, there is some a such that \{a\} \simeq g and so obviously \{a\}(a) =g(a) = e_a. This indicates that machine \varphi_{e_i} should guess that its index is \{i\}(i). Hence let \varphi_{e_i} be a Turing machine that first computes \{i\}(i), then, if this computation terminates, emulates the machine indexed by f(\{i\}(i)). The function g defined by g(i) =e_i is recursive because e_i can be computed from the quadruples of a universal machine, an index for f in this machine, and the quadruples that write a sequence of 1‘s of length i onto the tape.

Let a be an index for g. Let e_a = g(a). Machine e_a is the machine that computes \{a\}(a) then emulates f(\{a\}(a)). But a is an index for g and g(a)\downarrow=e_a. Hence e_a emulates f(e_a) and we are done.

Or simply define g to be a recursive function such that \{g(i)\} \simeq \{f(\{i\}(i))\}. Let a be an index for g then \{g(a)\} \simeq \{f(\{a\}(a))\} = \{f(g(a))\}.

To show that there is a computable fixed point, observe that an index for the function g is computable in an index for the function f.

Advertisements
This entry was posted in Posts. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s