The Halting Problem

Why should we care?

Have you ever had a program crash on you? A program which the OS closes with the message “This program is not responding” or some other barely decipherable message?

You might be incredibly lucky and have never seen such a message. Well done to you! You should be aware that others *do* have such issues and they’re annoying!

If you’ve been blighted by such computer behaviour you might ask yourself a crucial question. Why doesn’t a phone App store (or similar) act to prevent this software being released? Shouldn’t they have a clever program which will prevent a program that never completes from ever being released?

The answer has two words. The Halting Problem.

The halting problem

This is where a program `H` (more specifically a Turing Machine) should determine if a decision problem `P` for a given input `I` will ever halt.

It is important to note that for a Turing machine a program and an input are essentially the same thing. That is, the input of a Turing machine is actually the initial state of the machine itself.

Halting means that the program will either accept it and halt or reject it an halt.

The halting oracle H