Halting Problem

When you run a program, usually, something happens. That’s kind of the point of a program, right? You click a button or you type in a command, and instantly you see some sort of feedback. You run the program, it executes, and then it’s done. In other words, it stops to a halt.

But this isn’t always the case. Sometimes a program runs for a really long time. Sometimes even for an infinitely long amount of time.

The problem is, there’s no way to actually tell wether a program will ever be done. In fact, it’s one of the most fundamental problems in computer science, so fundemetal, that solving it changed both mathematics and computer science forever.

Let's imagine a program.

while(true) {
    print("I am running.")
}

It's obvious to us that this program will never halt. If the computer has infinite memory, the program will run forever. But knowing the code is cheating. Our job is to write a function which will tell us if an arbitrary program will ever halt. So let’s pretend that we don’t know what the program is. To us, it’s just a black box.

An obvious solution is to run the program and see if we ever get an output. If the program runs, and we recieve an output, we know that the program halts. But wait. Some programs take a very long time to finish. What if our program didn’t halt now, but will halt after, say, 1000 iterations?

Well, we can wait for a certain amount of time. But that only gives us correct answers for programs that will always complete in that amount of time. To be completely sure, we would have to wait infinitely! I don’t know about you, but I don’t really have that much time on my hands.

It’s just impossible to tell if an unknown program will halt or not.

And when I say impossible, I don’t just mean hard. Alan Turing, the father of computer science, actually proved mathematically that the halting problem is undecidable, or in other words, impossible to solve.

Turing proved it by way of contradiction. Let’s pretend for a second that we have some function which can tell us whether a program halts or not. It would look something like this.

bool halts(program) {
    // ... some magic happening here
}

Now, consider the following function.

int g(program) {
    if (halts(program)) {
        while(true) {
            print("I am running")
        }
    } else {
        return 0
    }
}

We will first call the halts function, and if it returns true, we will loop forever. Otherwise, we’ll halt.

Now, let’s try calling that program with itself, and see what happens.

g(g)

If g halts then this program will never halt. But how can that be true, if we know that g is halting? On the other hand, if g never halts, then this program will halt, so g will both... halt and not halt?

It doesn’t make sense. And so Turing says, if it doesn’t make sense, then obviously this is undecidable.

This has some real world consequences. This is why you don’t get a compiler error if you write an infinite loop. This is why stack overflows exist: If we could predict them, we could stop them from happening.

But there are some interesting, practical solutions to stopping infinite loops. One of them is in the cryptocurrecy Ethereum.

On the Ethereum platform, running programs isn’t free. Each time your program is run, a certain amount of “gas” is deducted from your account, just like if you were driving a car. You only have a certain amount of gas, so if you write an infinite loop, you’ll spend all of it immidately and your car, or your program, will just stop.

The Halting problem is a big deal because it’s one of the first times mathematicians called something undecidable. It’s the first time they said “We can’t know this.” And this spawned a boatload of other problems that were also undecidable.

In fact they realised that almost anything about a programs behaviour is undecadible. Does the program halt on all inputs? Undecidable. Does the program return correct output for all inputs? Undecidable. What's the optimal machine code for a given program to be compiled to? Undecidable.

So keep that in mind the next time your client asks for something hard. It might just be mathematically impossible. :]

References:

Halting Problem
https://en.wikipedia.org/wiki/Halting_problem

Rice's Theorem
https://en.wikipedia.org/wiki/Rice%27s_theorem

Entscheidungsproblem
https://en.wikipedia.org/wiki/Entscheidungsproblem

Accidental and Essential Complexity