recursive function is URM-computable

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.


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 pin(x1,,xn)=xi is computed by T(i,1). ∎

Proposition 3.

URM-computability is closed under functionalPlanetmathPlanetmathPlanetmathPlanetmath compositionMathworldPlanetmath.


This is proved in the entry on combining URMs. ∎

Proposition 4.

URM-computability is closed under primitive recursion.


Suppose f:m,g:m+2 are computed by M,N respectively. Let h:m+1 be obtained from f,g by primitive recursion, namely,

h(0,x1,,xm) := f(x1,,xm)
h(n+1,x1,,xm) := g(h(x1,,xm,n),n,x1,,xm).

Let P be the following URM:


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


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


compute h(0,x1,,xm) using M[p+2,,p+m+1;p+m+2]


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)


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


compute h(i,x1,,xm), where i is the content of register p+m+3, using


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


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

Note that if (x1,,xm,n)dom(h), then P(x1,,xm,n)h(x1,,xm,n). Otherwise, h(x1,,xm,n) is undefined. This can happen either f(x1,,xm) is undefined, in which case M diverges, g(x1,,xm,i,h(x1,,xm,i)) is undefined, in which case N diverges, or h(x1,,xm,i)0 for all i, 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.


Suppose f:m+1 is computed by M. Let g:m be obtained from f by minimization. In other words, for any 𝒙=(x1,,xm)m, set

A(𝒙):={y(z,𝒙)dom(f) for all zy and f(y,𝒙)=0}

and define

g(𝒙):={minA(𝒙)if A(𝒙),undefinedotherwise.

Let Q be the following URM:


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


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


compute f(0,x1,,xm) using M[p+m+1,p+1,,p+m;1], where the content of register p+m+1 is set to 0 initially.


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,x1,,xm), 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)


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


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


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

If (x1,,xm)dom(g), then Q(x1,,xm)g(x1,,xm). Otherwise, g(x1,,xm) is undefined, which can happen either when f(i,x1,,xm)0 for all i, in which case Q loops indefinitely, or f(i,x1,,xm) is undefined, while f(j,x1,,xm) are defined and non-zero, 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 PropositionsPlanetmathPlanetmathPlanetmath 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
Canonical name RecursiveFunctionIsURMcomputable
Date of creation 2013-03-22 19:04:51
Last modified on 2013-03-22 19:04:51
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Result
Classification msc 03D10
Classification msc 68Q05
Related topic RecursiveFunction