1. URM-Computable Functions

　　URM is short for Unlimited Register Machine, which is a computation model conceived by Shepherdson and Sturgis.

　　The function $f$ is URM-computable iff there exists a program that URM-computes $f$.

 

2. Recursive Functions

　　Partially Recursive Functions is a set of computable functions defined by Gödel and Kleene in 1936.

　　

　　As an example, Ackerman Function defined as follow is a partially recursive function, but not a primitive recursive function.

　　　　　　$\psi(x)\simeq\begin{cases}n+1 & m=0 \\ \psi(m-1,1) & m>0\wedge n=0 \\ \psi(m-1,\psi(m,n-1)) & m>0\wedge n>0 \end{cases}$

　　To prove Ackerman is computable, we take three steps:

　　(1) Denumerate sets of 3-tuples such that $(x,y,z)\in S_v$ iff $p_{2^x 3^y 5^z}|v$;

　　(2) The following predicate is : $$R(x,y,v) \equiv `((\exists z<v) (x,y,z)\in S_v)\wedge((0,y,z)\in S_v\rightarrow z=y+1))\vee((x+1,0,z)\in S_v\rightarrow(x,1,z)\in S_v)\vee((x+1,y+1,z)\in S_v\rightarrow(\exists u) ((x,u,z)\in S_v\wedge(x+1,y,u)\in S_v))'$$;

　　(3) Function $\psi(x,y)=\mu z((x,y,z)\in S_{\mu v R(x,y,v)})$ is computable.

 

　　 

3. Turing-Computable Functions

　　The three fundamental components of a multi-tape Turing Machine are an Alphabet (a finite set of symbols), a finite set of States and a Transfer Function.

　　The computation ability of a Turing Machine does not vary with its size of alphabet, its number of tapes, or whether its tapes are unidirectional or bidirectional.

 

　　Theorem.  URM-Computable Functions = Partial Recursive Functions = Turing-Computable Functions

　　The proof that a partial recursive function must be a URM-computable function is simply an application of with proper constructions.

　　To prove a URM-computable function must be a partial recursive function requires the knowledge of  and a conclusion derived from the proof of that  $\phi_e(\vec{x})=(c(e,\vec{x},\mu t(j(e,\vec{x},t)=0)))_1$ is partial recursive.

　　By the same token, one can prove that a Turing-computable function must be partially recursive, and any partial recursive function is Turing-computable.

 

4. Church's Thesis

　　The intuitively and informally defined class of effectively computable partial functions coincide exactly with the class of URM-computable functions.

 

 

References:

　　1. Cutland, Nigel. Computability: an introduction to recursive function theory[M]. Cambridge: Cambridge University Press, 1980