Prove that there exists an index for a specific computable function

Question

How can I prove that there exists an index $x$ s.t. the $x$-th computable function(0) $= x^2$

Thank you

Answer 1

If you want your listing to be computable, there is no computable listing of computable functions. So I assume you mean "x-th $\textit{partial}$ computable function".

Let $\Phi_n$ denote the $n^\text{th}$ partial computable function. Define the partial computable function

$$\Psi(n,m) = \begin{cases} n^2 & \quad m = 0 \\ 1 & \quad \text{ otherwise} \end{cases}$$

By the s-m-n theorem, there exists a computable function $f$ such that

$$\Psi(n,m) = \Phi_{f(n)}(m)$$

By the recursion theorem, there exists an $e$ such that $\Phi_{f(e)} = \Phi_e$. Hence

$$\Phi_e(0) = \Phi_{f(e)}(0) = \Psi(e,0) = e^2$$

This $e$ is your desired index.