You are here
HomeURM computable
Primary tabs
URM computable
Let $M$ be an unlimited register machine (URM), and $r$ a finite sequence of nonnegative integers. Recall the following notations:

$M(r)$ denotes the computation of $r$ by the program of $M$,

$M(r)\!\downarrow$ denotes that the computation halts ($M$ converges on $r$),

$M(r)\!\downarrow a$ denotes $M(r)\!\downarrow$, and $a$ is the content of register 1 in the output,

$M(r)\!\uparrow$ denotes that the computation does not halt ($M$ diverges $r$).
In the case where all but finitely many values of $r$ are $0$, say $r=r_{1},r_{2},\ldots,r_{n},0,0,\ldots$, we also write $M(r_{1},\ldots,r_{n})$ to emphasize the fact that $r_{i}=0$ for all $i>n$.
Definition. Let $f:\mathbb{N}^{n}\to\mathbb{N}$ be an $n$ary partial function on natural numbers (including $0$ in this discussion). $f$ is said to be URMcomputable if there is a URM $M$ such that $M(r_{1},\ldots,r_{n})\!\downarrow f(r_{1},\ldots,r_{n})$ precisely when $(r_{1},\ldots,r_{n})\in\operatorname{dom}(f)$. When $f$ is URMcomputable by $M$, we also say that $M$ computes $f$.
In other words, if $(r_{1},\ldots,r_{n})$ is in the domain of $f$, then we have a halting computation
start 
$r_{1}$  $\cdots$  $r_{n}$  $0$  $0$  $\cdots$ 
$\vdots$ 
halt 
$f(r_{1},\ldots,r_{n})$  $\cdot$  $\cdot$  $\cdots$ 
If on the other hand $(r_{1},\ldots,r_{n})$ is not in the domain of $f$, then the computation of the above input never terminates.
For example, $f(r_{1},r_{2})=r_{1}+r_{2}$, addition of two nonnegative integers, is URMcomputable, as is shown in this entry.
Here are two more basic examples:

(subtraction by $1$): $f(r_{1})=r_{1}1$. Note that $f$ is a partial function that is not total, because $f(0)$ is not defined. A URM that computes $f$ is the following:
$M=J(1,4,1),S(2),J(1,2,6),S(3),J(1,1,2),T(3,1)$ First, $M$ compares the $r_{1}$ with $r_{4}:=0$. If they are the same, it loops indefinitely. Otherwise, $M$ increments $r_{2}$ by $1$, and then compares $r_{1}$ with $r_{2}$. If they are the same, then $M$ transfers $r_{3}:=0$ in register $3$ to $r_{1}$ in register $1$. Otherwise, it increments $r_{3}$ by $1$ and loops back to the second instruction. The computation continues until $r_{1}=r_{2}$, and when this happens, $r_{1}$ is set to be $r_{3}$.

(parity checking): $f(r_{1})=1$ if $r_{1}$ is odd, and $f(r_{1})=0$ otherwise. In other words, $f(r_{1})$ is the remainder of the division of $r_{1}$ by $2$. A URM that computes $f$ is the following:
$\displaystyle M$ $\displaystyle=$ $\displaystyle J(1,2,14),T(1,2),S(2),S(3),S(3),J(1,3,9),J(2,3,11),J(1,1,4),$ $\displaystyle Z(1),J(1,1,14),Z(1),S(1),J(1,1,14)$ Basically, with input $r_{1}:=m$, $M$ first sets $r_{2}:=m+1$. Then by incrementing $r_{3}$ by $2$, $M$ tests whether $r_{1}=r_{3}$ or $r_{2}=r_{3}$. If the former, then $M$ sets $r_{1}:=0$, otherwise $r_{1}$ is set to $1$. The computation stops when the program jumps to the nonexistent instruction $14$.
Remarks.

For any URM $M$ and any positive integer $n$, $M$ computes a unique $n$ary (partial) function $f$. This can be simply done as follows: take the contents $r$ of the first $n$ registers of the tape as input, and run $M$. Define a partial function $f:\mathbb{N}^{n}\to\mathbb{N}$ so that $r\in\operatorname{dom}(f)$ iff $M(r)\downarrow$, and when this is the case, set $f(r)$ to be the integer such that $M(r)\downarrow\!f(r)$.
Examples.

$T(5,2)$ computes, for any $n>0$, the $n$ary function $f(x_{1},\ldots,x_{n})=x_{1}$.

$T(5,1)$ computes $f(x_{1},\ldots,x_{n})=0$ for any $0<n<5$, and $g(x_{1},\ldots,x_{n})=x_{5}$ for any $n\geq 5$.

$J(1,1,1)$ computes the empty function $\varnothing$ for all $n\geq 0$.


More generally, a partial function $f:\mathbb{N}^{n}\to\mathbb{N}^{m}$ is said to be URMcomputable iff there is a URM $M$ such that $M(r_{1},\ldots,r_{n})\!\downarrow$, and the $i$th coordinate of $f(r_{1},\ldots,r_{n})$ is the content of the $i$th register, $i\in\{1,\ldots,m\}$, precisely when $(r_{1},\ldots,r_{n})\in\operatorname{dom}(f)$.
The function $f$ above can be expressed as $(g_{1},\ldots,g_{m})$, where each $g_{i}:\mathbb{N}^{n}\to\mathbb{N}$. Then it is not hard to show that $f$ is URMcomputable iff each $g_{i}$ is URMcomputable.

One of the fundamental facts about URM computability is the following: a function is URM computable iff it is Turing computable. By Church’s thesis, this means that URM computability is equivalent to effective computability.
References
 1 J. C. Shepherdson, H. E. Sturgis, Computability of Recursive Functions. Journal Assoc. Comput. Mach. 10, 217255, (1963).
 2 N. Cutland, Computability: An Introduction to Recursive Function Theory. Cambridge University Press, (1980).
Mathematics Subject Classification
68Q05 no label found03D10 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