(i) Explain briefly what is meant by the terms register machine and computable function.

Let $u$ be the universal computable function $u(m, n)=f_{m}(n)$ and $s$ a total computable function with $f_{s(m, n)}(k)=f_{m}(n, k)$. Here $f_{m}(n)$ and $f_{m}(n, k)$ are the unary and binary functions computed by the $m$-th register machine program $P_{m}$. Suppose $h: \mathbb{N} \rightarrow \mathbb{N}$ is a total computable function. By considering the function

$$g(m, n)=u(h(s(m, m)), n)$$

show that there is a number $a$ such that $f_{a}=f_{h(a)}$.

(ii) Let $P$ be the set of all partial functions $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$. Consider the mapping $\Phi: P \rightarrow P$ defined by

$$\Phi(g)(m, n)= \begin{cases}n+1 & \text { if } m=0, \\ g(m-1,1) & \text { if } m>0, n=0 \text { and } g(m-1,1) \text { defined } \\ g(m-1, g(m, n-1)) & \text { if } m n>0 \text { and } g(m-1, g(m, n-1)) \text { defined }, \\ \text { undefined } & \text { otherwise. }\end{cases}$$

(a) Show that any fixed point of $\Phi$ is a total function $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$. Deduce that $\Phi$ has a unique fixed point.

[The Bourbaki- Witt Theorem may be assumed if stated precisely.]

(b) It follows from standard closure properties of the computable functions that there is a computable function $\psi$ such that

$$\psi(p, m, n)=\Phi\left(f_{p}\right)(m, n) .$$

Assuming this, show that there is a total computable function $h$ such that

$$\Phi\left(f_{p}\right)=f_{h(p)} \text { for all } p .$$

Deduce that the fixed point of $\Phi$ is computable.