11
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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
    Commented Aug 17, 2011 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
    Commented Aug 17, 2011 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
    Commented Aug 17, 2011 at 16:35

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Aug 17, 2011 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
    Commented Aug 18, 2011 at 0:33
  • $\begingroup$ The links to springerlink.com are broken. I'm also unable to find any snapshots saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Mar 29, 2023 at 1:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .