You are here
Homerecursive function is URMcomputable
Primary tabs
recursive function is URMcomputable
Proposition 1.
Every recursive function is URMcomputable function.
The proof can be broken down in several simple steps.
Proposition 2.
The zero function, the successor function, and the projection functions are URMcomputable.
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.
URMcomputability is closed under functional composition.
Proof.
This is proved in the entry on combining URMs. ∎
Proposition 4.
URMcomputability 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}}}$:
 $\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.
URMcomputability 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 nonzero, for all $j<i$, 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.
Mathematics Subject Classification
03D10 no label found68Q05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections