2
$\begingroup$

I am confused about the relationship between the quantifier complexity of formulae in the language of arithmetic and the computational classification of the sets those formulae define.

Specifically, my question can be boiled down to asking whether or not adding the minimization operator $μ$ to a primitive recursive formula always produces a $Δ^0_1$, total computable function. If this is the case, what is the proof, what guarantees the minimization always returns a value? If this is not the case, how does this not violate Post’s theorem?

What is confusing to me is that the minimization operator seems to perfectly correspond to an unbounded existential quantifier in my mind, i.e. they both are recursively enumerable but not recursive. If the number we’re looking for exists, an unbounded search will find it after a finite time. But if the number doesn’t exist, we will search forever. The minimization operator is often introduced in the context of loops. $Δ^0_1$ formulae have bounded quantifiers so they are clearly analogous to for loops, while the minimization operator is analogous to a while loop. But while loops are not guaranteed to halt (“while false, loop”), so how does fixing a minimization operator to a primitive recursive formula always produce a $Δ^0_1$ formula? If it doesn’t always, then the general recursive functions are not closed under minimization, which I thought was the point of the formalism, and we have general recursive functions which are $Σ^0_1$ which contradicts both my understanding of what Post’s theorem says and the definition of general recursive.

My only idea of how this could be solved is that, given Kleene’s normal form theorem, we know that we only need one use of minimization, which means we can always make the formula the minimization is attached to primitive recursive, and that somehow guarantees that the value the minimization is searching for will exist so it won’t loop forever, but I don’t know why that would be true if it is true. I guess the other option is that I do not understand Post’s theorem, or “general recursive/computable”. I always thought “general recursive/computable” meant the total functions closed under the primitive recursive functions and minimization, not the (non total) partial functions. As in, I thought the general recursive functions were the functions which are recursively enumerable and their complements are recursively enumerable, but not the functions which are recursively enumerable but whose complements are not recursively enumerable.

I know that I’m wrong about something, probably multiple things, but I cannot find an explicit answer to these questions in any textbook I have access to. What am I missing?

$\endgroup$
1
$\begingroup$

You're quite right that "the $\mu$-operator breaks $\Delta^0_1$-ness." As an explicit example, the formula $\theta(x,y)\equiv$ "the $x$th Turing machine with input $x$ halts within $y$ steps" is $\Delta^0_1$, but the unary relation $$H(x)\equiv \mbox{"}0\not=\mu y.\theta(x,y)\mbox{"}$$ is not $\Delta^0_1$.

However, this doesn't contradict Post's theorem. The mistake is the following:

I always thought “general recursive/computable” meant the total functions closed under the primitive recursive functions and minimization, not the (non total) partial functions.

That's not correct - (general) recursive functions are allowed to be partial. In particular, there is a recursive enumeration of the recursive functions, but there is no such enumeration of the total recursive functions.

Indeed, this is sort of the driving observation behind recursion theory. Remember that diagonalization tells us that we can never have an "effective" notion of "total effective function" - otherwise, the function $f$ given by $f(x) = 1+ t_x(x)$, where $t_x$ is the $x$th effective function according to this notion, would be simultaneously total effective and not total effective. Whenever we have a "concretely defined" class of total recursive functions, it falls short of being the whole class of total recursive functions.

By contrast, once we allow partiality this issue goes away. We can whip up a recursive enumeration $(\varphi_e)_{e\in\mathbb{N}}$ of the (partial) recursive functions (essentially, this is a universal Turing machine), and the function $$\theta(x)=1+\varphi_x(x)$$ is indeed recursive, but there's no contradiction: we have $\theta=\varphi_e$ for some $e$ such that $\varphi_e(e)$ is undefined. Our diagonalizing function $\theta$ is also therefore undefined at $e$, and so there's no issue. In fact, if we spend enough time thinking about this situation (and get a bit clever), we'll eventually arrive at the recursion theorem.

Of course, ease of use isn't a fully satisfying motivator for a shift in the notion of "fundamental object." But recursion theory is supposed to model algorithms, and the simple fact is that there are algorithmic procedures which don't halt, and - while we can easily check that a purported algorithm is "grammatically correct" - there is no good way to determine if an algorithm is going to halt on a given input. So in fact partial functions correspond better to what we care about than total functions.


Since you mention graphs: a (unary, for simplicity) recursive function can be identified with its graph $G_f:=\{(x,y): f(x)=y\}$, and a relation $R\subseteq\mathbb{N}\times\mathbb{N}$ is the graph of some recursive function iff:

  • $R$ is r.e., and

  • for each $x$ there is at most one $y$ such that $R(x,y)$.

If the function is total then its graph is recursive, but otherwise it's merely r.e. - this is a consequence of the second clause, since it means that we can compute $f(x)$ by searching for the unique $y$ such that $(x,y)\in G_f$. By contrast, if we drop the second clause this breaks: a total r.e. relation need not be recursive.

$\endgroup$
  • $\begingroup$ Many people (including perhaps the source of the OP's information) use "recursive" to mean "total recursive" and therefore explicitly say "partial recursive" when they don't insist on totality. Also, the OP may have learned a definition of the total recursive functions that obtains them from initial functions, composition, primitive recursion, and total minimization (i.e., minimization is allowed provided the resulting function is total). $\endgroup$ – Andreas Blass May 8 at 22:16
  • $\begingroup$ Andreas has described my exact experiences, I came to this subject from philosophy, not math, and most of my textbooks have set it up that way. I think my issue was that I had understood “recursive”/“computable” to mean a total function made up in the way Andreas described, so seeing “the general recursive functions are the recursive functions” led to my confusion with Post’s theorem because not all while loops terminate. So I think the answer to this last question will have it all make sense to me. But your answer has helped immensely already so thank you very much friend. $\endgroup$ – Dkn557 May 9 at 1:05
  • $\begingroup$ There are the primitive recursive functions which are easily seen to be computable in the intuitive sense. There are the total functions which are made from the primitive recursive functions and application of the minimization operator, such as the Ackermann function, and these are also computable in the intuitive sense. Then there are the partial (but not total) functions which are formed the same way, which are recursively enumerable, but whose complements are not, and are therefore only semi computable in the intuitive sense. And “general recursive functions” refer to all and only these? $\endgroup$ – Dkn557 May 9 at 1:05
  • $\begingroup$ @Dkn557 Yes. And every primitive recursive function is a total recursive function. However, your characterization of the total recursive functions isn't ideal: "the total functions which are made from the primitive recursive functions and application of the minimization operator" makes it sound like applying the minimization operator can never lead to partiality, which is not the case. Rather, the (partial) recursive functions are those which can be built from primitive recursive ones and minimization; some of these happen to be total. $\endgroup$ – Noah Schweber May 9 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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