Primitive recursion and $\Delta^0_0$

It's many years after the original question was asked, but I saw this recently and think I can give a more satisfactory answer than the current one.

The $\Delta^0_0$ functions can be thought of as functions in a programming language with "only for loops, not while loops," but only if we cannot change the values of non-boolean variables. Maybe it's not clear what I mean, so here are some examples.

The following program is allowed:

program allowed(x):
   a = true
   for y = 0,...,x*x + 5:
      for z = 0,...,x*y*y:
         if x*x - y*y*y + z = 6:
            a = false
   return a

The following program is not allowed:

program not_allowed(x):
   a = 2
   b = 2
   for y = 0,...,x:
      a = a*a
      for z = 0,...,a:
         b = b*b
   return true

The idea is just that the bounded quantifiers of a $\Delta^0_0$ formula are analogous to for loops, but there is nothing in a $\Delta^0_0$ formula to simulate reassigning variables in any way other than incrementing them via a for loop. This ability to reassign variables is what makes possible primitive recursive functions like tetration.

1. Let $\Sigma =\left \{0,1 \right \}$, then it's easy to check that for every $\phi({\bf x})\in \Delta_0^0$ there exists a Turing Machine $M$ in $\Sigma$ alphabet such that:

   • $L(M)$ is in class of Elementary,

   • $\forall n\in\mathbb{N}(|n|\in L(M) \leftrightarrow \phi(n))$, which $|n|$ is binary representation of $n$ in $\Sigma$.

   But by Time hierarchy theorem we have $Elementary \subsetneq PR$, so there exists a language $L\in PR$ and $L\not\in Elementary$, therefore $L$ is not $\Delta_0^0$ definable.

2. Let $\Sigma = \left \{ \forall, \exists, \rightarrow, \neg, \wedge, \vee, <, =, +, \cdot, 0, 1 \right \}$. Let $A$ be set of all $r.e.$ languages in this alphabet. we can show every Turing Machine by a $\Sigma_1$ formula $\psi$ in this alphabet, (See this ). Define $M=\left \{L\in A |L\subseteq \left \{0,1 \right \}^* \wedge L\in PR \right \}$, then $M$ is nonetrivial subset of $A$, so by Rice Theorem, $L=\left \{x\in \Sigma^*|(x\: is\:a\:formula)\wedge L(x)\in M \right \}$ is undecidable. Therefore there doesn't exists any syntactic necessary and sufficient condition for deciding primitive recursive predicates.