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

Question

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”?

Answer 1

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.

Answer 2

There is a result known as Richardson's theorem (see https://en.wikipedia.org/wiki/Richardson%27s_theorem?wprov=sfla1), which uses the undecidability of the halting problem to prove that presence of a natural class of functions on reals does not admit a decidable equality comparison for mathematical expressions containing variables, because solving equations involving those functions is undecidable.

Answer 3

You say:

"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."

This is an interesting point. This issue is precisely why Turing introduced the Universal Machine - it turns the issue of being unable to create a single algorithm for all machines at once, while possibly being able to create an algorithm for each individual machine separately, into the issue of being unable to create an algorithm for one specific machine (i.e the Universal Machine).