What can a machine compute?

In 1928 David Hilbert posed the Entscheidungsproblem, the “decision problem”: is there a mechanical procedure that, given any mathematical statement, decides whether it can be proved? To answer “no” one first had to pin down what a mechanical procedure is, an idea nobody had defined rigorously. In 1936, aged twenty-four, Alan Turing published On Computable Numbers and gave the definition we still use.

All of artificial intelligence rests on this foundation. A language model is, in the end, a program run by a computer, and what a program can or cannot do was settled in that paper, before any computer existed.

§The Turing machine

Turing imagined a person calculating with pencil and paper and stripped away everything inessential. Four things were left:

• an infinite tape divided into cells, each holding a symbol (or blank);
• a head that reads and writes one cell at a time and moves one position left or right;
• an internal state, taken from a finite list: the “working memory” of whoever is computing;
• a table of rules that, for each pair (state, symbol read), says what to write, where to move and which state to go to.

It looks far too poor to do anything interesting. Try it in the figure: the first machine adds one to a binary number with just two states and five rules.

Turing argued that any computation a person can carry out by following explicit rules can be carried out by one of these machines. That same year Alonzo Church reached the same frontier by another route, the lambda calculus, and the two definitions were shown to be equivalent.

It is not a theorem, because “effectively calculable” is an intuitive notion rather than a formal definition. It is a thesis that no counterexample has refuted in ninety years. The lambda calculus, recursive functions, cellular automata, every programming language and neural networks with unlimited precision all compute exactly the same class of functions.

§One machine to simulate them all

The paper's second idea carried even more weight. A machine's table of rules is a finite text, so it can be written on the tape of another machine.

This is the birth of the stored-program computer: a single physical machine whose behaviour is decided by a piece of data, the program. In 1945 John von Neumann described the architecture of the EDVAC around this idea, and almost every later computer follows it. The program being data has another consequence: it can also be produced by another program, from examples. The rest of this site is about that.

§The halting problem

The figure's third machine never stops. Watching it run, that is obvious. But is there a general method that, given any machine and its input, decides whether it will eventually halt?

Proof (by diagonalization)

Suppose $H$ exists. Build a machine $D$ that, on input $⟨M⟩$, runs $H(⟨M⟩,⟨M⟩)$ and does the opposite: if $H$ says that $M$ halts when reading itself, $D$ enters an infinite loop; if $H$ says it does not halt, $D$ halts.

Now ask what $D$ does with its own description. If $D(⟨D⟩)$ halts, it is because $H$ said it does not. If it does not halt, it is because $H$ said it does. Either way $H$ is wrong, so such an $H$ cannot exist.

The argument recycles the trick Cantor used to show that the real numbers cannot be listed, and Gödel in 1931 to prove that there are unprovable arithmetic truths. The answer to the Entscheidungsproblem is “no”: there are well-posed questions that no algorithm can answer.

§Computable is not enough: the cost

Knowing that something can be computed does not say whether it can be computed in time. Complexity theory counts how many steps a machine needs as a function of the input size $n$. Problems in the class $\mathrm{P}$ are solved in polynomial time, $O(n^k)$, and those in $\mathrm{NP}$ are the ones whose solution can be checked in polynomial time. Whether $\mathrm{P}=\mathrm{NP}$ is the most famous open question in computer science.

This matters a lot for AI. Many problems we would like to solve exactly are intractable. Even training a three-neuron network to fit a dataset perfectly is NP-complete in the worst case (Blum and Rivest, 1992). Modern AI does not promise optimal solutions: it looks for good enough solutions with approximate, statistical and local-optimization methods. The next chapters are about those methods.

§1950: can machines think?

Fourteen years later Turing published “Computing Machinery and Intelligence” in the journal Mind. Instead of defining “thinking”, he proposed the imitation game: if an interrogator conversing in writing cannot tell the machine from a person, we have no grounds to deny it the intelligence we grant to people. But the most visionary part of the paper is its last section, entitled Learning Machines:

Instead of trying to produce a programme to simulate the adult mind, why not rather try to produce one which simulates the child's? If this were then subjected to an appropriate course of education one would obtain the adult brain. — A. M. Turing, “Computing Machinery and Intelligence”, 1950

Seventy years early, this is the program of LLMs: a generic system that acquires its behaviour by learning from data instead of being handed hand-written rules. But for the next thirty years the dominant plan was the opposite one: write knowledge down as rules and let the machine deduce the consequences. That is logic.

§References

1. A. M. Turing (1936). “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society, s2-42.
2. A. Church (1936). “An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics, 58(2).
3. J. von Neumann (1945). First Draft of a Report on the EDVAC.
4. A. M. Turing (1950). “Computing Machinery and Intelligence”. Mind, 59(236).
5. T. Radó (1962). “On Non-Computable Functions”. Bell System Technical Journal, 41(3).
6. A. Blum and R. L. Rivest (1992). “Training a 3-Node Neural Network is NP-Complete”. Neural Networks, 5(1).