Chiang's Predictor and the Halting Problem

1-bit time travel is surprisingly powerful.

This post is adapted from some of my old writing.

Ted Chiang’s short story What’s expected of us features a “Predictor”, a device with one button and a single light which always flashes one second before you press the button (spoilers below, you should probably just read it since it’s very short).

It’s a fun idea. Each time you see the light flash, you find yourself inexplicably pressing the button one second later. The Predictor presents immutable proof of that we lack free will and it drives people mad.

In theory, the Predictor provides a way to send 1 bit of information back into the past. There are actually a lot of cool things you could do with this. For instance, if you had a Predictor with a delay of 1 week, you could use it to get rich by watching the stock price of a company and pressing the button if it goes up. That way, when the “you” from a week ago sees the light go on, they know to buy shares.

But Bill and Ted already did this stuff. More interesting is the fact that the Predictor can solve the halting problem.

The halting problem challenges us to determine if another program will eventually stop on a given input, or run forever. It’s impossible to do in general, but it’s no match for our little device.

The key is to repeat the stock market trick several times over to pass information as far as you want into the past. Then it’s just a matter of waiting to see if the program halts and passing that information back to your past self.

Let’s look at an example. Say you have a Predictor with a delay of 100 seconds. Its easy to send 1 bit of information 100 seconds back into the past; just press the button. But you can send information even further back by having your past self press the button as well! For example, each time you see the light come on, you wait 10 seconds and press the button. The timeline looks like this:

Now, the light flashing has been propagated even further back into the past.

You can repeat this process as many times as you like:

I omitted the intermediate labels for clarity

As I alluded to before, you can use this to solve the halting problem by running any program and waiting to see if it halts. If it does, push the button, and if you ever see the Predictor light up, wait 10 seconds and press the button. If the program halts, you will see the Predictor light up a few seconds after you start. But if you don’t see the predictor light up in a reasonable amount of time, then you know the program doesn’t halt.

Regardless of what you see, you can’t walk away just yet! In order for the trick to work you have to remain at your post, dutifully observing the computer and pressing the button as needed. You could be there forever if the program doesn’t halt.

In some sense, this trick doesn’t solve the halting problem for you, personally. But for an outside observer, it works just fine. You could also imagine a machine pushing the button on your behalf.

So what gives? Isn’t the halting problem logically impossible?

I think this scenario identifies the real problem with backwards time travel. The Predictor allows us to do an impossible task, so must also be impossible. Like a perpetual motion machine, the Predictor seems achievable, but possesses unlimited, unattainable power.

Tying the Predictor to the halting problem highlights the trouble with determinism. We recoil at the thought of meeting a Predictor and realizing that our choices have already been decided, but the Predictor turns that fear on its head. We can sidestep the question of free will entirely because even if we’re completely deterministic, there’s no way to be confronted with that fact without creating a loophole that lets us do the impossible. We can carry on believing in free will, as the story pleads:

My message to you is this: pretend that you have free will. It’s essential that you behave as if your decisions matter, even though you know that they don’t. The reality isn’t important: what’s important is your belief, and believing the lie is the only way to avoid a waking coma.