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.