The Walls

One machine can now run every rulebook. That raises a natural question. Is there a rulebook for everything? Could a universal machine, given the right program, answer any well-posed question? Turing asked this too, and the answer is no, in three different ways.

“Can run any program” does not mean “can answer any question”. There are walls, and they are the same for every machine, including brains as far as anyone knows.

A note for the reader For a quicker route to the learning machines, read “What the walls mean” at the end of this chapter and continue to Chapter 4. Chapter 16 returns to these limits.

The checker that cannot exist

A hospital buys software from many suppliers: triage tools, dose calculators, scheduling systems. A careful manager has an idea. Why not write one program that inspects any other program and reports, before it is ever used, whether it will always finish? A triage tool that freezes forever at 2 a.m. would be dangerous. A checker would catch every such tool in advance.

The idea is natural, and it is impossible. Not difficult, not expensive: impossible. Turing proved it in 1936, and the proof fits in a paragraph. It is the first of three limits that bound every computation, ours included as far as anyone knows. This book calls them walls.

Wall 1: impossible

Suppose someone hands you the perfect checker. Call it Will-It-Stop. You give it any program and that program’s input, and it always answers, correctly, “stops” or “runs forever”.

Now build a mischievous program called Contrary, which uses Will-It-Stop as one of its parts. Contrary takes a program as input and does this:

1. Ask Will-It-Stop: “Will this program stop if it is given itself as input?”
2. If the answer is “stops”, run forever on purpose.
3. If the answer is “runs forever”, stop at once.

Now feed Contrary to itself. Will it stop?

• If Will-It-Stop says Contrary stops, then Contrary runs forever.
• If Will-It-Stop says Contrary runs forever, then Contrary stops.

Either way Will-It-Stop gave the wrong answer. But we assumed it was perfect. So the perfect checker cannot exist. This is the halting problem, and it is undecidable: no program can answer it correctly for every program.

Three remarks keep this in proportion.

• It is about “every”. Checkers that work on most programs people actually write exist and are useful. What cannot exist is one that never fails.
• It spreads. The same trick rules out a perfect checker for almost any question about what programs do, including “does it ever give dangerous advice?” Chapter 16 returns to this.
• It is symmetric. People cannot solve the halting problem either. If brains are machines of the ordinary kind, which is the mainstream view, this wall stands in front of us just as it stands in front of computers. It is a limit on computing, not a difference between people and machines.

Wall 2: too slow

Most questions are not like the halting problem. They can be answered. But some of them take so long that the answer might as well not exist.

Take the hospital’s night schedule. Thirty nurses, two wards, a dozen rules: nobody works three nights in a row, every ward always has a senior nurse, people’s leave requests are respected. Suppose there are a hundred yes-or-no decisions to make. Each one doubles the number of possible schedules, so there are of them, about a million million million million million. A computer that checked a billion billion schedules per second would need about forty thousand years to try them all. With two hundred decisions, it would need far longer than the age of the universe.

Notice something odd, though. Checking a proposed schedule is easy: read it once and see whether any rule is broken. Finding a good schedule is hard. Many important problems share this shape: easy to check, hard to find, like a filled-in Sudoku or a proposed proof. Is every easy-to-check problem also easy to solve? This is “P versus NP”, one of the great unsolved questions in mathematics. Almost everyone expects the answer to be no.

And yet hospitals do produce schedules. Computer programs routinely solve industrial problems of this kind with a million variables in seconds. How? Because “too slow” is about the worst case: the most awkward problem anyone could construct. Real problems are not built to be awkward. They have structure, such as rules that mostly concern the same few people, or wards that hardly interact. A good method uses that structure. Hardness in the worst case and ease in practice are different facts, and both are true.

Wall 3: no shortcut

The third wall is subtler. Some processes cannot be predicted faster than by running them.

For a planet going round the sun, there is a shortcut. You do not need to simulate every minute of the next hundred years to know where the planet will be. A formula jumps straight there. Much of science is the discovery of shortcuts like this.

But some very simple systems have none. Take a row of cells that each update by looking at their neighbors. As far as anyone knows, the pattern after a million steps can be found only by computing all million. There is nothing to skip. The system is its own fastest simulator. The physicist and computer scientist Stephen Wolfram calls this computational irreducibility.

This is not the same as chaos, where tiny errors in the starting measurements grow. An irreducible system is hard to predict even when you know its starting point and rules exactly. Even a far more intelligent system must wait and watch, or simulate it step by step. But irreducible worlds are full of pockets of reducibility, regular patterns that can be predicted. Science, and intelligence generally, lives in those pockets.

What the walls mean

The three walls do not stand on equal footing. The first is proved: no perfect checker can exist. The second rests on a famous unsolved question: almost everyone expects that some easy-to-check problems are hard to solve, but nobody has proved it. The third describes processes for which no shortcut is known, and for which none is believed to exist; that is a conjecture about particular systems, not a theorem.

Intelligence, natural or artificial, does not get around these walls. It gets around the need for a universal method. It finds the structure in the problems that actually arise: the schedule that is mostly made of separate wards, the planet that follows a formula, the program whose termination is obvious. One sentence sums it up: there is no universal method, and intelligence is the art of not needing one.

At this step, the machine is still any stored-program computer, from EDSAC to the laptop on your desk, and no program will take either of them past these walls.