I’ve been getting a lot out of The Little Schemer recently. It’s an amazingly little book. One topic covered is the Halting Problem which I first came across back when I was studying Theory of Computation at university. The authors use Scheme throughout the book, but I thought it’d be useful to translate the discussion into Javascript since Javascript is quite accessible for newcomers to functional programming.

Some functions always return a value. For example, the following simple function always returns the value of PI:

function pi(){
    return Math.PI;
}

Some functions go into infinite loops and never halt. For example, the following function enters a while loop and never comes out:

function eternity(){
    while(true) {
        // goodbye, cruel world
    }
}

Wouldn’t it be nice to be able to tell ahead of time whether a function is going to halt or go into an infinite loop? (cue evil laughter from the computer scientists in the back row)

Let’s write a function that tells us whether another function halts. (It’s easy to write functions that take other functions as arguments in Javascript because it’s a functional programming language). What would such a function look like?

function halts(fn){ // takes one argument, fn (a function)
    // code that determines if fn halts goes here
}

We’re not sure yet what code to put into the function body, but let’s start by looking at what we know about this function. It has to return True or False. True if the argument fn halts and returns a value, False if not. Simple right?

Let’s try out halts() on some functions we’ve already talked about to get a feel for how it’s supposed to work.

halts(pi); // returns true because pi() halts
halts(eternity); // returns false because eternity() doesn't halt

So far so good. Ok, let’s create one last function just for fun and see how halts() goes.

function maybe() {
    if (halts(maybe)) {
        eternity(); // never ends..
    } else {
        return "ok I halted!";
    }
}

The question is, does maybe() halt? Well let’s see..

• Let’s assume that maybe() halts. Therefore the if clause is true and so eternity() gets called.. meaning that maybe() never halts. Wait! That can’t be right! We just contradicted ourselves. We must have guessed wrong.
• Ok, in that case, let’s say that maybe() doesn’t halt. Therefore the else clause gets called instead, and we return a value. Meaning that we halted. But that’s a contradiction too!

What this means is that it’s impossible to write a function like halts() that determines whether another arbitrary function halts or not, because the very definition of such a function leads to a contradiction. Sucks to be a programmer huh?

Thanks Alan M. Turing (1912-1954), and Kurt Gödel (1906-1978).