The Halting Problem
Before looking at the halting problem, it is worth considering why it is interesting in the first place. One of the reasons the halting problem is important is that it is an entry point to a more fundamental issue: is there anything that computers cannot do?
A couple of clarifications are in order:
this is not about processor speed, memory size or other technological details. We are not asking “is there anything that compters cannot do right now but may be able to do in 50 years?”. We are asking: “is there anything no computer can do – doesn’t matter if now or in 50 or 1000 years?”.
this is not about things such as “can computers eat and digest ice cream?”. There are no tricks: in this post we will be talking about plain, dumb computer-as-a-calculator stuff: reading a numeric or textual input, doing some work and eventually returning some answer (or performing a set of actions).
Before answering this questions, let us first take a quick look at two concepts that will be useful for our understanding of the halting problem and its consequences.
What does it mean for a program to terminate? Well, as the word says, a program terminates when it finishes its job (whatever that is) in a finite amount of time (usually providing an answer or performing some action as a result):
a program receiving two integers, performing their sum and returning the result to the user.
an mp3 converter taking a raw WAV audio file as input, performing some work and after a minute or so returning a compressed mp3 file.
a search engine receiving a string (the search query), and returning a web page containing the search result.
In reality however, programs may occasionally not terminate.
For example, the following function starts printing the string
"hi" and never stops:
Run it, and your programming environment will likely crash or become unresponsive in some way or another.
This is clearly an extreme example; in reality, this kind of behavior appears sporadically, most likely as a result of some particular input:
Here, we see that
sometimesLoops goes into an infinite loop only when the input is
0 and prints the string
"DONE" in all other cases.
alwaysLoops never terminates,
sometimesLoops terminates most of the times; still, we can’t say that it terminates on all inputs, because there is one particular input,
0, for which it does not terminate.
Programs that eat programs
We have seen programs that takes integers, strings or some sort of data as their input in order to produce their output. But this is not the end of the story. One thing programs can do, for example, is to take another program as their input, and even produce a new program as their output.
This should be no surprise for programmers since tools like compilers, interpreters, and static analysers are nothing but programs whose task is to take another program as their input and either: translate it into another form (compiler), execute it (interpreter) or scan it for possible issues (static analyser).
Since programs are stored as plain text files, it shouldn’t be surprising to know that there’s nothing preventing a program to read another program and do something with it:
This is a huge topic and we’ll not go into details here. For now, just bear in mind that as well as taking “data” as their input, program may, in some circumstances, receive, manipulate and return other programs.
The halting problem
Given an aribitrary program
P always terminate? Or, in other words, does
P terminate on all inputs?
For very simple programs, answering this question is trivial. For example, for both of our examples,
sometimesLoops the answer is a no.
The reason is that
alwaysLoops never terminates, while
sometimesLoops terminates in most cases but it still gets stuck in an infinite loop when the input is
Therefore, we can claim that none of them terminates on all inputs.
So far so good, but what if our program suddently becomes hunderds, thousands or million lines long?
I’m sure you don’t need me to convice you that our simple reasoning technique will be impractical in this new scenario.
But… wait! Maybe we can write a program for that, right? That is: can we write a program that takes another program
P as its input, and tries to determine whether
P always terminate (or not)?
Let’s think about it. Suppose such an algorithm, called
termination, exists; it takes a file name and returns
true if the program contained in the file terminates (on all inputs) and
So far so good. Remember, we are assuming that that our
termination function is smart enough so that it can take any program and respond to the halting question correctly.
Consider the following program then (assuming it is stored in
strangeFunction terminate? We have two cases to consider:
strangeFunctionterminates – In this case, the call
true. Why? Because
terminationtakes an existing program and determines whether it terminates or not – that’s its job! Now, take a closer look at the code for
strangeFunction: can you see where the problem is? That’s right:
termination(strangeFunction.py)returns true (since
strangeFunctionterminates) but this causes the
whileloop to loop indefinitely meaning that…
On the other hand, assume
strangeFunctiondoes not terminate. Once again
termination(strangeFunction.py)will do its job correctly, this time returning
false. But we are up for more troubles: given how
strangeFunctionis deﬁned, this time the
whileloop will finish immediately (since its argument is
false) which means that
strangeFunctiondoes actually terminate!
Since in both cases we reached a contradiction, our assumption about the existence of
termination must have been wrong. Therefore, we must take a step back and accept the fact that a program such as
termination cannot exists.
In other words we have shown that it is not possible to write a program that solves the halting problem!
In this post, we explained the halting problem in an intuitive way and, on the side, we also clarified what we mean by terminating/non-terminating programs and briefly introduced the concept of programs that manipulates other programs.
We have seen that despite it being quite a well defined input-output problem (i.e. no “tricks” involved), it is not possible to write a program that solves the halting problem.
More broadly, this means that there exist some problem that cannot be solved by a computer, which answers our initial question: “is there anything that computers cannot do?” The answer is yes, and the halting problem is one example.
So we can’t solve the halting problem with a computer – fair enough. But is there anything else computers can’t do? Or is it the halting problem alone?” This will be the topic of a future post where we discuss how the halting problem affects (among many other things) the branch of computer science that deals with software verification and static analysis.