# recursive function is URM-computable

###### Proposition 1.

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},\ldots,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,

 $\displaystyle h(0,x_{1},\ldots,x_{m})$ $\displaystyle:=$ $\displaystyle f(x_{1},\ldots,x_{m})$ $\displaystyle h(n+1,x_{1},\ldots,x_{m})$ $\displaystyle:=$ $\displaystyle g(h(x_{1},\ldots,x_{m},n),n,x_{1},\ldots,x_{m}).$

Let $P$ be the following URM:

 $\displaystyle T(1,p+1),T(2,p+2),\cdots,T(m+1,p+m+1),$ $\displaystyle M[p+2,\ldots,p+m+1;p+m+2],J(p+1,p+m+3,q),S(p+m+3),$ $\displaystyle N[p+2,\ldots,p+m+1,p+m+3,p+m+2;p+m+2],$ $\displaystyle 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:

$\boldsymbol{I_{1},\ldots,I_{m+1}}$:

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

 $T(1,p+1),T(2,p+2),\cdots,T(m+1,p+m+1)$
$\boldsymbol{I_{m+2}}$:

compute $h(0,x_{1},\ldots,x_{m})$ using $M[p+2,\ldots,p+m+1;p+m+2]$

$\boldsymbol{I_{m+3}}$:

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)$

$\boldsymbol{I_{m+4}}$:

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

$\boldsymbol{I_{m+5}}$:

compute $h(i,x_{1},\ldots,x_{m})$, where $i$ is the content of register $p+m+3$, using

 $N[p+2,\ldots,p+m+1,p+m+3,p+m+2;p+m+2]$
$\boldsymbol{I_{m+6}}$:

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

$\boldsymbol{I_{m+7}}$:

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

Note that if $(x_{1},\ldots,x_{m},n)\in\operatorname{dom}(h)$, then $P(x_{1},\ldots,x_{m},n)\downarrow\!h(x_{1},\ldots,x_{m},n)$. Otherwise, $h(x_{1},\ldots,x_{m},n)$ is undefined. This can happen either $f(x_{1},\ldots,x_{m})$ is undefined, in which case $M$ diverges, $g(x_{1},\ldots,x_{m},i,h(x_{1},\ldots,x_{m},i))$ is undefined, in which case $N$ diverges, or $h(x_{1},\ldots,x_{m},i)\neq 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 $\boldsymbol{x}=(x_{1},\ldots,x_{m})\in\mathbb{N}^{m}$, set

 $A(\boldsymbol{x}):=\{y\in\mathbb{N}\mid(z,\boldsymbol{x})\in\operatorname{dom}% (f)\mbox{ for all }z\leq y\mbox{ and }f(y,\boldsymbol{x})=0\}$

and define

 $g(\boldsymbol{x}):=\left\{\begin{array}[]{ll}\min A(\boldsymbol{x})&\textrm{if% }A(\boldsymbol{x})\neq\varnothing,\\ \textrm{undefined}&\textrm{otherwise.}\end{array}\right.$

Let $Q$ be the following URM:

 $\displaystyle T(1,p+1),T(2,p+2),\cdots,T(m,p+m),M[p+m+1,p+1,\ldots,p+m;1],$ $\displaystyle 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:

$\boldsymbol{I_{1},\ldots,I_{m}}$:

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

 $T(1,p+1),T(2,p+2),\cdots,T(m,p+m)$
$\boldsymbol{I_{m+1}}$:

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

$\boldsymbol{I_{m+2}}$:

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},\ldots,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)$

$\boldsymbol{I_{m+3}}$:

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

$\boldsymbol{I_{m+4}}$:

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

$\boldsymbol{I_{m+5}}$:

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

If $(x_{1},\ldots,x_{m})\in\operatorname{dom}(g)$, then $Q(x_{1},\ldots,x_{m})\downarrow\!g(x_{1},\ldots,x_{m})$. Otherwise, $g(x_{1},\ldots,x_{m})$ is undefined, which can happen either when $f(i,x_{1},\ldots,x_{m})\neq 0$ for all $i\in\mathbb{N}$, in which case $Q$ loops indefinitely, or $f(i,x_{1},\ldots,x_{m})$ is undefined, while $f(j,x_{1},\ldots,x_{m})$ are defined and non-zero, for all $j, 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.

Title recursive function is URM-computable RecursiveFunctionIsURMcomputable 2013-03-22 19:04:51 2013-03-22 19:04:51 CWoo (3771) CWoo (3771) 7 CWoo (3771) Result msc 03D10 msc 68Q05 RecursiveFunction