I bet you I can tell if a JavaScript program runs forever.

Published in

The Startup

7 min readApr 10, 2020

A friendly bet

Imagine that you have a friend called Callback Cat with whom you study JavaScript every day.

You and Callback Cat spend your time happily navigating the world of NPMs, Closures and Promises, helping each other make sense of it all.

One day, Callback Cat burst out a claim that they can tell if any JavaScript program runs forever just by looking at the code long enough.

Would you believe them?

Let’s say that they want to bet your favorite pizza on it. Which code would you give them to prove them wrong?

Try and think of a solution at this point. Hint: there’re many ;)

How about we make the outcome of the code entirely dependent on its inputs?

Determining if imReadyForPizza runs forever depends entirely on the value of x. It’s impossible to know if the code runs forever without knowing x. If we run imReadyForPizza(3) then it will run forever, otherwise it won’t.

Gotcha Callback Cat!

A sneaky twist

At this point, Callback Cat conveniently realizes that they forgot an important detail.

“Oops, I forgot something, silly me. What I meant to say is that I can tell if any JavaScript program runs forever by looking at the code and the input.”

Hmmm, sneaky Callback Cat, trying to win a free pizza.

Yet you still decide to humor them for the sake of the thought experiment. Being good friends that you are, you’ll share the pizza with each other no matter who loses the bet and ends up buying it.

What code would you give Callback Cat this time? Don’t forget, now you also have to give them the input to the code.

Not as easy right?

Maybe we can try a different approach here.

Callback Cat’s Claim in Code

For the sake of argument, let’s assume that Callback Cat can, indeed, tell if a piece of code runs forever or not, for any given input.

One way to express their claim would be with the following code:

if code(input) eventually terminates, Callback Cat will say 'TERMINATES'
if code(input) runs forever, Callback Cat will say 'RUNS_FOREVER'

Don’t worry right now about what’s inside of eventuallyTerminates, we’re assuming that it just works for now.

Debunking Callback Cat’s Claim

Now let’s create a couple of plain old JavaScript helper functions to test out callbackCatsClaim.

The first helper we’ll need is called actOut. It takes in the result of callbackCatsClaim as input and, well, acts it out.

actOut('RUNS_FOREVER') will make actOut run forever.
actOut('TERMINATES') will make actOut terminate.

The second helper we’ll use is a bit naughty. It receives the result of callbackCatsClaim and lies about it.

Now let’s go back to Callback Cat’s claim.

Remember, it’s supposed to work for any code and any input.

That means that, technically, we can use callbackCatsClaim to tell if a program runs forever when given its own source code as input.

willRunForeverOnSelf(code) will return 'TERMINATES' if code(code) at some point terminates.
willRunForeverOnSelf(code) will return 'RUNS_FOREVER' if code(code) runs forever.

Note: Don’t worry, this will all make sense soon. Stay with me :)

Let’s now combine our helpers into a function called actOutOpposite that takes in a piece of code, passes it itself as input, and then does the opposite of it, eventual-termination-wise.

if Callback Cat tells us that code(code) at some point terminates, then actOutOpposite(code) will run forever.
if Callback Cat tells us that code(code) runs forever, then actOutOpposite(code) will at some point terminate.

In other words, actOutOpposite(code) does the exact opposite of what code(code) does.

What happens when we run actOutOpposite(actOutOpposite)?

Let’s repeat what we know one more time.

We know that actOutOpposite(code) does the exact opposite of what code(code) does.

We want to know what happens when we run actOutOpposite(actOutOpposite).

Well, if we pass in actOutOpposite as code, it means that actOutOpposite(actOutOpposite) does the exact opposite of what actOutOpposite(actOutOpposite) does?

Oh oh.

Looks like we found a corner case for which, no matter what Callback Cat says happens (the code terminates or doesn’t), the opposite will happen.

The Halting Problem

Callback Cat’s claim would actually be a solution to a famous problem in Computer Science called the halting problem.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever

One of the main reasons the halting problem is as famous as it is is because it is one of the first problems that were shown to be impossible to solve.

Note: The approach that we‘ve used above to show that callbackCatsClaim does not work is called a proof by contradiction, and is a common way to demonstrate that the halting problem cannot be solved.

The halting problem is part of a group of unsolvable problems in CS that are called “undecidable”. An undecidable problem is one for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. In other words, sometimes we just don’t know the answer.

This means that, although callbackCatsClaim has a perfectly well-defined, deterministic value for every individual program and input, we can't write a program that can decide it for every program/input pair.

Why does it matter?

The discovery of the halting problem was revolutionary because it showed us that some problems just cannot be solved. Some solutions are impossible to generalize for all scenarios.

This is important because the halting problem isn’t the only one of its kind.

Equipped with the realization that undecidable problems exist, you can learn how to recognize them and save yourself from going on a wild goose chase, wasting time or resources.

In fact, undecidable problems are all around us.

Let’s take basketball for instance.

Could you tell me, with absolute certainty, if the Golden State Warriors will never win the NBA title again?

If you think they definitely will, can you write a program to tell me exactly after how many seasons?

Perhaps you could write a program that takes in any possible NBA roster as its arguments, and outputs which year that roster would win the NBA title?

All of these problems are just the halting problem in disguise.

In general, if a problem you’re dealing with requires you to know, generalized across an infinite set of cases, when something specific will happen, or if it will ever happen, you’re likely dealing with the halting problem.

No matter how much computing resources we poses, some problems will never be solvable in a generalized manner. Some computer programs will always have an edge case that won’t be covered.

Writing a program to decide if a given player in a game you’re building will ever reach 100,000 points? The halting problem.

Writing a program to decide when will any given UI spinner stop spinning? The halting problem.

Writing a program to decide if a compiler always produces the fastest resulting code from a given source code? The halting problem.

Lucky for us though, an approximate solution is many times more than enough in practice.

If you knew the exact roster of an NBA team, their age, physique, etc, you could probably arrive at a good estimation of when they would win the title.

In fact, we can even solve the halting problem for many cases.

One common, approximate, and practically efficient solution to the halting problem is to just use a timeout. If a program you’re testing doesn’t terminate within some (generous) time limit, then it’s ok to assume it likely never will.

Pizza time

It is true that, with enough effort and time, most problems can be solved.

Most of the time, if we try hard enough, we’ll eventually get to a solution.

Yet for those few times where that’s impossible, the most effective solution is to recognize that there isn’t one.

Recognizing when a problem is the halting problem in disguise will save time and resources. Sometimes the best program is the one that is fast, efficient, but fails in some corner cases.

Well, well. Looks like Callback Cat got a little ahead of themselves.

“Ok my friend, Callback Cat admits defeat. Time for some well-deserved pizza.”