Each year new computer systems are put into the market, featuring increased memory capacity, better screens but perhaps most importantly, stronger processors. More processing power results in handling more tasks per second or, in other words, less time per task.  A modern computer can carry out most operations in a fraction of a second, even though it took the most powerful computers minutes or even hours, 30 years ago. As computers get stronger, however, the tasks we ask them to perform get more complicated too. Whereas they once had to solve simple mathematical operations, they now have to bend their binary minds to complicated algorithms that require loads of processing power. Can we assume that every problem a computer faces is solvable, given that it has enough time? Or do problems exist that no computer, no matter its strength, can ever solve?

How fast a computer can solve a problem depends simply on how many steps a computer has to take to solve it and how many tasks per second that particular computer can carry out, which is determined mainly by its processing power. Obviously, an operation that consists of any amount of solvable steps, will itself be solvable. However, it is not too difficult to think of a program or operation that a computer will never finish executing. Imagine a very straightforward program that only tells your computer to open the program itself. This will result in a simple but never-ending loop in which the program keeps opening itself. Such a loop can occur in a small piece of code as well. Take for example a statement that tells the computer to return to the start of the code as long as a variable has a certain value. If that variable never changes value, the operation will never stop. The program will never halt. When such a loop occurs, it could point to an error in the code, or just a situation that the computer cannot handle. It would be very useful being able to tell if a piece of code or a program is going to eventually finish its task or if it shall run forever. Now considering this issue – whether or not a program will halt – is it possible to construct some sort of program that will tell beforehand if a computer will halt performing a certain operation? 

The halting problem

Alan Turing, British mathematician, computer scientist and cryptanalyst, perhaps known from the movie “The Imitation Game”, also contemplated this problem and actually solved it. This is how he did it;
Consider a machine, let’s call it “machine H”. Machine H can take as input the code of any program or machine and will tell whether that machine will eventually halt or not. It is not important whether or not this machine can actually ever exist, for now, just assume it could.

Now the idea Turing came up with is the following; assuming that we can construct such a machine H, what happens if we add another part upon this machine: a part that makes the machine enter an infinite loop if the original output is that the program halts, and that just stops the machine if the output is that the input program will not halt. This would look as follows:

Let’s call this new machine “machine H+”. Now, what would happen if we use as input for this machine H+, the machine itself? We “feed” the code for the new machine to itself…
There would be 2 options:

• The machine by itself would halt. Therefore, the part H of machine H+ would output “the program halts”, and the new part would make the machine enter an infinite loop.
• The machine by itself would run forever, making the H part of the machine output “the program will not halt”. Then the extra part would make the machine halt.

Notice that in both scenarios, we find a contradiction!
If the machine would halt, it will enter an infinite loop and thus not halt. If the machine would not halt, it will halt.
Using this somewhat simple illustration, Alan Turing proved that no such machine could ever exist. He therefore drew the conclusion that it is impossible to ever create a program or machine that will determine for any possible program whether it will eventually finish or not.
In this way, Turing proved that problems exist that a computer -no matter its strength- can never solve.

Dit artikel is geschreven door: Pieter Dilg