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

118 Views Asked by At

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.

1

There are 1 best solutions below

1
On BEST ANSWER

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