Chapter ten

The halting problem comes for the ruminator.

In 1936, in a paper written by a quiet, slightly awkward, twenty-three year old English mathematician named Alan Turing, the human race was given a piece of bad news that it has not, in the ninety years since, fully assimilated.

The bad news, on the face of it, is a small technical result about computers, which is curious, because computers in 1936 did not exist. Turing was reasoning about an abstract machine that would not be physically built for another decade, and was reasoning about it so precisely that the entire subsequent history of computer science is, in some real sense, footnotes to what he wrote that year. The result he proved, in passing, was that there exists a question one can ask about computer programs that no computer program will ever be able to answer.

The question is, in plain English, this. Given a program, and given an input, will the program ever finish running, or will it run forever?

This is called the halting problem. The name is technical. The question is, on reflection, not technical at all. The question is: can you tell, in advance, whether a process you have started is going to end. And the answer Turing supplied, in the strictest mathematical sense, is no. There exists no procedure that can answer this question in general. The impossibility is not a limitation of present-day technology. It is not a matter of more compute, or faster processors, or smarter algorithms. The impossibility is a theorem. It will be true on the last day of the universe.

I am going to explain why, because the proof is beautiful, and because the proof is also, on inspection, the cleanest description I have ever found of what your brain does at three in the morning.

Suppose, contrary to what we are about to prove, that there exists a program called halts(P, x) which takes any program P and any input x, and returns True if P(x) would eventually halt, and False if P(x) would run forever. Suppose this program exists. We are going to derive a contradiction.

Using halts, we build a small, polite, slightly malicious program called diagonal(P). The program takes a program P, hands it to halts as both the program and the input, and then does the opposite of whatever halts says. If halts(P, P) says P(P) would halt, then diagonal(P) goes into an infinite loop. If halts(P, P) says P(P) would loop forever, then diagonal(P) immediately returns.

Now ask the dangerous question. What happens when you call diagonal(diagonal)?

You feed diagonal to itself. The first thing the program does is consult halts(diagonal, diagonal). If halts says the program would halt, then by construction diagonal loops forever. But halts just said the program would halt. So halts was wrong. If, on the other hand, halts says diagonal(diagonal) would loop forever, then by construction diagonal immediately returns and halts. So halts was wrong again.

Either answer halts gives is wrong. halts cannot exist. The supposition collapses. The theorem is proved.

I would like to draw the structure of the proof, because it is one of the most beautiful pieces of self-reference in the history of human thought, and because the picture will be useful in a moment when we apply it to the brain at three in the morning.

That is Turing's proof, almost in its entirety. It takes a single page of notation and one act of intellectual daring, which is the willingness to feed a program to itself and watch what happens. The act of self-reference is the heart of the proof. Without it, the theorem does not work. With it, the theorem is unavoidable. No program can decide, in general, whether another program will halt.

Now I want to apply this to your brain at three in the morning.

The brain at three in the morning is engaged in a specific kind of cognitive activity that, in the clinical literature, is called rumination. The word is borrowed, somewhat indelicately, from cattle. A ruminating cow is one that has eaten something, regurgitated it slightly, and is now chewing it again, partly digested, in a slow steady cycle that can continue for hours. The metaphor is unflattering. The metaphor is also, on inspection, alarmingly accurate.

The anxious mind, in rumination, takes a thought, examines it, regurgitates it slightly modified, and re-examines it. The thought is, in technical terms, a process running on the brain. The mind, at each iteration, is doing something quite particular. The mind is asking itself: will this process terminate? Will I, at some future point, reach a conclusion that settles the matter? Will the thinking, eventually, finish?

This is the halting problem. The brain is, at three in the morning, attempting to compute halts(rumination, current_thought). It is trying to predict whether its own process will terminate. It is feeding itself, recursively, to its own decision procedure. And by Turing's theorem, it cannot in general succeed. There is no procedure available to the brain that can answer this question. The brain is attempting a computation that is provably impossible.

