14
$\begingroup$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter).

I have questions regarding the difference between the two:

  1. I have some intuition about primitive recursive functions. For example, a function is primitive recursive if its algorithm is described by means of "only for-loops, not while-loops". How the intuition for $\Delta^0_0$ relations are different from that for primitive recursive ones?

  2. What syntactic condition does primitive recursiveness correspond to, if it does at all? More precisely, if $R$ is a primitive recursive relation, what is the syntactic necessary and sufficient condition for $\phi$ if $\bar n \in R \Leftrightarrow \mathbb N \models \phi(\bar n)$, modulo first-order equivalence of $\phi$?

EDIT: The for-loop explanation of primitive recursion can, for example, be seen in Section 2.5 of Schwichtenberg and Wainer's Proofs and Computations.

$\endgroup$
5
  • 4
    $\begingroup$ Just for those who haven't come across it (not the OP!) there's a nice example of a p.r. function which isn't $\Delta^0_1$ given in this answer. $\endgroup$ Commented Jun 21, 2015 at 9:16
  • 1
    $\begingroup$ @PeterSmith Don't you mean not $\Delta_0^0$? $\Delta_1^0$ are the recursive functions, and so of course contain all p.r. functions. $\endgroup$
    – James
    Commented Jun 25, 2015 at 3:49
  • $\begingroup$ Oops I mostly certainly did :-) $\endgroup$ Commented Jun 25, 2015 at 7:32
  • $\begingroup$ Seems to me that the "only for-loops, not while-loops" intuition actually describes the $\Delta_{0}^{0}$ class because a for loop seems like bounded quantification. No? $\endgroup$ Commented Jul 1, 2015 at 20:50
  • $\begingroup$ @QuinnCulver That's exactly why I confused the two; some describe primitive recursive functions as "only for-loops, not while-loops", including a Wikipedia article en.wikipedia.org/w/… and a book I skimmed a few years ago (too bad I don't have the copy and the book isn't in English). There should be a subtle technical point which I should have missed, I think. $\endgroup$
    – Pteromys
    Commented Jul 2, 2015 at 1:44

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ That's a neat way of explaining it. $\endgroup$ Commented Jun 1, 2020 at 17:18
  • $\begingroup$ That makes sense. What doesn't is why I hadn't heard this explanation in person (or I hadn't come up with this myself). Where did you learn this? $\endgroup$
    – Pteromys
    Commented Aug 1, 2020 at 1:40
  • $\begingroup$ @Pteromys I didn't learn it anywhere. I have previously been interested in characterizations of $\Delta^0_0$ formulas and after I happened to see this question I tried to see if I could think of a characterization in terms of some programming language. The fact that every $\Delta^0_0$ formula can be expressed in this programming language is pretty much obvious. The other direction strikes me as less obvious, but follows from the characterizations of $\Delta^0_0$ formulas described here. $\endgroup$ Commented Aug 2, 2020 at 19:01
2
$\begingroup$
  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.

$\endgroup$
3
  • $\begingroup$ 1. I knew this, as stated above. 2. By a similar argument to yours, one could even show that $\Delta^0_0$ cannot be "syntactically characterized". Obviously this is not what I mean by this phrase. $\endgroup$
    – Pteromys
    Commented Nov 16, 2015 at 23:35
  • $\begingroup$ @Pteromys: $\Delta_0^0$ formulas are syntactically decidable, but if you want to know for formula $\phi$ Is there any $\Delta_0^0$ like $\psi$ such that formula $\phi\equiv \psi$ is undecidable. $\endgroup$ Commented Nov 17, 2015 at 11:37
  • $\begingroup$ The smallest class of formula that can define primitive recursive function are in form of $\phi(x)\equiv \exists \vec{u}(t_1(x,\vec{u})=t_2(x,\vec{u}))$(see [link](en.wikipedia.org/wiki/Hilbert%27s_tenth_problem)) and also all $r.e.$ sets can defined in this class, so by Rice theorem a turing machine can not distinguish between primitive recursive predicate and the other one, so there does not exists syntactically characterization of primitive recursive sets in this language. $\endgroup$ Commented Nov 17, 2015 at 11:37

You must log in to answer this question.

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