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.


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

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

Characteristic function

so that:

f(x)={1if φx(x)0if φx(x) 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.


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

φMˉ(x)={1if φx(x)0if φx(x) \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 HH such that:

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

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

So: φH(H)    φINT(Mˉ,H)=1=φMˉ(H)    φH(H)\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,

φH(H)    φINT(Mˉ,H)=0=φMˉ(H)    φH(H)\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!

Share on: