Post History

According to [Wikipedia](https://en.wikipedia.org/wiki/Arithmetical_hierarchy#Examples), the set of (indices of) Turing machines that compute total functions, i.e. which halt on all inputs, is a $\Pi_2$ set. If we use the [variation of the definition of arithmetical hierarchy which includes primitive recursive functions](https://en.wikipedia.org/wiki/Arithmetical_hierarchy#Extensions_and_variations), then it is fairly straightforward^[If you are comfortable with encoding data into naturals.] if tedious to explicitly write ([given a reasonable encoding of a reasonable representation of Turing machines](https://en.wikipedia.org/wiki/Post%27s_theorem#Formalization_of_Turing_machines_in_first-order_arithmetic)) a primitive recursive function that returns the state of the Turing machine encoded by $e$ on input $n$ after $s$ steps. We get the $\Pi_2$ formula: $\forall n.\exists s.\mathsf{steps}(e, n, s)=\mathsf{HALT}$. It may require a $\Sigma_1$ formula to formulate $\mathsf{steps}(e, n, s)=\mathsf{HALT}$ without primitive recursive functions, but that is not an issue for us because $\exists s.\mathsf{steps}(e, n, s)=\mathsf{HALT}$ would still be a $\Sigma_1$ formula.

Using [Post's Theorem](https://en.wikipedia.org/wiki/Post%27s_theorem), if we could show that the above set is not recursively enumerable given an oracle that can answer whether a *plain* Turing machine halts, then we'd know that the formula wasn't $\Sigma_2$ and thus not $\Delta_2$. At this point, we're back to where you are.

A well-known result is that the set of total computable functions is $\Pi_2$-complete (e.g. Theorem 3.2 of Chapter IV of "Recursively Enumerable Sets and Degrees" by Robert Soare). So if this set was $\Delta_2$, we'd have $\Pi_2 = \Delta_2$. The proof from there is roughly as follows.

Given any $\Pi_2$ set, $A$, we have, by definition, $x\in A \iff \forall y.\exists z.R(x,y,z)$ for some recursive relation $R$. We can define a one-to-one recursive function $f$ such that $f(x)$ is a(n index of a plain) Turing machine which halts on input $u$ if and only if $\forall y < u.\exists z.R(x,y,z)$ holds. If $x\in A$, then this resulting Turing machine $f(x)$ implements a total function, i.e. $f(x)$ halts on all (infinitely many) inputs. If $x \notin A$, then $f(x)$ halts on finitely many inputs. Therefore, $x \in A$ if and only if $f(x)$ is total. $\square$