How can I show, that for every recursive function $f: \mathbb{N} \rightarrow \mathbb{N}$ we have a number (source code) $c$ such that $\forall x \in \mathbb{N}: f_U (c,x)=f_U (f(c),x)$, where $f_U: \mathbb{N}^2 \rightarrow \mathbb{N}$ is a partial recursive function that is universal in the sense that for every other partial recursive encoded by the number $c$ $f_U (c,x)$ is the output of that function, when $x$ is given as input to that function ?

Going further: If I have the above, how can I show that there is a constant function that has output $c \in \mathbb{N}$ and additionally the property that its codification is also $c$ ?

  • 1
    $\begingroup$ These are very standard questions from a theory of computation course. If you are taking such a course, they will probably be answered soon. $\endgroup$ – David E Speyer May 10 '11 at 12:02

Both of these questions can be solved using the recursion theorem; there is an article on this on Wikipedia at http://en.wikipedia.org/wiki/Kleene%27s_recursion_theorem , and it is covered in most textbooks. There are some difficult applications of the recursion theorem, but these are quite direct once you have the statement of the theorem, which is not particularly different than the first question you asked.

| cite | improve this answer | |

Your Answer

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