Why does Alan Turing proof of the halting problem is considered a proof that mathematics is undecidable

computational mathematicsdecidability

Whenever I read about the Entsheidungsproblem or the halting problem, I read that this proof proves that there is no general algorithm to solve this problem for any given algorithm with a given input. However, I don’t understand why this means that mathematics is undecidable?

Because the word “general” means that there is no one way to solve the problem for “all” algorithms, but that doesn’t mean that there is no solution to every individual algorithm on its own.

A special method or algorithm to solve its halting problem for and only for that very algorithm, so this doesn’t necessarily conclude that mathematics is undecidable. It might mean that the question of “what are the algorithms that solve the halting problem for all algorithms with inputs?” Is just too general to answer. It’s like asking what is the color of the ball without specifying which ball for example. The answer is different with each ball so the question is wrong. Just like asking what is the algorithm for solving the halting problem without specifying which algorithm the former is for, because the answer might be different with each different algorithm and maybe even with every input. So it’s not necessarily the case that mathematics is undecidable. If the proof contains a special algorithm that has no way to decide its halting problem. Why do references like these keep mentioning the word “general”?

Best Answer

The halting problem asks whether there exists a (single) Turing machine $H$ such that for every Turing machine $T$ and input $I$, when we feed $\langle T,I\rangle$ as input to $H$ then

  • $H$ will terminate with an answer Yes or No
  • the answer will reflect whether $T$ halts upon $I$

You suggest that instead we ask for a $H_T$ for every $T$? Or even go further and ask for a $H_{\langle T,I\rangle}$ for every pair $\langle T,I\rangle$? The latter would be easy! One of

PRINT "YES"

or

PRINT "NO"

will do the job, but I won't tell you beforehand which of these!

So back to the other idea: Suppose that for every TM $T$, there exists a TM $H_T$ such that $H_T$ halts for every input $I$ and gives us either a "YES" or "NO" that correctly tells us whether $T$ will halt on input $I$. Then in particular, there exists $H_S$ for the simulation TM $S$ (which we can write down explicitly), i.e., $S$ takes the description of a TM $T$ as input and simulates what TM $T$ would do when given $T$ as its input; in particular, $S$ halts on input $T$ iff $T$ halts on input $T$. Now from $H_S$ we can explicitly construct yet another TM $Z$, which is just $H_S$ except that every terminating node is replaced with "check what output we produced; if it is 'NO', terminate; otherwise, loop forever".

What might $Z(Z)$ produce? That depends on $H_S(Z)$, which again depends on $S(Z)$, so ultimately on $Z(Z)$! If $Z$ halts on input $Z$, then $S$ halts on input $Z$, then $H_S$ halts on input $Z$ with result "YES", then $Z$ does not halt on input $Z$ - contradiction. On the other hand, if $Z$ does not halt on input $Z$, then $S$ does not halt on input $Z$, then $H_S$ halts on input $Z$ with answer "NO", then $Z$ halts on input $Z$ - contradiction again! We conclude that $H_S$ cannot exist. Hence there exists at least one TM that does not have its specific halt-checker TM. Hence it is false that every TM has a halt-checker TM.


As to the undecidability of math: For any given statement $\phi$, we (i.e., a TM) can enumerate all finite sequences of math symbols and check whether such a sequence constitutes a proof of either $\phi$ or a proof of $\neg \phi$. Such a proof-finding TM, let's call it $P$, will either halt with a proof for $\phi$ or with a proof for $\neg \phi$ - or not halt at all. But perhaps we are lucky and this will always halt? Unfortunately, for every given TM $T$ and input $I$, we can formulate "TM $T$ will halt on input $I$" as a mathematical statement. Thus $P$ above will either find a proof that $T$ halts or a proof that it does not halt on input $I$. Per halting problem, we know that this is impossible. Therefore, there do exist some inputs for which $P$ does not halt. That is, there do exist some statements $\phi$ such that neither $\phi$ nor $\neg\phi$ is provable.