Turing Machines and the Halting Problem

Code along video

Learning objectives

In the previous code along, we saw that self-reference creates paradoxes in logic, art, and set theory, and that programs, which are just strings, can refer to themselves too. In this final code along of the chapter, we meet Alan Turing’s 1936 model of a computer, the Turing machine, and build a four-state Turing machine that adds two numbers. We then state the halting problem (the magic autograder that would tell us whether a program ever stops) and follow Turing’s proof by contradiction that no program can solve it. We close with Rice’s theorem and why this nearly century-old theory matters as much as ever in the era of AI.

Code along summary

Setup

This code along is conceptual, with no programs to run. If you like, have a pencil and paper handy to trace the Turing machine.

Enter Turing

Alan Turing thought that computer science is not tremendously different from mathematics, and he wondered whether he could take Gödel’s work and give computing its own existential crisis, before anything resembling a modern computer even existed. That was the genius of what he did. He noticed that we are never going to escape a certain formulation of a computer. Even if we fast-forward a hundred years, to a point where computers seem very intelligent, everything they do is still a collection of operations on ones and zeros, and that places limitations on what they can do.

Turing’s goal was to take the concept of a computer and abstract away the simplest imaginable representation of it. In this chapter, our computer has had a CPU with registers, trading values back and forth with RAM. You might have thought that X-Toy is a really simple machine, but Turing’s 1936 formulation of a computer is even simpler.

The Turing machine

A Turing machine has an infinitely long tape of cells, each of which holds 0 or 1. (Some formulations also allow a blank cell, but in the simplest one, cells are 0 or 1.) Turing literally imagined an analog machine with a head, like a camera, that moves left and right along the tape. At any point in time, the head sees only the current cell; it can read the value there and overwrite it.

The key point is that the head has an internal state, which takes one of finitely many possible values (think of them as colors, or as letters A, B, C, and so on), including a special state called HALT. In a deterministic Turing machine, whenever the machine is in a given state and sees a given value, it always takes the same action, as if it were looking up a guide. For example, “in state C, if you see a 0, overwrite it with a 1, move one cell to the right, and enter state X.” Then, “in state X, if you see a 1, keep the 1, move left, and enter state Q.” And so on.

This is an immensely simple formulation of a computer, and yet anything that your computer can do can be implemented by a Turing machine. You watching this video could be implemented on a Turing machine. How on earth could anyone prove such a thing? Everything that a computer does is ultimately the result of many simple building block operations, which is the intuition that we have tried to build in this chapter by writing GCD algorithms with a handful of X-Toy instructions. If all of those building blocks can be implemented on a Turing machine, then so can everything built from them.

A Turing machine that adds

We have seen binary, decimal, and hexadecimal notation; here is caveman notation, or unary numbers, which are tally marks. The number 1 is 1, 2 is 11, 3 is 111, and 17 is seventeen 1s. Any positive integer can be represented this way.

Exercise: an addition Turing machine

Here is one solution, which shows that a single X-Toy operation, addition, can be performed on a simple Turing machine. We assume that the head starts at the first digit of the first number x, that there is some number of zeros between x and the second number y, and that both numbers are positive. The idea is to move the 1s that make up y over to the left, one at a time, until they sit right next to x. The machine has four states, and even though the machine takes only simple actions, we give each state a descriptive name.

State	If it sees a 0	If it sees a 1
A: “Start”	Write 1, move right, enter B	Keep 1, move right, stay in A
B: “Move right until we hit y“	Write 0, move right, stay in B	Write 0, move right, enter C
C: “Are we done?”	HALT	Keep 1, move left, enter D
D: “We aren’t done, so loop back toward x“	Write 0, move left, stay in D	Keep 1, move right, enter A

Let us trace it with x = 3 and y = 4. In state A, the head sees a 1, keeps it, and moves right, staying in A; it does this for each 1 in x. (That took three steps here, but it could take 150 million.) Eventually it reaches the first 0 after x, writes a 1 there, moves right, and enters state B. In state B, it moves right over zeros until it hits the first 1 of y, which it crosses off by writing a 0, then moves right and enters state C. So far, we have replaced a 0 at the end of x with a 1, and a 1 in y with a 0.

