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