3
$\begingroup$

There is a famous equivalence between types of grammars and automatons. However when discussing recursive functions, we only consider equivalence of General Recursive functions with Turing machines. However primitive recursive functions are considered separately and I don't know any equivalence of that computational model with any other. I was wondering whether primitive recursive functions are equivalent to any other known computational model. I was thinking about Turing Machine with bounded tape size (linearly bounded), since primitive recursive functions have bounded $\mu$ operator. However I couldn't find any result that would say that, so is there any known computational model equivalent to primitive recursive functions?

$\endgroup$
3
  • 1
    $\begingroup$ It is not equivalent to linearly bounded automata (LBA) nor Turing machine. LBA is in $\textsf{PSPACE}$ while primitive recursive is in $\textsf{EXPSPACE}$ while Turing machine is in $\textsf{RE}$. We know $\textsf{PSPACE} \subset \textsf{EXPSPACE} \subset \textsf{Ack} \subset \textsf{RE} \subset \textsf{R} \subset \textsf{ALL}$ (complexity zoo). $\endgroup$ Commented Mar 27 at 23:32
  • 1
    $\begingroup$ See here for a proof-theoretic characterization. $\endgroup$ Commented Mar 28 at 7:57
  • 1
    $\begingroup$ thanks Kenneth for editing the post, also for stating the fact that LBA isn't equivalent to primitive recursive functions. also for providing hierarchy for complexity classes. $\endgroup$
    – math boy
    Commented Mar 29 at 5:09

1 Answer 1

6
$\begingroup$

LOOP is a simple programming language which exactly captures primitive recursive functions.

Primitive recursive functions also have other characterizations. For example, they are the functions which are provably total in $\rm I\Sigma_1$ (a fragment of Peano arithmetic), and they are the functions computable by a Turing machine whose running time is in the Grzegorczyk hierarchy.

$\endgroup$
1
  • 1
    $\begingroup$ thank you for providing 3 different perspectives. I've also checked proof-theoretic aspect as well, LOOP programming language is very interesting as well. proof theory perspective, programming language perspective and computation model perspective (TM with specific running time) all equivalent to PR. $\endgroup$
    – math boy
    Commented Mar 29 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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