State C asks whether we are done. If the head sees a 1, there are digits of y left, so it keeps the 1, moves left, and enters state D, which walks left over zeros until it sees a 1 at the right edge of x. Then it moves right and enters state A again. Notice that many states just stay inside themselves until they see something different, and that we have built a loop: while there are digits left in y, we cycle through the states A, B, C, and D. On the last pass, when state C sees a 0, every digit of y has been used, and the machine halts.

start:  0 0 1 1 1 0 0 0 1 1 1 1 0 0
halt:   0 0 1 1 1 1 1 1 1 0 0 0 0 0

We started with three 1s on one side of the tape and four on the other, and now we have seven 1s in a row, with every other cell equal to 0. (We could add a couple more states to walk the head back to the start, but that would not require much.) We have represented addition on a Turing machine with just four states, which is pretty cool.

In turn, every building block operation that a computer performs can be done on a Turing machine. The Church-Turing hypothesis goes further: anything that any machine could ever compute is computable by a Turing machine. That has never been disproven. Even the most powerful AI systems have never freed themselves from operations performed behind the scenes as ones and zeros, and so they have never freed themselves from Turing machines. The hypothesis is very strong, because it is not just about your laptop or your phone (that much has been established mathematically). It claims that any computer that anyone might come up with, even in a million years, could ultimately be replicated by a Turing machine.

The halting problem

If everything a computer can do can be done by a Turing machine, and a Turing machine is just ones and zeros, then there must be problems that computers cannot solve. To find one, we focus on problems with a binary answer. A decision problem is a computational problem whose output is either yes or no (true or false, one or zero, light switch on or light switch off). For example, “Is this integer prime?” is a decision problem.

Here is another decision problem, called the halting problem. Its input is a Turing machine together with the initial contents of its tape. Its output is yes if running the machine on that tape reaches the HALT state in a finite number of steps, and no if the machine gets stuck in an infinite process that never halts.

Notice how similar this is to our original question: does my code stop? Because Turing machines are equivalent to everything that your computer does, the halting problem is equivalent to asking, given a function f and an input x, whether running f(x) ever stops. That is the problem that we care about, and that we would love to solve with an autograder. We are looking for a function terminates(f, x) that returns true if f halts on input x in a finite amount of time, and false otherwise.

Notice that both inputs are text files. We have tried to change your brain a little to think of a program as a string, which it is, so terminates takes two strings as input and returns a Boolean value.

def terminates(f: str, x: str) -> bool:
    """
    Takes the source code of a program f and an input x, both as strings.
    Returns True if running f on x halts in a finite number of steps,
    and False if it runs forever.
    """
    ...

One idea is to just run the code: call f(x), start a stopwatch, and see whether it finishes. But this idea is flawed. Even if we wait a million years, the code could be so inefficient that it is just about to stop a minute later. There is no amount of time that we could wait and be 100% sure that a running program is not about to halt, so running the code is no different from you staring at the window, wondering whether you need to stop it.

These days, there is another answer: use AI. Computers are smarter than us now anyway, so we could train one with some fancy approach to read program code and analyze whether it has a flaw. These tools have gotten very good at certain kinds of analysis; if your main starts with a while True that does nothing, it will certainly notice that the program loops forever. As AI gets better and better at this kind of meta-analysis, we might feel very confident about it. And yet in 1936, Turing showed that this magic autograder is not something that any computer can build.

Proof by contradiction: paradox(paradox)

Theorem (Turing, 1936): There is no program that solves the halting problem. To prove this, we will use a proof by contradiction. We assume that the wonderful, beautiful autograder terminates(f, x) exists, and we show that this assumption leads to nonsense. If terminates exists, then we can write the following function, which takes a program z as input. Its name should make you suspect that we are about to trick you.

def paradox(z: str) -> None:
    while True:
        if terminates(z, z) == False:
            return

