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.

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|improve this question
    
Do you copy & paste all your tasks here and just wait until they are solved by someone? Maybe you should add some own thoughts and add a homework tag. –  Listing May 7 '11 at 20:06
1  
Are you the same user as temo (user 8875)? If so, I can merge your accounts. –  Qiaochu Yuan May 8 '11 at 3:38
    
@Qiaochu Yuan: No, although I have the suspicion, that we live in the same student house. –  user10324 May 8 '11 at 16:38
    
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

1 Answer 1

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.

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.