I want to say this with some care, because it is the chapter's central claim. The exhaustion of three-in-the-morning thinking is not a moral failing. The exhaustion is not laziness, weakness, or the wrong sleep hygiene. The exhaustion is the natural consequence of attempting an unanswerable question. The brain keeps asking will this end? The brain cannot answer. The brain asks again. The brain still cannot answer. The brain does not know that the question is, in principle, unanswerable, so the brain interprets its own failure to answer as evidence that it has not yet thought hard enough. The brain redoubles its effort. The brain is now generating more material to think about, which the brain then asks will this end? about. The loop is, in a strict computer science sense, the diagonal program calling itself. The loop is, in a strict computer science sense, exactly what Turing proved cannot be resolved by any algorithm whatsoever.

The ruminator is doing computer science. The ruminator does not know they are doing computer science. The ruminator is, with all the determination they can muster, attempting to compute a function that is provably uncomputable.

Let me write the failed program out, because there is a peculiar comfort in seeing the impossibility on the page.

def halts(thought, context):
    """
    Decide whether a given thought, in a given context, will
    eventually resolve, or whether it will go on indefinitely.

    THIS FUNCTION CANNOT BE WRITTEN. Alan Turing proved so in 1936.

    The following is a polite attempt anyway, because the brain
    runs it every night around three in the morning, on the
    theory that it must be possible if only one tried hard enough.
    """
    # Try thinking about it for a bit and see if it resolves.
    resolution = think_about(thought, context, duration=300)

    if resolution is not None:
        return True

    # Nothing yet. Maybe more thinking will help.
    deeper_thought = think_about(resolution_attempt(thought),
                                 context,
                                 duration=600)

    if deeper_thought is not None:
        return True

    # Still nothing. The brain now feeds the question to itself:
    # "will this thinking ever halt?"
    return halts(thought, context)
    # ^^^ NOTICE: infinite recursion. We have just called the
    #     function we are trying to define, with the same arguments,
    #     in the hope of getting an answer it never had. This is
    #     the ruminator. This is also exactly the structure Turing
    #     proved cannot work.


def three_am_brain():
    while True:
        thought = pick_an_unresolved_thing_from_the_day()
        if halts(thought, current_context()):
            # We will never reach this branch. halts() never returns.
            sleep()
        else:
            # We will never reach this branch either.
            sleep()
        # We are still here. Have you noticed? We are still here.

The code does not run, in the strict sense, because it cannot. The function halts calls itself with the same arguments, with no base case, and on a real computer this would produce a stack overflow within milliseconds. The code does run, in the strict sense, on a particular kind of human brain, which has, for reasons evolution does not entirely explain, the property that it can recurse on itself indefinitely without the stack visibly overflowing. The brain just keeps going. It does not crash. It only feels like crashing.

The function three_am_brain is, perhaps, the most accurate piece of code I have ever written. It contains a while-true loop, an unreachable sleep call, and a final comment that just notes, plaintively, that the program is still running. If you have ever lain awake at three in the morning and noticed, with a kind of resigned despair, that you are still awake, you have been the comment. The comment is doing what the comment was designed to do, which is to register, with no power to change anything, that the loop has not yet exited.

Now I want to extract the operational consequence, because the chapter is useless without it.

The cheap version of this argument would be just stop thinking about it. The cheap version fails because it has been tried, by every anxious person who ever lived, and it does not work. Telling a ruminator to stop ruminating is precisely the move that fails, because the instruction to stop ruminating is itself a thought, and the ruminator is now ruminating about whether they are successfully not ruminating. The cheap version makes the loop deeper. The cheap version is a feature request, sent to a system that cannot, in principle, fulfill it.

The real version is different, and it is one of the most useful single ideas the book contains. The rumination cannot be resolved by more rumination. The question the rumination is trying to answer is provably unanswerable. This is not a failure of you. This is a property of the question. The rumination ends not by being resolved but by being halted from outside. Something has to enter the loop from somewhere the loop is not, and break it.

