5
$\begingroup$

This problem is probably a rather trivial one, since I have the impression, that it is a textbook-style one, but nonetheless somehow it won't give in. Here it is:

I have to show that there exists a (unary) recursive function, that has code $c$ and also takes the constant value $c$ (i.e., it outputs its own code).

I am pretty sure, I have to use Kleene's (second) recursion theorem, that says that for a given (total) recursive function $f:\mathbb{N} \rightarrow \mathbb{N}$ there is a number/code $c$ such that $\phi_c=\phi_{f(c)}$ (where $\phi_a$ is the partial recursive function that has code $a$), but I can't figure out how...

  • 3
    $t$emo, why don't you try writing a program (in any language, or even in pseudocode) that does this? After that, it's just a matter of translating back to this terminology.2011-05-15

3 Answers 3

5

Just let $f(x)$ be a function that, on input $x$, creates and returns a program $P_x$ such that $P_x$ ignores its input and returns the number $x$.

  • 1
    Since you already know $x$, you can just hard-code it into a program. In C, the program would just say, for example, "return 5;". All that $f$ does is return a program of this sort.2011-05-16
1

You want $\phi_c$ to be "the function which outputs $c$". Hence, you want $\phi_{f(c)}$ also to be a function that outputs $c$. The difference is that you can control $\phi_{f(c)}$ since you control $f(x)$.

So you want to define $f(x)$ to be the code of the constant function $x$ (i.e. returns $x$ for every input). Now Kleene's theorem gives you the following: There exists $c$ such that the function coded by $c$ is exactly the constant function $c$.

0

Let $T_i$ be a Turing Machine with Godel number $i$ and $\phi_i$ the function computed by $T_i$.

We wish to show there exists a number $n_0$ such that $T_{n_0}$ prints its own coding $n_0$. Let $\phi_0, \phi_1, ...$ be any enumeration (Godel numbering) of all computable functions and let $h$ be any totally computable function. Then, by the fixed point theorem (as you have suspected) there exists a number $i_0$ such that $\phi_{i_0} = \phi_{h(i_0)}$, i.e. $i_0$ is a fixed point for $h$.

Let us now define the function $h$ to be the function such that for each natural number $n$, we have that $h(n)$ is equal to a machine that prints $n$ and halts, i.e., such that $\phi_{h(n)} = n$. Let $n_0$ be a fixed point for $h$. Then $\phi_{n_0} = \phi_{h(n_0)} = n_0$.