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.

  • 2
    $\begingroup$ I think that Cutland's Computability: An Introduction to Recursive Function Theorey has a complete proof that the indicated function is primitive recursive. $\endgroup$ – danportin Nov 17 '13 at 18:13
  • $\begingroup$ Thank you, Daniel. @portin.daniel $\endgroup$ – superAnnoyingUser Nov 17 '13 at 18:36
  • 1
    $\begingroup$ This question is unrelated to computational complexity. I removed that tag. $\endgroup$ – 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$;

(2) Increment the value read;

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

You must prove that this is a primitive recursive function. (The details will depend on your exact definition of primitive recursive, and what functions you already know are primitive recursive.)

Then repeat for each instruction.

| cite | improve this answer | |
  • $\begingroup$ Ah, yes, I was afraid this could happen. Thank you, Ted. Look at the edit. $\endgroup$ – superAnnoyingUser Nov 17 '13 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.