In computer science terms, this is called an external interrupt. The program is in an infinite loop. The operating system has the power to send a signal that forces the program to stop, regardless of the program's internal state. The program cannot generate this signal itself, because the signal would, by the moment of being considered, be just another thought inside the loop. The signal must come from outside.

The outside, in practice, is one of a small number of things. Falling asleep is one of them, although the brain at three in the morning is, almost by definition, the brain that is not falling asleep. Getting out of bed is another, because the physical motion of standing up, walking to another room, and doing something with your hands has the property of being an event in the world rather than a thought in the head, and the loop runs on thoughts, not events. Cold water on the face is another. Calling someone, if there is someone to call at three in the morning, is another. Writing the thought down, with a pen, on a piece of paper, is another, because the act of writing is, in computer science terms, an output, and output drains the queue. The thought, once written, has somewhere to go that is not around again.

What does not work, predictably and reliably, is more thinking. The brain is in the loop. The brain cannot exit the loop by thinking, because the thinking is the loop. The brain has to be interrupted by an event in the world. The event in the world is the only thing the loop has not been told how to anticipate. The event in the world is the operating system signal that the rumination cannot self-generate.

This is, in some quiet way, what every old piece of folk wisdom about three in the morning has been trying to tell you. Get out of bed and have a glass of water. Walk around. Read something boring. These were not, as a younger version of me believed, useless suggestions. They were the closest thing the folk tradition has to an understanding of the halting problem. They were saying, in their imprecise way, that the loop has to be interrupted from outside, and that the outside, in practice, is the kitchen, the book, the cold glass of water, or, in the worst nights, the quiet act of standing in a different room until the brain has, by sheer disorientation, dropped the thread.

I want to make one observation that the chapter has been circling, because I think it is useful to state directly.

The anxious mind has, somewhere in its construction, internalized the belief that any thought worth having is a thought worth completing. The belief is not stated. It runs in the background. It says: if I started thinking about this, I owe it to the thought to think it through to the end. Stopping mid-thought is intellectual cowardice. The responsible thing to do is to follow the thought wherever it leads, and stop only when it has been satisfactorily concluded.

This belief, in light of the halting problem, is mathematically incoherent. Not every thought has an end. Not every thought has a place where the thinking, on its own steam, will stop. Some thoughts are infinite loops, structurally, and following them to their conclusion is impossible because the conclusion does not exist. Stopping such a thought partway through is not intellectual cowardice. It is recognizing that the thought is, in technical terms, non-terminating, and that the responsible action is to send the interrupt and move on.

You are not abandoning the thought by stopping it. You are recognizing, with appropriate humility about the limits of computation, that the thought was the wrong kind of thought to expect to complete. The thought will be there tomorrow, in a different form, possibly answerable, possibly not. The thought does not need you to die of exhaustion for it. The thought, in some sense the chapter has been arguing, would prefer that you slept, because the same thought, asked at eleven the next morning after a regression-to-the-mean recovery (see Chapter 9), will often turn out to be a smaller and more tractable thought than the version that was keeping you awake. The thought, like all thoughts, looks bigger in the dark.

Chapter 11 takes the next step, into the related but distinct trap of recursive thinking without a base case. The halting problem says you cannot in general decide if a loop will end. The recursion problem in Chapter 11 is more specific: it is about the particular shape of self-referential worry in which each worry generates a smaller copy of itself, which generates a smaller copy of itself, until the stack of unfinished worries collapses under its own weight. The relationship between Chapters 10 and 11 is the relationship between, in computer science, the general unsolvability of halting and the specific case of stack overflow, and the chapter will explain why the worry that goes but what if, but what if, but what if is, in a precise technical sense, the human implementation of a function call that forgot to put in a return statement.

For now, the page closes here. The thought is a process. Not every process halts. The halting cannot, in principle, be predicted from inside the process. The interrupt has to come from outside the process. The outside, in practice, is the kitchen, the glass of water, the cold air, and the small acts of leaving the head for long enough that the head, in the meantime, quietly resets itself.