0
$\begingroup$

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
    These are very standard questions from a theory of computation course. If you are taking such a course, they will probably be answered soon.2011-05-10

1 Answers 1