Writing is thinking. To write well is to think clearly. That's why it's so hard.

~ David McCullough

# The Halting Problem in Javascript

## The Specs for `Halt`

We suppose the existence of a function called `Halt`

. It takes one parameter: a function, we will call f, that takes 0 parameters. Then `Halt(f)`

returns `true`

if the call to `f()`

ever returns a value, and `Halt(f)`

returns `false`

if `f()`

loops infinitely.

An important part of this assumption is that `Halt(f)`

must always return `true`

or `false`

regardless of your choice of `f`

. It must not itself loop.

## A very small test suite

So first, let's come up with some simple functions to pass to `Halt`

. Remember, they have to take 0 parameters.

One example is the `Zero`

function:

```
function Zero()
{
return 0;
}
```

When called, `Zero`

simply returns 0. It's boring, but it's a function.

Another example is the `Loop`

function:

```
function Loop()
{
while (true)
{
// do nothing
}
return 0;
}
```

Clearly, `Loop`

gets stuck in an infinite loop. It will never return a value.

So, let's use `Halt`

.

`Halt(Zero)`

returns `true`

, because `Zero()`

returns immediately gives us a value.

`Halt(Loop)`

returns `false`

, because `Loop()`

never returns a value.

## A weird problem

So far so good. But we run into problems with certain misbehaved functions.

```
function Weird()
{
if (Halt(Weird))
{
return Loop();
}
else
{
return Zero();
}
}
```

Nevermind what use `Weird`

is to a programmer. It's a valid Javascript function. So we are allowed to pass it to `Halt`

.

So what is `Halt(Weird)`

? Think about this for a while and see how much you can figure out.

## What's wrong with `Weird`

We don't know up front, but we made a claim at the start that `Halt`

always returns either `true`

or `false`

. And so let's investigate both possibilities.

First, suppose `Halt(Weird)`

returns `true`

. When we run `Weird()`

, we get to the if statement. Since `Halt(Weird)`

returns `true`

, we take the first branch, and we wind up returning `Loop()`

. But that means `Weird()`

doesn't actually return and so `Halt(Weird)`

must have been `false`

, not `true`

! We have a contradiction.

Not a problem. We must have made the wrong choice. Instead, `Halt(Weird)`

must return `false`

. Problem solved.

Right? Maybe not. If we trace through the code, we see that instead of taking the first if branch, we take the second. But the second returns `Zero()`

. So while we assumed Halt(Weird)`was`

false`, it ended up halting after all. This alternative also gives us a contradiction.

Both of our cases ended in a contradiction. The only assumption we made was that it was possible to write a definition for the function `Halt`

with the properties we want. But the mere existence of `Halt`

allow us to construct functions that purposefully break it. There's no way around it. `Halt`

cannot be written in Javascript.

## A shout out to Self-reference

I want to point out a critical feature of the definition here. `Weird`

is defined in terms of `Halt`

. It was purposefully defined so that it could break `Halt`

and so it only makes sense that it contain some reference to it.

I won't say much more than this: self-reference is at the heart of the halting problem. While you think about that, maybe you can also consider the following paradox:

There is a Barber who lives in a particular village. His job is to shave every man in the village... but he doesn't shave men who shave themselves. Does the barber shave himself?

## Caveats

You might be thinking to yourself, "This is absurd. I can certainly tell when a function halts." You might even present an example like this one to drive home the point that this is crazy:

```
function ObviouslyHalts()
{
for (var i = 0; i < 100; i++)
{
// do nothing
}
return 0;
}
```

And sure enough, I would agree with you this function does halt. However, you have missed a subtle point about the halting problem. The game isn't to figure out if *this particular* function halts. Or that all the functions I would typically write as a programmer halt. The problem specifies that `Halt`

must work for *all* Javascript functions. And that's a much stricter requirement than to ask it work on all "reasonable" inputs.

In practice, the halting problem is solvable for a very large class of useful functions. For instance, if you banned the use of while loops and the use of recursion and required that all for loops were of the form `for (var V = 0; V < N; V++)`

with `V`

a variable and `N`

a value which doesn't change between iterations, then your program would be guaranteed to halt.

In practice, *most* software can be written in this restricted for loops styles. This hsouldn't be too surprising, since we want to make it obvious our programs don't get stuck in infinite loops.

If for loops seem too restrictive, I will say that it's possible to add back in while loops and recursion, but you need to impose elaborate restrictions on them. Each iteraton of a while loop must bring you closer and closer to failing the condition. Each recursive function call must bring you closer and closer to reaching a base case.

## Servers and the halting problem

The above story of `Halt`

is taught to every single student of computer science. Less well-known (and honestly, more recently discovered), is how this relates to long-running computer programs that are intended to run (effectively) forever.

A server is any computer program which sits around waiting to be contacted by another. When it receives an incoming request, it produces a result, sends it off, then continues waiting. On and on. Forever.

How does the halting problem deal with these sorts of programs?

One way is to say that servers simply don't halt. But this is not as satisfying as it should be. Even though a server doesn't halt, it would feel funny to say they get stuck in infinite loops. And even worse, if the server might be potentially shut down, can we even say it doesn't halts? Whether it halts or not is now a function of how it interacts with the world.

Sadly, I don't have the time to get into the full story. But I would like to at least hint at the big idea. It turns out to be useful to introduce some a new notion: productivity.

A server is able to send and receive messages from any clients that want to connect to it. A server might not halt, and frankl, we stop caring if it does or not. Instead, we ask a new question: if we send it a message, will it eventually return a response back?

If when sent a message, a server eventually comes back with a reply, say the server is productive.

In a certain sense, productivity is halting "turned inside out". Instead of taking a finite amount of time to run, it's taking a finite of time to respond.

And with this mild extension, we are able to talk about halting in regards to servers as well as ordinary functions.

## Technical details not included

I have purposefully scrubbed this article of as much technical detail as I could. Javascript is a large and semantically complicated language, and it is not well-suited for serious talk about the halting problem. However, I used it because I wanted to share the main gist of the halting problem with as many people as possible.