Universal URM Computable Functions
Theorem
For each integer $k \ge 1$, there exists a URM computable function:
- $\Phi_k: \N^{k+1} \to \N$
such that for each URM computable function $f: \N^k \to \N$ there exists a natural number $e$ such that:
- $\forall \left({n_1, n_2, \ldots, n_k}\right) \in \N^k: f \left({n_1, n_2, \ldots, n_k}\right) \approx \Phi_k \left({e, n_1, n_2, \ldots, n_k}\right)$.
This function $\Phi_k$ is universal for URM computable functions of $k$ variables.
Proof
Let $\Phi_k: \N^{k+1} \to \N$ be given by:
- $\Phi_k \left({e, n_1, n_2, \ldots, n_k}\right) = U \left({\mu z \ T_k \left({e, n_1, n_2, \ldots, n_k, z}\right)}\right)$
where $T_k$ and $U$ are as in Kleene's Normal Form Theorem.
Thus we have reinterpreted Kleene's Normal Form Theorem as being about URM computable functions.
This is legitimate, as a URM Computable Function is Recursive and vice versa.
$\blacksquare$
Comment
Thus we can obtain all URM computable functions of $k$ variables by letting the value of the first variable of $\Phi_k$ to range through all the natural numbers.
So we can think of a corresponding URM program $P$ which computes $\Phi_k$ as being a universal machine which computes all URM computable functions of $k$ variables.
So we now have a recipe for constructing a suitable URM program $P$ for this universal machine.
This recipe will be fairly complicated.