The Halting Problem

Welcome to the second issue of “Intractable Problems,” a column designed to challenge and stimulate your thinking skills. In the last issue, I promised to show you that there are some types of problems that cannot be solved, in any conceivable way! This may be quite a shock for those of us who believe that there will always be a solution for everything, such as faster than light travel, the current deficit, bug free software, etc.

Allan Turing, a famous mathematician, was the first person to show that some problems are `undecidable’, in the sense that no method can ever be found for solving them. He did this by proving that it is impossible to specify any algorithm which, given an arbitrary computer program and an arbitrary input to the program, can decide whether or not the program will eventually halt.[1]

This means is that it is impossible for us to write a computer program which can check if every computer program is correct. What a surprise! It means that there are some limits to the types of problems that we, as computer experts, can solve.

Think about a computer program which, given some data, either stops and outputs a result if it can, or runs forever if it can’t. If it stops then we know that the program solved the problem. Turing asked if anyone could write another program which could tell, in advance, if the first program would ever halt.

Let’s assume that I can write such a program. Then my program halts when it decides whether the first program will halt or not. My program puts out a 1 if the first program will halt, otherwise it puts out a 0.

Let’s run my program on itself. My program reads itself as data, and it can decide if my program runs correctly. Of course it does, I am a good programmer. My program will always halt, having arrived at the proper decision.

Now, let’s make a simple change to my program. Let’s change it so that instead of halting whenever it would have put out a 1, it goes into a loop and never stops. Now, if we run my changed program on itself, one of two things will happen. It will either stop and put out a 0 or it will run forever.

If we suppose that it stops with a 0, then obviously the unchanged program would have halted with a 0, too. But if it did, then the 0 means that my changed program would not halt, yet clearly it did. This can’t be right.

Well then, let’s suppose that my program doesn’t halt. Then it must be in a loop, which means that program is trying to put out a 1. But this means that the program being checked, my changed program, should halt. Clearly it didn’t, as that’s what we supposed.

We’re quite muddled now. How can both choices be wrong? The only answer is that our original assumption must be false. Obviously I can’t write a program which checks to see if other programs will halt. (No one else can write this program, either.)

So, clearly, there are some problems that can never be solved.  Now, this can be useful because the next time your boss asks you to solve a difficult problem, you could assess whether this is one of these ‘undecidable’ problems or simply a more normal ‘impossible’ problem. Every intractable problem will fall into one of these two categories. However, be warned that most of the apparently intractable problems encountered in practice are decidable and can be solved with the aid of an infinitely parallel or non-deterministic computer. What this means is that if you have a machine that can work on an infinite number of solutions all at the same time, then many intractable problems can be solved.  You might like to think of quantum computers? So beware, it’s quite hard to use undecidability as an excuse for not trying.

Next issue, we will move on to a lighter topic – making money in the stock market. I will show you that there are enough similarities between the market performance and a completely random process for all of us to seriously consider using random guesses for choosing stock. And you thought that skill was involved?

Footnotes

1. Turing, A. “On computable numbers, with an application to the Entscheidungsproblem”, Proc. London Math. Soc. Ser. 2, 1936, Vol. 42, pp. 230-265 and Vol.43, pp. 544-546.