Even after everything that we have learned, a three-line program can be really challenging. The key is terminates(z, z). This is where quines and self-referential X-Toy programs come in: a program is a string, and its input is a string, so we can plug a program’s own source code into itself as input. Most programs are not very interesting when we do that, but it is at least possible (and Turing went to great lengths to show that it is). When we run z on its own source code, it either halts or it does not.

If z(z) does not halt, then terminates(z, z) is false, so paradox ends. If z(z) does halt, then the if statement is never satisfied, and paradox loops forever. In other words, paradox(z) halts exactly when z(z) does not halt, and it runs forever exactly when z(z) halts.

Let us set z equal to paradox and replace every z in our conclusion with paradox. We find that paradox(paradox) halts exactly when paradox(paradox) does not halt, and that it runs forever exactly when it halts. If it halts, then terminates(paradox, paradox) must be false, which means that it does not halt; if it does not halt, then terminates(paradox, paradox) must be true, which means that it does halt.

We are right back where we started with the liar paradox: if one direction is true, then it must be false, and if it is false, then it must be true. The only assumption that we made was that terminates exists, so that assumption must be wrong. Computers seem like immensely powerful machines that can solve any problem we pose to them, and yet they fall into the same traps as the Droste museum, Russell’s paradox, and the liar paradox, all of which arise from self-reference.

Rice’s theorem, and “Hey AI, are you safe?”

In every generation, someone says that theory does not matter. Look at what computers can do for us! The halting problem proof seems like nothing more than weird self-reference that we can shove into a corner. In one Stack Exchange post making exactly this argument, a respondent pointed out why we still need to study theory: many practical problems do not look like the halting problem, but they are the halting problem in disguise. If you could solve one of them, you could solve the halting problem, which means that you cannot solve them.

For example, say that we want to convert a program into the fastest possible machine code. This matters for Python, which presents us with a beautiful interface but whose conversion to machine code is often slow. Finding the optimal machine code for any program turns out to contain the halting problem, as do many questions about security and antivirus software. Each of these is a meta-question about programs, and it winds up being the halting problem.

Here is a small, made-up example of a problem with a yes or no answer: are two functions the same? The input is two functions, and the output is yes if they always give the same output on the same input, and no otherwise. Consider the following two Python functions, where f and x are some fixed function and input.

def h(y: str) -> int:
    f(x)
    return 1


def g(y: str) -> int:
    return 1

The function h does not seem to do anything interesting: it calls f(x) and returns 1. But it only returns if f(x) does not run forever. If f(x) takes a billion years, then h eventually returns 1, no matter what string we give it. Meanwhile, g always returns 1. So h and g are equivalent exactly when f(x) halts. We have hotwired the halting problem into a question about equivalent functions, which means that no program can decide in general whether two functions are the same.

There is a general version of this idea called Rice’s theorem. It says that any nontrivial question about what programs do (a meta-question that we ask computers to answer about programs, including about themselves) is undecidable: there is no program that answers it correctly in general. There may be solutions in certain categories or special cases, but there is no general answer.

Why does that matter as much today as it ever has? Because one of those questions is “Hey AI, are you safe?” That question is inherently connected to the foundational theoretical work that Turing did nearly a hundred years ago. Self-reference broke logic. It broke set theory. It broke mathematics. It broke computer science. And meanwhile, we are hurtling at breakneck speed toward self-reference becoming more and more pressing, with machines that are getting very close to learning how to say the word “I” and mean it.

What is going to happen? Nobody can pretend to know. But students love to see computers make and build things, and so do we, and it is hard to convey how beautiful the work of Turing, Gödel, and Escher is unless you get your hands dirty with it. This material is as important as it has ever been.

Looking ahead

This is the last code along of Chapter 7, and it brings us full circle: from the ones and zeros inside the machine, through assembly language programs that compute GCDs, to the limits of what any machine can ever compute. Thank you for coming along on the journey. To keep practicing, try the Chapter 7 practice exercises, in which we implement another ancient algorithm, the sieve of Eratosthenes, in X-Toy.