# The representation of the step function is primitive recusrsive

I've been trying to construct a proof that Unlimited Register Machine (URM) computable functions are partial recursive, which follows from the universal function theorem. I could not prove that the representation of the step function is primitive recursive. Would someone help me with that?

To this end assume you have an effective coding of all the instructions, and an effective coding of the programs $\gamma$.

Then by representation of the step function I mean $$S(\gamma(P), n)=\delta(<Step(\gamma(P),(n)_0,(n)_1,\dots,(n)_k,\dots)>)$$ where $\delta$ is and effective coding of $c_{00}(\mathbb N)=\{(x_i)_{i\in\mathbb N}:(\exists n\in\mathbb N)(\forall k>n)(x_i=0)\}$. For instance $$\delta(n)=\prod_{i\geq0}p_i^{x_i}$$

$(x)_i$ are $\delta$'s member functions.

EDIT: Assume for simplicity that each type of instruction is primitive recursive, and the step function brakes to cases of primitive recursive predicates. Assume that only instructions of the type $x_i\to x_i+1$ are allowed. Assume $P$ is a fixed program with memory $m$ and step function $S$. Then $S(t,x_1,\dots,x_m)=(t+1,x_1,\dots,x_k+1,\dots,x_m)$. Assume now that $\Pi$ is a primitive recursive coding of the $m$-tupples of numbers. The problem then boils down to proving that $\Pi\circ S\circ\Pi^{-1}$ is primitive recursive.

• I think that Cutland's Computability: An Introduction to Recursive Function Theorey has a complete proof that the indicated function is primitive recursive. – danportin Nov 17 '13 at 18:13
• Thank you, Daniel. @portin.daniel – superAnnoyingUser Nov 17 '13 at 18:36
• This question is unrelated to computational complexity. I removed that tag. – Carl Mummert Feb 13 '14 at 12:37

The details will depend on the precise way that $\gamma$ encodes the instructions of the program $P$. But the basic idea is to show that there is a primitive recursive function which 'decodes' program $P$ into instructions, and that the actions performed by each instruction are 'simple' enough that they are primitive recursive.

I don't know what instructions you have, but, for example, suppose one of the instructions is "add 1 to memory location $i$" (I assume the $n$ in your notation represents the memory of the computer). Then the operation would:

(1) Read ('decode') the value $(n)_i$ from $n$;

(3) Re-encode the new value of $n$.