General computable functions can be described either functionally (in terms of closure of the coordinate functions, constant functions, composition, primitive recursion, and $\mu$-recursion), or in terms of a Turing machine.

I have only seen primitive recursion defined in the functional language, i.e. functions obtained by coordinates, constants, composition, primitive recursion.

Is there a similar type of machine model for primitive recursion?

I am aware of some (pedagogical) programming languages, such as Hofstadter's BLOOP, that are PR-complete, but this approach doesn't really look like a Turing machine to me.

  • 1
    $\begingroup$ There is very little you can do with Turing machines except imposing resource bounds (time and/or space). A function is PR iff it is computable on a TM in time (or space) $O(A(c,n))$ for some constant $c$, where $A$ is Ackermann function, which is not a particularly elegant characterization. I’m not familiar with BLOOP, but what’s wrong with it? I would naturally go for a minimalistic programming language-like model rather than TM when asked to give a computational model exhausting primitive recursive functions. $\endgroup$ – Emil Jeřábek supports Monica Aug 17 '11 at 15:35
  • 3
    $\begingroup$ Is there a reason why you need a machine model? Such formulations are beneficial mostly for philosophical reasons. For example, the advantage of the Turing-machine formulation of the Entscheidungsproblem is that it focuses all of the "infiniteness" in one place: the tape; everything else about the machine is finite. This laid to rest a lot of philosophical uncertainties in the 1930s about the role of the infinite ${\mathbb N}$ in $\mu$-recursion and insertion of characters into unboundedly-long $\lambda$-terms. I'm not sure there's any reason to prefer a machine model now that... $\endgroup$ – Adam Aug 17 '11 at 16:33
  • 1
    $\begingroup$ ... Turing has established that the notion of computability does not rely on anything mysterious about the "less disciplined infiniteness" of the other formulations. $\endgroup$ – Adam Aug 17 '11 at 16:35

If you're willing to accept register machines (rather than just tape machines), you can get what you want via the Grzegorczyk hierarchy, which generates the class of primitive recursive functions in stages.

The ${n+1}^{th}$ stage of the hierarchy ${\mathscr E}_{n+1}$ is the closure of the zero, successor, projection, and hyper operation $H_n$ function under composition and bounded recursion.

Bounded recursion is defined just like primitive recursion, except that when defining a function $f$ at the ${n+1}^{th}$ level, the definitions of the base case and inductive case for $f(m,\bar x)$ must take the form $\text{min}(g(m,\bar x),...)$ where $g$ is a function from the $n^{th}$ level.

Every primitive recursive function belongs to ${\mathscr E}_n$ for some $n$, and every function in the hierarchy is primitive recursive.

Beltiukov's stack register machines (also here) give a "machine-oriented" characterization of the Grzegorczyk hierarchy -- and therefore of the primitive recursive functions. There is a slightly more accessible description of stack register machines here, starting on page 108.

  • $\begingroup$ The perhaps slightly more accessible equivalent answer is a C program with bigints and unlimited memory using only "for" loops with bounded integer limits, and no recursive function calls. $\endgroup$ – Ron Maimon Aug 17 '11 at 20:16
  • 4
    $\begingroup$ @Ron: This is not equivalent since C rules for 'for' loops are much too relaxed. For example, for (i=1; i<10; i++) i--; is a perfectly legal non-terminating program according to your restrictions. $\endgroup$ – François G. Dorais Aug 18 '11 at 0:33
  • $\begingroup$ I can't find a version of Beltiukov's paper that isn't in Russian, would you happen to have the link to such a resource? $\endgroup$ – user76284 Feb 1 '16 at 15:40

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.