The Halting Problem

Sat 21 July 2018 by A Silent Llama

Most people who have used a computer will have run into a program that suddenly hangs for, seemingly, no reason. The program freezes and won’t respond to anything you do. As a programmer I run into these depressingly often - usually because I made some mistake when I was coding. One of the reasons this happens is simple: computer programs do exactly what you tell them to. They’re like Golems. The clay creatures obey anything their master tells them to do, absolutely and to the letter. So if you ask one to, say, dig a trench it will. It will continue digging the trench indefinitely until it circles the world and then, for a change of pace, it’ll keep digging. You need to specify very carefully when it has to stop - maybe after 20 metres, or when the trench reaches a river or after an hour. There has to be some end condition. Computer programs are just like Golems - if you don’t tell them when to stop they’ll keep running in circles forever.

This is one of the causes of hanging programs (there are others but we’ll only consider this one today). Sometimes a program can get into a loop and won’t have any way to get out - we call this an infinite loop. It happened to me the other day when I wrote a program to read an excel file. The program was supposed to read each row into memory so I could do a calculation but I forgot to tell the program to move from the first row to the next one. The program sat reading the first row until my memory started to run out!

When faced with a hanging program people might rightly ask why computer programmers don’t do something about this problem. Surely there must be a way to detect if this type of thing is going to happen, right? Well - a computer scientist named Alan Turing asked that exact question as long ago as 1936 and came up with a surprising answer.

Alan Turing.

It sounds easy to say - can we detect if a program will halt or if it will loop indefinitely - but how exactly would one go about detecting something like that? We can’t simply run a program and wait - some calculations can take hours or weeks to run but still reliably stop. The Towers of Hanoi game played with 64 disks would take a computer hundreds of thousands (if not millions) of years to solve but it would halt.

When considering a difficult problem it’s often useful to imagine what would happen if we already had the solution. We imagine a perfect world - a world where the problem has already been solved and then see what we can deduce from that world. It often gives us clues about the eventual solution. Let’s imagine a world where we’ve solved the Halting Problem (which is the official name for the problem we’ve been considering). In this world we have a program, which we’ll call HaltingPredictor, and this program will tell us if any program halts or runs forever.

Lets think a little about what the HaltingPredictor will look like. Well for one it’ll have to take a program as an input. So HaltingPredictor(Program) will tell us if some Program halts or not. Hmm - except we’ve left something out - our Program might need some input too! (Think of a program on your PC - it needs input from your keyboard or your mouse to function properly). So we’ll also need to specify some input when we check if a Program will halt. So we have HaltingPredictor(Program, Input). It might seem a little strange to say that one program can take another program as input but if you think about it there isn’t any real reason why we can’t do that. A program is stored as code in files and we can easily just give those files to our HaltingPredictor program. In fact, if you like, you can open a program on your computer in a text editor to have a look at it - that’s a program (the text editor) looking at another program (not that you’ll be able to tell much from the gibberish).

Well - this is looking good. Our perfect world has a HaltingPredictor program and there are no more infinite loops. Huzzah! Except, well, we have to consider human nature. What is the first thing that would happen to our HaltingPredictor program? Well, you just know that someone is going to test it’s limits. People just can’t resist testing the limits of things.

Turing discovered a surprising ‘hack’. He came up with a program that started out something like this:

with open("turings-program.py") as f:
    turings_program = f.read()

Whoa! What’s happening there? Well - this code says that we’ll open the file called “turings-program.py” and we’ll call that open file f. We’re then going to read that file and save the contents for later. We’ll call that saved content turings_program. Well, we just said that programs could read other programs and now we have an example of a program reading itself. This is perfectly valid (you can even run that Python code yourself to see that it works - you just need to call your Python file ‘turings-program.py’).

Turing’s ‘hack’ continued - his entire program looked something like this:

with open("turings-program.py") as f:
    turings_program = f.read()

program_input = get_input()

if HaltingPredictor(turings_program, program_input) == "Run Forever":
    halt()

if HaltingPredictor(turings_program, program_input) == "Halt":
    run_forever()

Turing wanted to know - what would happen if we ask our HaltingPredictor what this program would do? It doesn’t really matter what input we give it so we’ll just leave program_input as a variable. What will HaltingPredictor(turings_program, program_input) look like?

Let’s say that the HaltingPredictor says it runs forever. Well - then we’re done right? We’ve predicted what will happen, no need to do anything further. You should have an uncomfortable feeling now. Something doesn’t look right here… Maybe we should run the program just to check? So we run the program and get to the first bit:

with open("turings_program") as f:
    turings_program = f.read()

Nothing funny so far - we’ve just read our own program. Next up is:

program_input = get_program_input()

Well - here we’ve read the program_input we gave (this could be anything really). Again - nothing funny.

if HaltingPredictor(turings_program, program_input) == "Run Forever":
    halt()

Okay - this is a complicated line. It says: if the HaltingPredictor program says turings_program runs forever given our program_input (which it did) then our next step is to halt. Well, we already know HaltingPredictor(turings_program, Program_Input) says we’re going to run forever so now we need to run the ‘halt’ command. But wait! The HaltingPredictor said turings_program would run forever! We just halted! The HaltingPredictor was wrong!

Hmm - in that case the only answer must be that the HaltingPredictor should’ve said the program halts. Phew! We were almost in big trouble there. Just to check we run the program again. This time we’ll skip this line:

if HaltingPredictor(turings_program, program_input) == "Run Forever":
    halt()

and we’ll run this one:

if HaltingPredictor(turings_program, program_input) == "Halt":
    run_forever()

Ok - so this time we know that the HaltingPredictor said we would halt. So now… Hmm… So now our program will run forever? The HaltingPredictor was wrong again? In fact no matter what prediction our HaltingPredictor makes turings_program will prove it wrong! It’s like computer aikido - turings_program uses the HaltingPredictor to defeat itself!

How could this happen? We were imagining a perfect world! How is it possible that the HaltingPredictor is wrong when our entire world was constructed around it being right? There is only one conclusion - the HaltingPredictor can’t exist in our perfect world. The Halting Predictor can’t exist even in an imaginary world we created were it could. (This is a logical argument we call Proof by Contradiction - we make an assumption and then look at the implications of that assumption. Somewhere we’ll find something that contradicts our assumption which proves that it was incorrect).

This is a very important proof in computer science - it tells us that there is a fundamental limit to what we can calculate. Some problems have no solution. (Note that what I’ve gone through here doesn’t constitute a formal proof - I’ve used Python to demonstrate but what you really need to do is show that this happens for all computer programs regardless of what language they’re written in. Turing did this by creating something called a Turing Machine which is an abstraction that can represent any computation.)

It’s not all bad news. We could create a partial halting predictor - one that works sometimes. If you think of a HaltingPredictor that has 3 outputs “Halt”, “Runs Forever” and “Don’t Know”. Some good research has gone into this area (see the wikipedia entry for The Halting Problem for more info). However Turing’s proof shows that we can never find a complete solution.