Recursive function with code $n$, whose output is the number $n$ itself

Question

There is a recursive function with code $n$, whose output is the number $n$ itself. That is $\phi_n$ is the constant function with value $n$.

I've been toying with the idea of using s-m-n theorem applied to a particular function and then applying the recursion theorem to get the constant function/value. I cannot go any further. How should I prove the above statement? There's another question with four answers but they don't answer my question.

You're on the right track. As a hint, think of the function $f(x,y) = x$. Try applying the $s_{mn}$ theorem to this. — tci, May 17 '13 at 14:16
In general, when you want to build a program with some kind of self reference, you should try the recursion theorem. — Quinn Culver, May 18 '13 at 18:00

score 3 · Accepted Answer · answered May 17 '13 at 18:36

This is not entirely just s-m-n theorem. You need to use the Recursion theorem, which is a fairly easy consequence of the s-m-n theorem.

Define the partial computable function

$\Psi(x,y) = x$

Since it is partial computable, there exists an $e$ such that

$\Psi(x,y) = \Phi_e(x,y)$

By applying the s-m-n theorem (just like I described in one of your earlier questions, i.e. letting $f(x) = s(e,x)$, where $s$ is the function coming from the s-m-n theorem), there exists a computable function $f$ such that

$\Psi(x,y) = \Phi_e(x,y) = \Phi_{f(x)}(y)$

By the recursion theorem, there exists a $n$ such that

$\Phi_{f(n)} = \Phi_n$

Hence on all input $y$,

$\Phi_n(y) = \Phi_{f(n)}(y) = \Phi_e(n,y) = \Psi(n,y) = n$

So $\Phi_n$ is a program with code $n$ which is also constant function taking input $n$.

A "fairly easy consequence"?!?! Maybe for you... – Quinn Culver May 18 '13 at 17:57 — Quinn Culver, May 18 '13 at 17:57

Recursive function with code $n$, whose output is the number $n$ itself

1 Answers1