Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
These are very standard questions from a theory of computation course. If you are taking such a course, they will probably be answered soon. – David 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 , 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.

share|cite|improve this answer

Your Answer


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.