The halting problem
An interactive tutorial
Perhaps your code editor has warned you before: “Unreachable code detected!” But how does it know? And will it warn you about all lines that are unreachable? Back in 1936, before computers really existed, Alan Turing was already thinking about this problem. In this chapter, you’ll learn the most important result in computability theory: Turing’s trick to troll any termination test!
What is ‘halting’?
In this lesson, we’ll write programs in JavaScript. Here are three programs. Which one never halts, i.e. never prints "done"?
// Program A
console.log('done');// Program B
let s = 'hi';
for (let i = 0; i < s.length; i++) {
s = s + '!';
}
console.log('done');// Program C
let s = 'hi';
while (s !== '') { s = ''; }
console.log('done');No, program A prints 'done', then halts.
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! Program B loops forever adding exclamation marks to s.
No, Program C does halt. It enters the while loop once, which sets s to the empty string, after which the test s !== '' fails, then the program halts.
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!
So the last line of Program B will never be reached. But if you paste Program B into your code editor, you won’t get a warning saying “Unreachable code detected!” A while ago someone offered $1000 for a developer to fix this bug once and for all. What do you think — would you take the contract?
Okay! In this chapter, you’ll learn whether that was a wise choice.
Brave! In this chapter, you’ll learn whether that was a wise choice.
The halts function
For your code editor to detect all unreachable code, it would need a function called halts that takes some code as input, and returns true or false to say whether it finishes running. More precisely, we want a JavaScript function like this:
function halts (code: string) {
// Would the string `code` halt
// when evaluated as JavaScript?
// Insert clever analysis here!
return wouldHalt;
}Let’s write a test for halts. What should the following do?
halts(`
let i = 1;
while (i !== 10) i += 2;
console.log(i);
`)No, it should actually return false, because the following program loops forever:
let i = 1;
while (i !== 10) i += 2;
console.log(i);(Notice that the values of i go 1, 3, 7, 9, 11, ... and never hit 10.)
Right! The program passed in never halts, because the values of i never hit 10, so halts returns false.
No, not quite. Perhaps you were saying that the following program never halts:
let i = 1;
while (i !== 10) i += 2;
console.log(i);If so, you’d be right! (Because the values of i go 1, 3, 7, 9, 11, ... and never hit 10.)
However, the halts function should always halt on every input. If the program passed in will halt, it should return true, and if the program passed in would not halt, it should return false.
Implementing halts
How would you implement halts(code)? You could first try to parse the code as JavaScript: if it’s not valid JavaScript, you can return true (it would immediately crash). Then if the program has no loops or recursion, you should return ...
No, you should return true, because a program without loops or recursion is a finite sequence of statements. If you find a way around this, email me!
And if the program starts with while(true){}, you should return ...
No, you should return false, because while(true){} never halts, so the whole program will never halt.
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.
Paradoxical self-reference
Alan Turing was thinking about this back in 1936, and came up with the surprising answer: whatever version of halts you write, it will always have a bug!
Here’s a strange starting point: consider the sentence “this sentence is false”. Is that sentence true or false?
Well, if “this sentence is false” is true, then you should believe what it says: it’s false! And vice versa. No, I think the most reasonable answer is that it’s neither true nor false.
Well, if “this sentence is false” is false, then you should believe the opposite of what it says: that the sentence is true! And vice versa. No, I think the most reasonable answer is that it’s neither true nor false.
I think so too!
It’s weird, isn’t it? This sentence is confusing because it’s able to refer to itself. There are many other paradoxes like this. The insight underlying Turing’s proof, and many other many interesting theorems, is that self-reference often leads to weird paradoxes.
There are hints of self-reference in the description of halts: it’s a program that reasons about programs. So Turing starts thinking ... what would halts say if we asked it whether halts halts?
The haltsOn function
However, we can’t just ask whether halts halts. It’s a function, so we must ask whether it halts on a particular input. So we need to change the problem a bit: rather than seeking a function halts(code), we’re going to seek a function haltsOn(funcStr, argStr). It should tell us whether the function would halt when given a specific argument.
Let’s write some tests for haltsOn. Here’s one:
const isSmallNum = `function (n) {
return n < 3;
}`;
haltsOn(isSmallNum, '2')I’m glad you asked! It’s for the same reason that code and funcStr are strings: we’re giving haltsOn raw source code access, so we pass it the JavaScript string representation of the argument.
Anyway, I’ll give you this one for free: haltsOn should return true, because the following program will halt:
const f = function (n) {
return n < 3;
};
f(2);Now it’s your turn: what should the following program do?
const funcStr = `function (s) {
while (s === "foo") { }
}`;
haltsOn(funcStr, '"foo"')Indeed, the following program will never halt, so haltsOn should return false:
const f = function (s) {
while (s === "foo") { }
};
f("foo");No, haltsOn should actually return false, because the following program never halts:
const f = function (s) {
while (s === "foo") { }
};
f("foo");No: haltsOn should always halt, returning either true or false. In this case, the program it’s analyzing is:
const f = function (s) {
while (s === "foo") { }
};
f("foo");This program does not halt, so haltsOn should return false.
Self-reflecting functions 🪞
Anyway, Turing was thinking about functions that can look at their own source code. Here’s an innocent function that, given a string, extracts the first number in it:
function firstNumberIn(str: string) {
return /d+/.exec(str)[0];
}For example, firstNumberIn("testing 1 2 3") would return "1". But what would firstNumberIn return when given its own source code?
Similarly, we can ask whether functions will halt when given their own source code. Try this one out:
function (s) {
if (s.includes("froot")) {
while (true);
}
}What does this function do when given its own source code?
It actually loops forever. This strange function checks whether its input contains the string "froot", and if so, it loops forever. Now check the function’s source code: it contains the string "froot" in the second line. So this function would loop when given its own source code!
(You could actually replace "froot" with any other string, and it would still loop when given its own source code. That should be a hint that things are getting weird.)
But we don’t have to analyze this ourselves: we can just ask haltsOn! Here’s how:
function haltsOnSelf(funcStr: string) {
return haltsOn(
funcStr,
JSON.stringify(funcStr)
);
}(Notice the JSON.stringify. Without this, we would not be passing the source code to the function; we would be passing a literal function as the argument.)
Here’s an example:
haltsOnSelf(`function (s) {
while (s.length > 1000) { }
}`)What should the above return?
Right! The function’s source code is much shorter than 1000 characters, so it never enters the loop.
No, it should return true. The function loops forever if its input string has more than 1000 characters. But its own source code is much shorter than that, so it halts immediately. Therefore, haltsOnSelf must return true.
Turing’s troll function 👺
This is getting very loopy, isn’t it? Stay strapped in, because there’s one more level of loopiness to come! Turing now defines a devilish function, troll, which looks like this:
function troll(funcStr: string) {
if (haltsOnSelf(funcStr)) {
while (true) { }
}
}Turing’s troll function looks bizarre! Given a funcStr, it either halts or loops forever. To decide, the troll asks haltsOnSelf what the function would do when given its own source code, and then the troll does the opposite! That is, if funcStr would halt on its own source code, then troll does not halt; but if funcStr would not halt on its own source code, then troll halts.
Let’s work through some examples. What will the following do?
troll(`function (s) {
return true;
}`)No, troll actually would loop forever! It first consults haltsOnSelf, which tells us whether this strange program halts:
const f = function (s) {
return true;
};
f(`function (s) {
return true;
}`);Try it for yourself: the above program halts. Because of this, troll then goes into an infinite loop.
Right! The program halts when run on its own source code, so troll decides to loop forever.
Let’s try another one. What would the following do?
troll(`function (s) {
while (true) { }
}`)Right: the function passed in loops forever, so troll will halt.
No, troll will actually halt, because the following program loops forever:
const f = function (s) {
while (true) { }
};
f(`function (s) {
while (true) { }
}`);Trolling the troll 👺🪞
Now, the function troll, like any other JavaScript value, can be encoded as a string:
const trollStr = `function (funcStr) {
if (haltsOnSelf(funcStr)) {
while (true) { }
}
}`;Now comes Turing’s truly crazy thought: what happens when we call troll on its own source code? That is, what happens if we run troll(trollStr)? Luckily, we can answer that: just run haltsOnSelf(trollStr)!
Now, haltsOnSelf(trollStr) is either true or false. And it turns out that, in either case, we get a strange contradiction ...
If the troll halts on its own code ...
Let’s first assume haltsOnSelf(trollStr) returns true. Then what is halts claiming that troll(trollStr) will do?
Remember the meaning of haltsOnSelf(funcStr): it tells us whether the function would halt when given its own source code. So if haltsOnSelf(trollStr) returns true, it’s saying that troll(trollStr) halts.
Now read the definition of troll: what would troll(trollStr) actually do?
Actually, troll would loop forever! The first thing troll(trollStr) does is query haltsOnSelf(trollStr). We’ve assumed that this returns true. In this case, troll maliciously loops forever!
So if haltsOnSelf(trollStr) returns true, it would be wrong!
If the troll does not halt on its own code ...
Not so bad perhaps: surely haltsOnSelf(trollStr) must return false, then?
Let’s try it. Now assume haltsOnSelf(trollStr) returns false. Then halts is claiming that troll(trollStr) will not halt.
But now read the definition of troll: if haltsOnSelf(trollStr) returns false, what would troll(trollStr) actually do?
Actually, it would halt. The first thing troll(trollStr) does is query haltsOnSelf(trollStr). We’ve assumed that this returns false. In this case, troll maliciously halts instead of looping forever!
Right, it would halt.
Again, haltsOnSelf is wrong: it claimed that troll(trollStr) would not halt, but upon inspection, it clearly would halt! Whatever haltsOnSelf claims troll will do, troll maliciously does the opposite!
So, our haltsOnSelf has a bug: it gives the wrong answer for the input trollStr. But where is the bug, exactly? Turing’s says: the bug is in the haltsOn function that we assumed the existence of.
Whatever version of haltsOn we’re given, we can show that it has a bug. That is, there is no function that correctly solves the halting problem!
Equivalence of halts and haltsOn
We originally asked for a function halts, rather than haltsOn. But it turns out that they’re equivalent. If we assume that we have a correct halts, then we can write a correct haltsOn like so:
function haltsOn(funcStr, argStr) {
return halts(`
const f = ${funcStr};
f(${argStr});
`);
}This shows that halts is not possible either, because it would lead to a correct haltsOn, which we just saw is not possible.
But note that you could actually define them the other way around! Here’s an exercise: assuming you have haltsOn, write an implementation of halts.
Great! Perhaps your implementation looked like this:
No worries. Here’s a possible implementation:
function halts(code: string) {
return haltsOn(
// Ignore argument, just run code
`function(_) { ${code} }`,
// Can be anything - it's ignored!
'0'
);
}So, halts and haltsOn have equivalent power. For this reason, you’ll often see authors casually jump between one and the other.
Can we patch the bug? 🐛
You might be wondering: can’t we just fix patch the bug in haltsOn? Let’s try defining a haltsOn_v2 that just patches over this bug:
function haltsOn_v2(funcStr, argStr) {
if (funcStr === trollStr &&
argStr === JSON.stringify(trollStr)) {
// Patch over the bug!
return !haltsOn(funcStr, argStr);
}
// Otherwise it's probably right?
return haltsOn(funcStr, argStr);
}Does haltsOn_v2 have a bug?
Actually, haltsOn_v2 has a bug too, and we can show it in exactly the same way we did for haltsOn! We define a new troll_v2 that uses haltsOn_v2, in exactly the same way we did for the original haltsOn:
function troll_v2(funcStr) {
if (haltsOn_v2(funcStr, funcStr)) {
while (true) { } // loop forever
} else {
return; // halt
}
}Using the same reasoning as before, we can conclude that haltsOn_v2 gives the wrong answer to the input troll_v2Str.
Right! We can show haltsOn_v2 has a bug in exactly the same way, by defining a new troll_v2 that uses haltsOn_v2.
Conclusion
The point is: whatever implementation of halts you provide, we can write a version of troll that proves it has a bug!
This is ‘the halting problem’. I bet you’re regretting taking that contract now! You’ll never be able to complete it. Fortunately, you can complete this chapter now.
This is ‘the halting problem’. Your instincts were good, and you were wise not to take that contract! You’d never have been able to complete it! Fortunately, you can complete this chapter now.
End notes:
Turing’s troll function is usually called g. Thanks to an anonymous reviewer for suggesting the name “troll”!