Can everything be computed?

In 1936 Alan Turing defined a precise notion of a machine following instructions, and then showed that no such machine can decide, for every machine it is shown, whether that machine goes on printing forever, or whether it ever prints a given symbol. The halting problem as now taught, whether a program eventually stops, is a close relative of these, first set out by Martin Davis in the 1950s.

The argument is a construction: assume such a decider exists, use it to build a machine that works through every machine in turn, and show that when it reaches its own description the decider can give neither verdict. The assumption collapses. It rules out an entire class of possible machines rather than reporting a failure to find one.

Many ordinary-sounding questions turn out to be undecidable too, and one theorem says how many. Rice proved in 1953 that every non-trivial question about what a program computes, as opposed to how it is written, is undecidable. Whether a program correctly computes a given function is such a question. So is whether a piece of code ever produces a given output.

The same shape appears in mathematics as Gödel’s incompleteness theorems. Any consistent formal system strong enough to describe arithmetic contains true statements it cannot prove.

A separate question is whether the behaviour of physical systems can always be simulated by a machine of this kind. The claim that every finite physical system can be simulated to any desired accuracy has been called the Deutsch-Wolfram thesis, and whether it is true is open. In 1981 Pour-El and Richards showed that the ordinary wave equation, started from computable conditions, can behave in a way no such machine computes; whether those starting conditions can occur in nature is also open.

There are results showing that particular questions about models of quantum many-body systems, such as whether one has an energy gap, are undecidable. Whether any real material is affected is open: the models are, in their authors’ words, highly artificial, and whether the result extends to more natural ones is not known.

In 2015 a paper proved that whether a model of a quantum material has an energy gap, a property that shapes much of how a material behaves, is undecidable in general. There is no algorithm that answers it for every such model.

The construction embeds a halting problem into a lattice of interacting particles, and it applies to an idealised infinite system rather than to any object on a bench.

What it establishes is that undecidability is not confined to questions about programs. It can be a property of a physical model, which is a stranger result than it first sounds.

It has been argued that human mathematicians see the truth of statements a formal system cannot prove, and therefore are not machines of this kind. Lucas put it in 1961: given any consistent machine capable of simple arithmetic, there is a formula it cannot produce as true but which we can see to be true. Penrose later made very similar claims.

The specialists have largely rejected it. The standard reply, which goes back to Putnam, is that the theorem is conditional: the truth of a system’s Gödel sentence depends on that system being consistent, so the argument needs a mind that can always tell whether an arbitrary formal theory is consistent, and that is highly implausible. Lucas and Penrose have both replied. That is not the same as the question being settled about minds. It is the argument from this theorem being settled.