Page loading
Home link logo
0%

The Halting Problem!

Need a quick buck? A while ago someone offered $1000 for a developer to “create a debugger program. This program will take as input the source code of another program, and will analyze that other program and determine if it will run to completion, or have an error, or go into an infinite loop.”

What do you think — would you take the contract?

Okay! In this lesson, you’ll learn whether that was a wise choice.

Brave! In this lesson you’ll learn whether that was a wise choice.

In this lesson, we’ll write programs in JavaScript. (But don’t worry, you won’t need to know much JavaScript: we only use functions, loops and variables.)

Here are three programs. Which one never finishes running?

// Program A:
function A(s) { return s.length > 3; }
A('hi');

// Program B:
function B(s) {
  for (let i = 0; i < s.length; i++) {
    s = s+'!';
  }
  return true;
}
B('hi');

// Program C:
function C(s) {
  while (s !== '') { s = ''; }
}
C('hi');

Program C does not have a return statement, but it does halt. (The function call returns undefined when it reaches the end of the function body.)

The answer is actually program B: it loops forever adding exclamation marks to s, starting with s='hi', then s='hi!', then s='hi!!', and so on. The loop variable i never catches up with the end of the string!

Program A actually does halt. It returns the value false, because 'hi'.length is not greater than 3.

The answer is actually program B: it loops forever adding exclamation marks to s, starting with s='hi', then s='hi!', then s='hi!!', and so on. The loop variable i never catches up with the end of the string!

Right! Although Program C has return true, this will never be reached: it loops forever adding exclamation marks to s.

The task is to write a JavaScript function called halts. It must return true or false to say whether a JavaScript program will finish running. More precisely, halts should look like:

function halts (funcStr, arg) {
  // Would `funcStr` halt when called
  // with the string argument `arg`?
  // Insert clever analysis here!
  return wouldHalt;
}

Let’s write some tests for halts. What should the following do?

const funcStr = `function (s) {
  return s.length < 3;
}`;

halts(funcStr, 'foo')

No, halts should return true, because the following program will halt:

function P(s) {
  return s.length < 3;
}
P('foo')

(Yes, this program returns false, but halts does not care what value it returns, it just cares whether it returns anything at all.)

One more test case: what should the following program do?

const funcStr = `function (s) {
  while (true);
}`;

halts(funcStr, 'foo')

Indeed, the program will never halt, so halts should return false.

No, halts should actually return false, because the following program never halts:

function P(s) {
  while (true);
}
P('foo')

No: halts should always halt, returning either true or false. In this case, the program it’s analyzing does not halt, so it should return false.

How would you implement halts(funcStr, arg)? You might first parse the funcStr as JavaScript: if it does not parse, you can return true. Then if the program has no loops, you can return true. If the program starts with while(true){}, you can return false. You could even run the program for a while with eval, and if it halts, then you can return true.

But is it enough to just do all the checks we can think of? What we really need is a single, unified way to check whether any program halts.

Turing’s devilish g function 😈

Sadly, Alan Turing burst this balloon in 1936, by showing that however you write halts, it will always have a bug! Turing’s proof works by contradiction: assuming you have written a correct version of halts, we can find an input for which it must be wrong!

So let’s assume you’ve written a correct halts. Turing then defines a devilish function, g, which looks like this:

function g (funcStr) {
  // Embed our `halts` implementation
  function halts(f,a) { /* ... */ }

  if (halts(funcStr, funcStr)) {
    while (true) { }  // loop forever
  } else {
    return;  // halt
  }
}

Turing’s function g looks bizarre! It asks halts what a function would do when given its own source code. Then g inverts the answer: if halts says that the program would halt, then g does not halt; but if halts says that the program would not halt, then g halts.

Let’s work through some examples. What will the following do?

const funcStr = `function (s) {
  return true;
}`;
g(funcStr)

No, g actually would loop forever. It first consults halts, which tells us whether this strange program halts:

function P(s) {
  return true;
}
P(`function P(s) {
  return true;
}`)

Try it for yourself: the above evaluates to true. That is, it halts. So halts must return true. Because of this, g then goes into an infinite loop.

Right! The program halts when run on its own source code, so g decides to loop forever.

Let’s try another one. What would the following do?

const funcStr = `function (s) {
  while (true) { }
}`;
g(funcStr)

Right: the function described by funcStr loops forever, so g will return false.

No, g will actually halt, because the following program loops forever:

function P(s) {
  while (true) { }
}
P(`function (s) {
  while (true) { }
}`)

The function g, like any other JavaScript value, can be encoded as a string:

const gStr = `function (funcStr) {
  // Embed our `halts` implementation
  function halts(f,a) { /* ... */ }

  if (halts(funcStr, funcStr)) {
    loop();
  } else {
    return;
  }
}`;

Now a crazy thought: what happens if we run g(gStr)? That is, what happens when we call g on its own source code? Luckily, we have our magic halts function to answer that question: we just run halts(gStr, gStr)!

Now, halts(gStr, gStr) either returns true or returns false. And it turns out that, in either case, we get a strange contradiction ...

Let’s first assume halts(gStr, gStr) returns true. By doing so, what is halts claiming that g(gStr) will do?

Remember the meaning of halts(funcStr, arg): it tells us whether the function whose source code is funcStr would halt when given argument arg. So if halts(gStr, gStr) returns true, it’s saying that g(gStr) halts.

Now read the definition of g: what would g(gStr) actually do?

Actually, g would loop forever! The first thing g(gStr) does is query halts(gStr, gStr). We’ve assumed that this returns true. In this case, g maliciously loops forever.

So if halts(gStr, gStr) returns true, it would be wrong! Not so bad perhaps: surely halts(gStr, gStr) must return false, then?

Let’s try it. Now assume halts(gStr, gStr) returns false. Then halts is claiming that g(gStr) will not halt. But now read the definition of g: assuming halts(gStr, gStr) returns false, what would g(gStr) actually do?

Actually, it would halt. The first thing g(gStr) does is query halts(gStr, gStr). We’ve assumed that this returns false. In this case, g maliciously halts instead of looping forever.

Right, it would halt.

Again, halts is wrong: it claimed that g(gStr) would not halt, but upon inspection, it clearly would halt! Whatever halts claims g will do, g maliciously does the opposite!

This proves that our implementation of halts has at least one bug: it gives the wrong answer for the input g.

But does this really show we can never write a correct halts? Can’t we just fix this one bug? Let’s try defining a halts_v2 that just patches over this bug:

function halts_v2(funcStr, arg) {
  if (funcStr === gStr && arg === gStr) {
    return !halts(funcStr, arg);
  }

  return halts(funcStr, arg);
}

Does halts_v2 have a bug?

Actually, halts_v2 has a bug too, and we can show it in exactly the same way we did for halts! We define a new g_v2 that uses halts_v2, in exactly the same way we did for the original halts:

function g_v2 (funcStr) {
  // Embed our `halts_v2` implementation
  function halts_v2(f,a) { /* ... */ }

  if (halts_v2(funcStr, funcStr)) {
    while (true) { }  // loop forever
  } else {
    return;  // halt
  }
}

Using the same reasoning as before, we can conclude that halts_v2 gives the wrong answer to the input g_v2Str.

Right! We can show halts_v2 has a bug in exactly the same way, by defining a new g_v2 that uses halts_v2.

The point is: whatever implementation of halts you provide, we can write a version of g that proves it has a bug! This is ‘the halting problem’: the original task was unsolvable!