Sideband #58: Halt! (or not)

evaluate(2B || !2B)

Hamlet’s famous question, “To be or not to be?” is just one example of a question with a yes/no answer. It’s different from a question such as, “What’s your favorite color?” or, “How was your day?” What it boils down to is that the young Prince’s question requires only one bit to answer, and that bit is either yea or nay.

Computers can be very good at answering yes/no questions. We can write a computer program to compare two numbers and tell us — yea or nay — if the first one is bigger than the second one. Computers are also very good at calculations (they’re just big calculators, after all). For example, we can write a computer program that divides one number by another.

But there are questions computers can’t answer, and calculations they can’t make.

We’ll start with a Divider program. It takes two numbers as input and calculates an answer for its output.

There are two senses in which computers might be unable to calculate something.

In the first sense, the calculation is possible in principle, but there isn’t enough time in the age of the universe to perform it. The  calculation is intractable.

In the second sense, the calculation isn’t possible even in principle.

It’s this second sense (only) that I’m writing about today.

Consider the simple calculation program mentioned above; it divides one number by another. Let’s call the first number the dividend (the thing divided), and the second number the divisor (the thing we divide by).

Calculation completes!

If we give the program 100 and 25, we want it to calculate 100 ÷ 25, which is 4.0.

Importantly, we’re able to take the number 100, divide it by 25, and come up with an exact result: 4.0.

What’s important here is that the calculation stops because it has generated a complete result.

What happens if we give our program a 1 and a 3?

Calculation loops forever!

It begins to calculate 1 divided by 3, which as a decimal number has a fraction that goes on forever: 0.333….

Unless our program has some sort of “don’t calculate forever!” escape clause, that’s exactly what it will do: calculate forever. You would run into the same problem if you attempted to calculate 1 ÷ 3 using long division: you keep getting more 3s.^[1]

Actual computer programs that do potentially endless calculations, such as division, must implement some sort of “guard rail” to prevent endless loops. (Programmers who mess this up create buggy code capable of falling into a loop trap — usually resulting in complete lack of response from the app.)

It’s a magical oracle!

Given the potential for some program, let’s call it P, to find itself in an endless loop, it would be nice if we had some other program that could tell us whether that will happen.

Let’s call that one the Decider. It takes program P along with some intended input and tells us if P will go into an infinite loop given that intended input.

In other words, if we asked:

Decider: Divide (100, 25)?

The Decider would reply: “Halts!” (Note that the Decider doesn’t actually do the division. It can’t tell us the answer is 4, only that the the Divide program does halt in this case.)

If we asked:

Decider: Divide (1, 3)?

The Decider would reply: “Loops!” (And that’s why the Decider doesn’t run the input program. In this case the Decider would get trapped in the same loop Divide does.)

Computers can do so many things, it seems like this wouldn’t be impossible.

Turns out: it is.

It is impossible (even in principle) to create a Decider program that can take some other program, and the intended input for the program, and tell us if that program will lock up on that input.

It seems easy to see that 1 ÷ 3 produces a fraction that goes on forever (0.333…) while 1 ÷ 4 does not (0.25). But there are larger numbers where it would not be so obvious, and Divide is a very simple program, anyway.

Determining whether a complex program locks up is much more of a challenge. (And the point here is that it’s been shown to be fundamentally impossible.)

The formal proof that a Decider program is impossible is very abstract and mathematical (which proofs tend to be), and uses a technique called the diagonal method to demonstrate a mathematical contradiction that requires the impossibility of a Decider.^[2]

But there is an informal proof that I think suffices. It’s a computer program version of the Liar Paradox. We use the idea that a Decider program is possible to prove that a Decider program is impossible.

A born trouble-maker!

Assume we have a Decider. We can use it inside another program, let’s call it a Liar.

This new program takes an input program and passes it to the Decider program inside.^[3]

If that Decider says the input program runs forever on that input data, the Liar halts and says, “Done!” But if the Decider says the test program will halt, then the Liar enters an infinite loop and runs forever.

Remember how the Decider can’t run the input program because it might get caught in a loop? The Liar uses the fully determined output of the Decider to act as though the program was run but reverses the “caught in a loop” logic!

This type of self-referencing logic reversal is the heart of the Liar Paradox!

So a Program X that would run forever makes the Liar halt and say, “Done!” But a Program Y that would halt makes the Liar run forever.

Now what happens if we start with Liar-A and give it Liar-B?

We give one Liar (A, right) another Liar (B, left) as input.

In this set up, Liar-A applies Liar-B to both inputs of its inner Decider, who has to decide what happens to a Liar taking a Liar as input.

Inside Liar-A, the Decider must decide: Halts or Loops?

So the Decider inside Liar-A has to figure out what happens in the exact situation we just created (a Liar taking a Liar as input). It’s deciding what happens when it decides, but the logic-reversal of the Liar generates a kind of “hall of mirrors” effect.

▶ Suppose the Decider says: (Liar-B) Loops!

That means Liar-A will halt (and say, “Done!”).

But Liar-A is the same program as Liar-B, which the Decider said runs forever, so Liar-A should also run forever.

Contradiction!

▶ Suppose, instead, the Decider says: (Liar-B) Halts!

That means Liar-A will enter an infinite loop and run forever.

But Liar-A is the same program as Liar-B, which the Decider said halts, so Liar-A should also halt.

Contradiction!

Remember that Liar-A and Liar-B are identical. The Decider inside Liar-A tries to answer the question: Does Liar-B (taking another Liar as input) halt or loop?

This is the same question we’re asking when we give Liar-B to Liar-A as its input: Does a Liar (taking a Liar as input) halt or loop?

Whatever Liar-A ends up doing contradicts whatever its Decider said about Liar-B. But they are the same program, so that’s impossible. Two identical things cannot contradict each other (a fundamental axiom of math and logic is that x=x).

The conclusion is that a Decider is not possible, even in principle.

Alan Turing (1912-1954)

Assuming one does exist leads to a contradiction, therefore none exist.

This analysis is known as the Turing Halting Problem (after Alan Turing who proved it), and it represents a fundamental limit on calculation.

Effectively, it limits computers to the discrete world — they are not transcendental.

Kurt Gödel demonstrated that mathematics has fundamental limits (using a proof not unlike Turing’s). Both proofs are based on Cantor’s proof that the real numbers cannot be enumerated (listed, counted).

Computation and mathematics are closely related, in particular through something called lambda calculus — a mathematical formalism for computation.

But that is a topic for another time!

Meanwhile, here is a very cute video that illustrates the Halting Problem — you’ll recognize the Decider and the Liar in the video^[4]:

^[1] To be precise, 1 ÷ 3 goes on forever in decimal (base 10) notation. In base 3, it would be simply: 0.1, which allows the division to halt. But base 3 has infinite fraction issues with other numbers. Whether a given fraction produces an infinite expression depends on the base and the fraction, but all bases have infinite fraction issues.

^[2] Cantor’s use of diagonalizing seems (at least to me) much less abstract in the context of what he was seeking to prove and much easier to understand. If you wanted to pursue Turing’s formal proof, Cantor is a good starting point.

Turing’s proof — as I understand it, and that’s not a given — basically says there’s no way to enumerate all possible non-halting programs, so there’s no way to know if a given program is on the non-halting list or not.

^[3] The Decider is expecting two inputs, a Program and its input. The Liar uses its single input for both of Decider’s inputs (which means the Liar requires a Program as input).

This is an important point (that took me a while to fully grasp)! The Decider is deciding on the same situation we’ve set up: a Liar taking a Liar as input (the video makes this very clear).

^[4] The H and X machines.