# 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!