Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
for those interested, this may provide some context: en.wikipedia.org/wiki/Quine_(computing) –  Eugene Bulkin May 15 '11 at 20:40
2  
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. –  tci May 15 '11 at 20:40

3 Answers 3

up vote 5 down vote accepted

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

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

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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