recursive function is URM-computable

Proposition 1.

Every recursive function is URM-computable function.

The proof can be broken down in several simple steps.

Proposition 2.

The zero function, the successor function, and the projection functions are URM-computable.

Proof.

The zero function is computed by $Z(1)$, the successor function is computed by $S(1)$, and for any $n>0$, the $i$-th projection function $p_i^n(x_1,\mathrm{\dots },x_n)=x_i$ is computed by $T(i,1)$.∎

Proposition 3.

URM-computability is closed under functional composition.

Proof.

This is proved in the entry on combining URMs. ∎

Proposition 4.

URM-computability is closed under primitive recursion.

Proof.

Suppose $f:{\mathbb{N}}^m\to \mathbb{N},g:{\mathbb{N}}^{m+2}\to \mathbb{N}$ are computed by $M,N$ respectively. Let $h:{\mathbb{N}}^{m+1}\to \mathbb{N}$ be obtained from $f,g$ by primitive recursion, namely,

$h(0,x_1,\mathrm{\dots },x_m)$$:=$$f(x_1,\mathrm{\dots },x_m)$

$h(n+1,x_1,\mathrm{\dots },x_m)$$:=$$g(h(x_1,\mathrm{\dots },x_m,n),n,x_1,\mathrm{\dots },x_m).$

Let $P$ be the following URM:

$T(1,p+1),T(2,p+2),\mathrm{\cdots },T(m+1,p+m+1),$

$M[p+2,\mathrm{\dots },p+m+1;p+m+2],J(p+1,p+m+3,q),S(p+m+3),$

$N[p+2,\mathrm{\dots },p+m+1,p+m+3,p+m+2;p+m+2],$

$J(1,1,m+3),T(p+m+2,1).$

where $p=\max (m+2,\rho (M),\rho (N))$ and $q=m+7$. The program works as follows:

${𝑰}_{\mathrm{𝟏}}\mathbf{,}\mathbf{\dots }\mathbf{,}{𝑰}_{𝒎\mathbf{+}\mathrm{𝟏}}$:

transfer the first $m+1$ registers to another are on the tape:

$$T(1,p+1),T(2,p+2),\mathrm{\cdots },T(m+1,p+m+1)$$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟐}}$:

compute $h(0,x_1,\mathrm{\dots },x_m)$ using $M[p+2,\mathrm{\dots },p+m+1;p+m+2]$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟑}}$:

if the content of register $p+1$ (formerly the content of register $1$) is the same as the content of $p+m+3$ (initially set to $0$), go to the last instruction whose index is $q(=m+7)$; otherwise continue to the next instruction: $J(p+1,p+m+3,q)$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟒}}$:

increment register $p+m+3$ by $1$: $S(p+m+3)$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟓}}$:

compute $h(i,x_1,\mathrm{\dots },x_m)$, where $i$ is the content of register $p+m+3$, using

$$N[p+2,\mathrm{\dots },p+m+1,p+m+3,p+m+2;p+m+2]$$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟔}}$:

go to instruction $m+3$: $J(1,1,m+3)$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟕}}$:

transfer result back to register $1$: $T(p+m+2,1)$.

Note that if $(x_1,\mathrm{\dots },x_m,n)\in \mathrm{dom}(h)$, then $P(x_1,\mathrm{\dots },x_m,n)\downarrow h(x_1,\mathrm{\dots },x_m,n)$. Otherwise, $h(x_1,\mathrm{\dots },x_m,n)$ is undefined. This can happen either $f(x_1,\mathrm{\dots },x_m)$ is undefined, in which case $M$ diverges, $g(x_1,\mathrm{\dots },x_m,i,h(x_1,\mathrm{\dots },x_m,i))$ is undefined, in which case $N$ diverges, or $h(x_1,\mathrm{\dots },x_m,i)\ne 0$ for all $i\in \mathbb{N}$, in which case $P$ loops indefinitely. In all cases, $P$ diverges. This shows that $P$ computes $h$.∎

Proposition 5.

URM-computability is closed under minimization.

Proof.

Suppose $f:{\mathbb{N}}^{m+1}\to \mathbb{N}$ is computed by $M$. Let $g:{\mathbb{N}}^m\to \mathbb{N}$ be obtained from $f$ by minimization. In other words, for any $𝒙=(x_1,\mathrm{\dots },x_m)\in {\mathbb{N}}^m$, set

$$A(𝒙):=\{y\in \mathbb{N}\mid (z,𝒙)\in \mathrm{dom}(f)\text{ for all }z\le y\text{ and }f(y,𝒙)=0\}$$

and define

Let $Q$ be the following URM:

$T(1,p+1),T(2,p+2),\mathrm{\cdots },T(m,p+m),M[p+m+1,p+1,\mathrm{\dots },p+m;1],$

$J(1,p+m+2,q),S(p+m+1),J(1,1,m+1),T(p+m+1,1)$

where $p=\max (m+1,\rho (M))$ and $q=m+5$. The program works as follows:

${𝑰}_{\mathrm{𝟏}}\mathbf{,}\mathbf{\dots }\mathbf{,}{𝑰}_{𝒎}$:

transfer the first $m$ registers to another are on the tape:

$$T(1,p+1),T(2,p+2),\mathrm{\cdots },T(m,p+m)$$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟏}}$:

compute $f(0,x_1,\mathrm{\dots },x_m)$ using $M[p+m+1,p+1,\mathrm{\dots },p+m;1]$, where the content of register $p+m+1$ is set to $0$ initially.

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟐}}$:

if the content of register $p+m+2$ (which is always $0$) is the same as the content of register $1$ (value of $f(0,x_1,\mathrm{\dots },x_m)$, if defined), go to the last instruction whose index is $q(=m+5)$; otherwise continue to the next instruction: $J(1,p+m+2,q)$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟑}}$:

increment register $p+m+1$ by $1$ (counter): $S(p+m+1)$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟒}}$:

go to instruction $m+1$: $J(1,1,m+1)$

${𝑰}_{𝒎\mathbf{+}\mathrm{𝟓}}$:

transfer content of register $p+m+1$ to register $1$: $T(p+m+1,1)$.

If $(x_1,\mathrm{\dots },x_m)\in \mathrm{dom}(g)$, then $Q(x_1,\mathrm{\dots },x_m)\downarrow g(x_1,\mathrm{\dots },x_m)$. Otherwise, $g(x_1,\mathrm{\dots },x_m)$ is undefined, which can happen either when $f(i,x_1,\mathrm{\dots },x_m)\ne 0$ for all $i\in \mathbb{N}$, in which case $Q$ loops indefinitely, or $f(i,x_1,\mathrm{\dots },x_m)$ is undefined, while $f(j,x_1,\mathrm{\dots },x_m)$ are defined and non-zero, for all , in which case $M$ diverges. In both cases, $Q$ diverges. Hence $Q$ computes $g$.∎

Since a recursive function is obtained by a finite application of functional operations specified in Propositions 3,4,5 on the basic arithmetic functions specified in Proposition 2, every recursive function is URM computable as result, proving Proposition 1.