Halting Problem

Published May 25, 2022 - By Marco Garosi

The halting problem in the computability theory, that is the problem of deciding whether a given function (and thus a program) ever terminates, is not decidable: this means that a machine cannot tell wether a program will ever halt or not. It may wait for thousands of years, but never know if the program it’s running will terminate in the next few minutes, centuries or never.

Statement

The halting problem states that given a function $f(x)$ such that:

f(x) = \begin{cases} 1 &\text{if } x \in S \\ 0 &\text{if } x \notin S \end{cases}

Characteristic function

so that:

f(x) = \begin{cases} 1 &\text{if } \varphi_x(x) \downarrow \\ 0 &\text{if } \varphi_x(x) \uparrow \end{cases}

is a total yet non-recursive function.

Proof

The proof is made by contradiction. Let’s suppose that there exists a program (some code) $\bar{M} \in \text{GitHub}$ such that:

\varphi_{\bar{M}}(x) = \begin{cases} 1 &\text{if } \varphi_x(x) \downarrow \\ 0 &\text{if } \varphi_x(x) \uparrow \end{cases}

We can construct program $H$ such that:

\text{input}(x); \\ \text{if } \varphi_{\text{INT}}(\bar{M}, x) = 0 \text{then output(yes)} \\ \text{else while true } \{ x = x \}

Function $\varphi_H$ diverges when $\varphi_{\bar{M}}$ converges and vice-versa.

So: $\varphi_H(H) \uparrow \iff \varphi_{\text{INT}}(\bar{M}, H) = 1 = \varphi_{\bar{M}}(H) \iff \varphi_H(H) \downarrow$ .

On the other hand,

\varphi_H(H) \downarrow \iff \varphi_{\text{INT}}(\bar{M}, H) = 0 = \varphi_{\bar{M}}(H) \iff \varphi_H(H) \uparrow

This is, of course, a contradiction: hence a Turing Machine cannot tell whether a progamm will halt or not on a given input. It can only try and run it for some finite amount of time (even great amounts of time, like the life of the Universe): if the program halts, at some point, then it can tell it halts; if it doesn’t, it can only keep on going. If the program never halts, the machine only runs forever, without ever returning an answer.

This is much like driving on an infinite road and wondering whether you’ll ever run into some cavity in the asphalt. If you’ve run into one, then you can tell you did. If you did not, you can only keep on driving. However, in a finite amount of time, you cannot tell that the infinite road has no holes at all: one hole may be just some kilometers ahead from you — and you wouldn’t know!