Universal URM Programs

Theorem

For each integer $k \ge 1$, there exists a URM program $P_k$ such that:

For each URM program $P$ there exists a natural number $e$ such that:

For all $\left({n_1, n_2, \ldots, n_k}\right) \in \N^k$, the computation using the program $P_k$ with input $\left({e, n_1, n_2, \ldots, n_k}\right)$

has the same output as the computation using the program $P$ with input $\left({n_1, n_2, \ldots, n_k}\right)$.

This function $P_k$ is a universal program for URM computations with $k$ inputs.

Proof

This follows directly from:

• Kleene's Normal Form Theorem‎;
• Universal URM Computable Functions‎.

$\blacksquare$