Writing is thinking. To write well is to think clearly. That's why it's so hard.

~ David McCullough
 

The Halting Problem in Javascript

2013年09月12日

The Specs for Halt

We suppose the existence of a function called Halt. It takes one parameter: a function, we will call f, that takes 0 parameters. Then Halt(f) returns true if the call to f() ever returns a value, and Halt(f) returns false if f() loops infinitely.

An important part of this assumption is that Halt(f) must always return true or false regardless of your choice of f. It must not itself loop.

A very small test suite

So first, let's come up with some simple functions to pass to Halt. Remember, they have to take 0 parameters.

One example is the Zero function:

function Zero() 
{ 
    return 0; 
}

When called, Zero simply returns 0. It's boring, but it's a function.

Another example is the Loop function:

function Loop() 
{ 
    while (true) 
    { 
        // do nothing
    }
    return 0; 
}

Clearly, Loop gets stuck in an infinite loop. It will never return a value.

So, let's use Halt.

Halt(Zero) returns true, because Zero() returns immediately gives us a value.

Halt(Loop) returns false, because Loop() never returns a value.

A weird problem

So far so good. But we run into problems with certain misbehaved functions.

function Weird() 
{
    if (Halt(Weird))
    {
        return Loop();
    }
    else
    {
        return Zero();
    }
}

Nevermind what use Weird is to a programmer. It's a valid Javascript function. So we are allowed to pass it to Halt.

So what is Halt(Weird)? Think about this for a while and see how much you can figure out.

What's wrong with Weird

We don't know up front, but we made a claim at the start that Halt always returns either true or false. And so let's investigate both possibilities.

First, suppose Halt(Weird) returns true. When we run Weird(), we get to the if statement. Since Halt(Weird) returns true, we take the first branch, and we wind up returning Loop(). But that means Weird() doesn't actually return and so Halt(Weird) must have been false, not true! We have a contradiction.

Not a problem. We must have made the wrong choice. Instead, Halt(Weird) must return false. Problem solved.

Right? Maybe not. If we trace through the code, we see that instead of taking the first if branch, we take the second. But the second returns Zero(). So while we assumed Halt(Weird)wasfalse`, it ended up halting after all. This alternative also gives us a contradiction.

Both of our cases ended in a contradiction. The only assumption we made was that it was possible to write a definition for the function Halt with the properties we want. But the mere existence of Halt allow us to construct functions that purposefully break it. There's no way around it. Halt cannot be written in Javascript.

A shout out to Self-reference

I want to point out a critical feature of the definition here. Weird is defined in terms of Halt. It was purposefully defined so that it could break Halt and so it only makes sense that it contain some reference to it.

I won't say much more than this: self-reference is at the heart of the halting problem. While you think about that, maybe you can also consider the following paradox:

There is a Barber who lives in a particular village. His job is to shave every man in the village... but he doesn't shave men who shave themselves. Does the barber shave himself?

Caveats

You might be thinking to yourself, "This is absurd. I can certainly tell when a function halts." You might even present an example like this one to drive home the point that this is crazy:

function ObviouslyHalts()
{
    for (var i = 0; i < 100; i++)
    {
        // do nothing
    }
    return 0;
}

And sure enough, I would agree with you this function does halt. However, you have missed a subtle point about the halting problem. The game isn't to figure out if this particular function halts. Or that all the functions I would typically write as a programmer halt. The problem specifies that Halt must work for all Javascript functions. And that's a much stricter requirement than to ask it work on all "reasonable" inputs.

In practice, the halting problem is solvable for a very large class of useful functions. For instance, if you banned the use of while loops and the use of recursion and required that all for loops were of the form for (var V = 0; V < N; V++) with V a variable and N a value which doesn't change between iterations, then your program would be guaranteed to halt.

In practice, most software can be written in this restricted for loops styles. This hsouldn't be too surprising, since we want to make it obvious our programs don't get stuck in infinite loops.

If for loops seem too restrictive, I will say that it's possible to add back in while loops and recursion, but you need to impose elaborate restrictions on them. Each iteraton of a while loop must bring you closer and closer to failing the condition. Each recursive function call must bring you closer and closer to reaching a base case.

Servers and the halting problem

The above story of Halt is taught to every single student of computer science. Less well-known (and honestly, more recently discovered), is how this relates to long-running computer programs that are intended to run (effectively) forever.

A server is any computer program which sits around waiting to be contacted by another. When it receives an incoming request, it produces a result, sends it off, then continues waiting. On and on. Forever.

How does the halting problem deal with these sorts of programs?

One way is to say that servers simply don't halt. But this is not as satisfying as it should be. Even though a server doesn't halt, it would feel funny to say they get stuck in infinite loops. And even worse, if the server might be potentially shut down, can we even say it doesn't halts? Whether it halts or not is now a function of how it interacts with the world.

Sadly, I don't have the time to get into the full story. But I would like to at least hint at the big idea. It turns out to be useful to introduce some a new notion: productivity.

A server is able to send and receive messages from any clients that want to connect to it. A server might not halt, and frankl, we stop caring if it does or not. Instead, we ask a new question: if we send it a message, will it eventually return a response back?

If when sent a message, a server eventually comes back with a reply, say the server is productive.

In a certain sense, productivity is halting "turned inside out". Instead of taking a finite amount of time to run, it's taking a finite of time to respond.

And with this mild extension, we are able to talk about halting in regards to servers as well as ordinary functions.

Technical details not included

I have purposefully scrubbed this article of as much technical detail as I could. Javascript is a large and semantically complicated language, and it is not well-suited for serious talk about the halting problem. However, I used it because I wanted to share the main gist of the halting problem with as many people as possible.

qed