Two versions of Kleene's recursion theorem - what's the relationship between them?

220 Views Asked by At

Below are two versions of Kleene's recursion theorem. How are they related? Are they equivalent? If not, does one of them (which one?) imply the other?

Note that both $U(n,x)$ and $\phi_n(x)$ is the result of application of program number $n$ to input $x$.

Version 1:

If $H:N\to N$ is a total computable function and $U$ is a Godel universal computable function (defined here), then there is $n$ such that $U(n,x)=U(H(n),x)$ for all $x$ (i.e., there's a "program" that does the same thing before and after the application of $H$).

(The construction of the fixed point is given here.)

Version 2:

For every number $p$, there exists $q_0$ such that for all $x$, $$\phi_p(q_0,x)=\phi_{q_0}(x)$$

1

There are 1 best solutions below

3
On

The question of whether they're equivalent is a little imprecise since they're both true (whether one follows immediately from the other might depend on how the formalisms are developed), but I think both versions say essentially the same thing.

In version 2, we think of $p$ as encoding an interpreter that takes a program representation $q$ and runs it on input $x$ (using its own internal interpretation of $q$ as a program). The theorem states that for any such interpreter, there's a number $q_0$ that represents the same program in $p$'s "language" as it does in our "canonical language" of program numberings.

In version 1, given a Godel universal computable function $U$ (which we think of as a universal interpreter in the sense that for any interpreter $V$, we can computably translate programs from $V$'s language to $U$'s language), we can think of $H$ as the translation function for some arbitrary interpreter $V$. The theorem says that there's a number $n$ that represents the same program in $V$'s language that it does in the "universal" language of $U$.