# Are Primitive recursive functions (with bounded $\mu$ operator) equivalent to other known computational model?

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?

• 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). Commented Mar 27 at 23:32
• See here for a proof-theoretic characterization. Commented Mar 28 at 7:57
• 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. Commented Mar 29 at 5:09

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.