Proof that The termination analysis is $\Pi_2$ undecidable

Question

I read here (https://en.wikipedia.org/wiki/Termination_analysis) that the termination analisys is $\Pi_2$ undecidable. However, i'm having a hard time finding a proof of that. Do you know a book where i can find such a proof? Is there an intuitive proof?

Thanks in advance

Answer 1

In computability theory the set of (indices of) Turing machines which halt on all inputs is generally denoted by "$Tot$" (for "total"); Soare's book introduces it that way for example, and proves its basic properties.

• Incidentally, while Soare's book is rather expensive it is one of the best computability theory texts around, the only real competitor in my opinion being Downey/Hirschfeldt: for example, in my opinion Nies' book has a more limited focus, Oddifreddi's book has lots of typos and is often unclear, and Lerman's book covers less and is more difficult to read, while basically every other book I'm aware of (e.g. Cutland, Sipser, Soare's new book, ...) simply doesn't cover the more advanced topics (like infinite injury) at all.

---

As to the proof, while some completeness results can be quite involved the $\Pi^0_2$ completeness of $Tot$ is nicely straightforward. Fix some $\Pi^0_2$ formula $\varphi(z)\equiv\forall x\exists y\theta(x,y,z)$ with $\theta\in\Sigma^0_0$, and for each $e\in\mathbb{N}$ consider the machine $M_e$ which on input $a$ searches for some $b$ such that $\theta(a,b,e)$ holds, halting if it finds one (and by default running forever if it doesn't).

It's easy to see that $M_e$ halts on all inputs iff $\varphi(e)$ holds; a standard argument shows that the map $f_\varphi$ sending each $e$ to an index for $M_e$ is total computable, and so provides a reduction witnessing $\{e:\varphi(e)\}\le_m Tot.$

• In fact, we get a "uniform completeness" result: we can find (an index for) $f_\varphi$ uniformly from (the Godel number of) $\varphi$. So in a sense, $Tot$ is "uniformly $\Pi^0_2$-complete." This is a general phenomenon - I'm not off the top of my head aware of a natural completeness result which doesn't hold uniformly.

---

As a final note, let me suggest the following as a good further exercise:

Show that in fact the Turing degree of $Tot$ is exactly ${\bf 0''}$ - the "halting problem's halting problem."

Of course the Turing degree analysis is coarser than the syntactic completeness result established above (both $Tot$ and $\mathbb{N}\setminus Tot$ have the same Turing degree after all, but the latter isn't $\Pi^0_2$), but in my experience this isn't intuitively clear at first.