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...

$\endgroup$
  • 2
    $\begingroup$ for those interested, this may provide some context: en.wikipedia.org/wiki/Quine_(computing) $\endgroup$ – Eugene Bulkin May 15 '11 at 20:40
  • 3
    $\begingroup$ temo, 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. $\endgroup$ – tci May 15 '11 at 20:40
5
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you give me a hint, why this $f$ has to be recursive ? (if I'm not already asking too much) $\endgroup$ – temo May 16 '11 at 6:49
  • 1
    $\begingroup$ 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. $\endgroup$ – Carl Mummert May 16 '11 at 11:18
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.