Could arguments be settled the way sums are? The German philosopher and mathematician Gottfried Wilhelm Leibniz thinks so. Machines can already do sums: the French mathematician Blaise Pascal built one in 1642 that adds and subtracts, and in 1673 Leibniz showed the Royal Society in London a model of one that multiplies and divides too. It is unworthy of excellent men, he later writes, to lose hours like slaves in the labor of calculation.

On March 15, 1679, Leibniz writes out a way of counting with just two digits, 0 and 1, in which each place is worth twice the one to its right. Arithmetic in this binary system is so simple, he notes, that a machine could do it with marbles, letting them fall through holes opened for the 1s and keeping the holes for the 0s shut.

But Leibniz dreams of much more: a universal language of symbols for all our ideas, with fixed rules for calculating that would settle any question of mathematics, or any other question that doesn’t turn on facts about the world. Then, he writes a few years later, people who disagree would no more need to argue than two accountants do: they could take their pens in hand, sit down at their abacuses, and say to each other, “Let us calculate” (emphasis in the original).

Printed tables are full of mistakes. Sailors use them to find their place at sea, and astronomers, engineers, and insurers to do their sums. People called computers work the numbers out by hand. Then they’re copied and set in type, by hand too, and every step lets errors in. In 1821, the English mathematician Charles Babbage and the English astronomer John Herschel check tables that two computers have worked out for the new Astronomical Society, and they find error after error. “I wish to god these calculations had been executed by steam,” Babbage exclaims, as he later remembers it. “It is quite possible,” Herschel replies.

On June 14, 1822, Babbage tells the Society how. Most tables can be worked out by adding alone. Take the square numbers: 1, 4, 9, 16, 25. To get from one to the next, you add 3, then 5, then 7, then 9, each time 2 more than before. So the next square is 25 + 11 = 36, and the one after that 36 + 13 = 49, without multiplying at all. Gears can add, so a machine of number wheels, turned by a handle, could work out a whole table, and print it too, so that no copying error creeps in. Babbage has built a small model, and he shows it working out the table of x² + x + 41, a formula whose first 40 results are all prime numbers.

The British government agrees to pay for a full-size Difference Engine, as Babbage calls it, and grants him GBP 1,500 in 1823, about USD 350,000 in today’s money. With the engineer Joseph Clement, he sets out to build it: some 25,000 parts, weighing about four tons.

The Difference Engine is never finished. In 1833, Babbage and Clement fall out over money, and Clement stops work and dismisses his workmen. All that’s ever assembled is a demonstration piece, about a seventh of the engine, which works out tables flawlessly before amazed visitors.

By then, Babbage is after something far bigger. In October 1834, he begins designing an engine that could carry out any calculation at all. It has a store, holding a thousand numbers of fifty digits each, and a mill, doing arithmetic on them – what we now call a computer’s memory and its processor. Punched cards tell it what to do, an idea Babbage borrows from the French inventor Joseph Marie Jacquard, whose looms have been weaving patterns from punched cards since the early 1800s. And the engine can choose which cards to follow next, depending on its own results. Babbage calls it the Analytical Engine.

In 1840, he explains it to scientists gathered in Turin, and in October 1842, one of them, the Italian engineer Luigi Menabrea, who will later be Italy’s prime minister, publishes the first account of it. Weeks later, on November 4, the government gives up on the Difference Engine, after spending about GBP 17,000 on it, some USD 3.7 million in today’s money. Asked for his opinion, the Astronomer Royal, the English astronomer George Biddell Airy, has called it worthless. Making it useful, the Chancellor of the Exchequer writes to Babbage, would cost too much.

Babbage refines his designs until he dies in 1871, at 79, but never finishes another engine. In 1878, a committee of the British Association for the Advancement of Science advises against building the Analytical Engine: the design is unfinished, and nobody can be sure it would run. Was the engineering of his day not up to it? In 1991, for the 200th anniversary of Babbage’s birth, London’s Science Museum builds his later Difference Engine No. 2 from his drawings, to no finer precision than he could have had. It works, to 31 digits. So precision didn’t stop Babbage. His failure, its builders conclude, had as much to do with politics, money, and personalities as with how hard such a machine was to build at the time. Nothing like it had been built before. Its parts, a committee of the Royal Society reported in 1829, were “dissimilar to any used in ordinary mechanical works”, and making them precisely enough meant “constructing, and in many instances inventing, tools and machinery of great expense and complexity.”

A translation becomes the most famous paper on Babbage’s engine. The English mathematician Ada Lovelace, the daughter of the poet Lord Byron, has known Babbage since she saw his demonstration piece at seventeen. She translates Menabrea’s account into English, and at Babbage’s suggestion, she adds notes of her own, signed A. A. L., three times as long as the account itself.

Lovelace sees further than anyone. The engine needn’t stop at numbers: it works on symbols by rules, and symbols can stand for anything whose relations can be put into rules. If the rules of harmony could be, she writes, the engine “might compose elaborate and scientific pieces of music of any degree of complexity or extent.” As she puts it, “the Analytical Engine weaves algebraical patterns just as the Jacquard-loom weaves flowers and leaves” (italics in the original).

In her last note, she sets out, step by step, how the engine would work out a series of numbers named after the Swiss mathematician Jacob Bernoulli. It’s often called the first computer program, though Menabrea’s account already had a few short ones. Hers is far longer and repeats some of its steps over and over, as programs still do. Historians still argue over how much of it was Babbage’s work.

She also warns against expecting too much. “The Analytical Engine has no pretensions whatever to originate any thing,” she writes. “It can do whatever we know how to order it to perform” (italics in the original).

Lovelace dies of cancer in 1852, at 36. What she might have thought of next, nobody can say. Today, a programming language bears her name: Ada.

The most famous mathematician alive wants every question answered. In 1928, the German mathematician David Hilbert and his student Wilhelm Ackermann call it the main problem of mathematical logic: find a mechanical procedure that decides, for any statement written in logic’s symbols, whether it can be proved. Hilbert wants all of mathematics written in one system of symbols and rules – Leibniz’s dream, made precise – that could be shown to be free of contradictions and to answer every question.

On September 8, 1930, Hilbert speaks to a meeting of German scientists and physicians in his hometown, Königsberg. At a meeting of the same society in 1872, the German physiologist Emil du Bois-Reymond declared that some questions about nature would always be beyond us: “ignorabimus,” we will not know. Hilbert will have none of it. “We must know,” he ends. “We will know.”

The day before, at a smaller meeting in the same city, a 24-year-old Austrian logician, Kurt Gödel, has mentioned, almost in passing, a result that sinks part of Hilbert’s program. In any consistent system of rules rich enough for arithmetic, Gödel has proved, there are true statements that the rules can neither prove nor disprove. Hardly anyone takes it in. The Hungarian-American mathematician John von Neumann does. Gödel publishes the proof the following year. But could a mechanical procedure at least decide which statements can be proved? For six more years, nobody will know.

What makes a statement true? The Polish logician Alfred Tarski gives an old answer a precise form. A true statement, he writes, is one “which says that things are so and so, and things are indeed so and so” (italics in the original): it corresponds to the facts. His example: “‘it is snowing’ is a true statement if and only if it is snowing” (italics in the original). In 1933, he shows how to turn this into an exact definition of truth for a whole formal language, built up from its simplest statements.

But there’s a catch. For a language rich enough for arithmetic, the definition can only be given in a richer language, which talks about the first one from outside. Within the language itself, truth can’t be defined at all. To prove it, Tarski uses a method he credits, in a footnote, to Gödel: statements of arithmetic can be made to talk about statements, even about themselves. If the language could define its own truth, one of its statements could then say of itself, “this statement is not true” – the ancient liar paradox, which is true if and only if it isn’t.

Gödel had used the same trick on proof instead of truth: a statement that says it can’t be proved. Arithmetic can describe which of its statements can be proved, as Gödel showed, but not which ones are true, as Tarski now shows. So the two can never be the same, which is Gödel’s result again, from another side: proof can’t capture all of truth.

So there’s no universal criterion of truth. Some statements can still be settled mechanically: a calculation settles whether 1,681 is a prime number, for example. But no system of rules can tell, of all its own statements, which ones are true. That’s no blow to truth. Tarski’s definition says what truth is, and we can still aim at it, by guessing and criticizing. We just can’t always check for it mechanically. The Austrian-British philosopher Karl Popper later credits Tarski with rehabilitating the idea of truth as correspondence to the facts.

Can a mechanical procedure decide which statements can be proved? A 23-year-old answers Hilbert’s question, and invents the computer on the way. In 1935, at the University of Cambridge, the English mathematician Alan Turing hears the British mathematician Max Newman lecture on Hilbert’s decision problem. What would a mechanical procedure be, exactly? Turing thinks about what a person does when working out a calculation on paper: reading and writing symbols one at a time, following rules, in one state of mind or another. He boils it down to a machine. It has a tape divided into squares, and a head that reads one square at a time. The head can write or erase a symbol there, and move one square left or right. A table says what to do next, for each state the machine can be in and each symbol it can read. Turing calls these states m-configurations: the machine’s counterpart of a person’s state of mind.

One of Turing’s examples shows how much such a table can do. Just ten lines keep the machine writing forever, without ever repeating itself: 0 0 1 0 1 1 0 1 1 1 0 …, each run of 1s one longer than the last. To make the next run longer, the machine has to remember how long the last one was. So it ticks off that run’s 1s, with an x in the empty square beside each, then writes one more 1 than it ticked off, rubbing out the ticks as it goes. The tape is its memory, as in every computer since.

Then comes his big idea. A machine’s table is itself a list of symbols, so it can be written on a tape. “It is possible to invent a single machine which can be used to compute any computable sequence,” Turing writes: a universal machine, which reads another machine’s description and does whatever that machine would do. One computing machine, given the right program, can do the work of every other.

With it, he answers Hilbert. No machine, he shows, can decide for every machine whether it will ever print a 0: if one could, a machine could be made to ask it about itself and do the opposite. So no mechanical procedure can decide, for every statement, whether it can be proved. Turing sends in his paper on May 28, 1936. Weeks earlier, at Princeton, the American logician Alonzo Church has reached the same answer by another route. Turing shows that their two ideas of what can be computed amount to the same thing, and goes to Princeton to work with Church. The view that they capture everything that can be computed by following rules is now called the Church–Turing thesis.

No fixed procedure can settle every question, and as Tarski showed three years earlier, there’s no universal criterion of truth. And while brains, our biological computers, come up with new ideas, nobody yet knows how to program a computer to do that. But once people have put forward their ideas and criticisms, working out which ideas still face criticisms nobody has addressed is mechanical. So Leibniz’s dream survives in a smaller form, because Veritula does just that: it shows which ideas are rationally adoptable, given the criticisms so far.

Then comes the war. On September 4, 1939, three years after his paper and the day after Britain declares war on Germany, Turing reports to Bletchley Park, its codebreaking center. He designs the “bombes,” named after the “bomba,” a machine of the Polish codebreakers who first broke the German Enigma cipher. The bombes search through Enigma’s settings, and from 1940 on, they help read the enemy’s messages. Later in the war, Bletchley Park runs Colossus, an electronic machine the British engineer Tommy Flowers builds to break another German cipher, with statistical methods Turing worked out. But neither the bombes nor Colossus is universal. Each does one kind of job, set up by hand with plugs and switches.

Turing’s paper had shown what’s missing. His universal machine reads its instructions from its tape, the same tape that holds its numbers. So a computer that keeps its program in its memory, along with its numbers, could do any job: to give it a new one, you’d load a new program instead of rewiring it. After the war, Turing designs such a computer, but building it stalls. On June 21, 1948, at the University of Manchester, a small machine built by the British engineers Frederic Williams and Tom Kilburn becomes the first electronic computer to run a program kept in its own memory. Every computer since works this way. Turing joins them that fall. A century after Babbage, his engine runs, in electronics.

Now Turing asks: can machines think? Rather than argue over what thinking is, he proposes a test, which he calls the imitation game: could an interrogator, exchanging typed messages, tell a machine from a person? By the end of the century, he predicts, “one will be able to speak of machines thinking without expecting to be contradicted.” Then he takes on the objections one by one, Veritula-style, among them “Lady Lovelace’s Objection” (italics in the original). She had written: “The Analytical Engine has no pretensions whatever to originate any thing” (italics in the original). Her engine, he points out, was itself a universal computer: “Probably this argument did not occur to the Countess or to Babbage.”

Turing doesn’t see the end of the century. In 1952, he is convicted of “gross indecency” for a relationship with a man and is made to take female hormones for a year. He dies on June 7, 1954, at 41, of cyanide poisoning, which an inquest rules a suicide. In 2009, the British prime minister apologizes for how Turing was treated, and in 2013 the Queen pardons him. Since 2021, his face has been on the 50-pound note.

Can a computer simulate nature? At a conference on the physics of computation, held in May 1981 at a country house of MIT’s outside Boston, the American theoretical physicist Richard Feynman points out a problem. To describe particles that can each be in one of two states, quantum theory needs a number for every combination of their states: 4 numbers for two particles, 8 for three, and twice as many for every particle added. For a few hundred particles, a classical computer – one that, like every computer so far, works with bits that are each either 0 or 1 – would need more numbers than there are atoms in the universe.

So Feynman proposes a different kind of computer, made of quantum parts, that would behave the way nature does. At the end of his talk, he says he isn’t happy with analyses that use only classical physics, “because nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical.”

He isn’t the only one. The American physicist Paul Benioff, at Argonne National Laboratory near Chicago, has already shown on paper that a computer could run by quantum mechanics alone: he worked out how a Turing machine built of quantum parts would carry out its steps, one after another, without losing energy. Some had thought that impossible even in principle. In Moscow, in a short book published in 1980, the Russian mathematician Yuri Manin has suggested, with an argument much like Feynman’s, that quantum automata might do what classical ones can’t. Few in the West notice.

Turing’s universal machine is an abstraction, with an endless tape. But every real computer is a physical object, run by the laws of physics. The British physicist David Deutsch, at Oxford, takes that seriously. Turing claimed that his universal machine can compute anything that would naturally be regarded as computable. That, Deutsch argues, is really a claim about physics, and he restates it as one: “every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means.” He calls it the Church–Turing principle, and points out that experiments could refute it.

Turing’s machine fails it. The quantities of the physics Turing knew, like positions and speeds, vary continuously, and a machine fed a finite tape can only approximate them. So Deutsch describes a universal quantum computer, a machine working by quantum physics itself, and shows that it can meet the principle. It computes nothing that Turing’s machine can’t, given enough time. But with what Deutsch calls quantum parallelism, it can do some tasks faster than any classical computer could, and he gives the first example.

How can it? Deutsch’s answer: the computer shares out the work among copies of itself in other universes, as Everett’s many worlds have it. When a quantum computer does two days’ worth of computing in one day, how would the other interpretations of quantum theory explain the correct answer? “Where was it computed?” he asks (italics in the original). It’s a modest example. Nine years later, an algorithm will make the question far harder to dodge.

Deutsch is often called the father of quantum computing. In 1998 the Institute of Physics gives him its Dirac Prize for it, and he shares the 2023 Breakthrough Prize in Fundamental Physics with the American physicist Charles Bennett, the Canadian computer scientist Gilles Brassard, and the American mathematician Peter Shor.

A quantum computer suddenly has a killer application. Peter Shor, at AT&T’s Bell Labs, finds a way for one to factor large numbers: to find the prime numbers that multiply to give them. That sounds harmless, but most of the internet’s secrets, from bank transfers to private messages, are locked with codes that are safe only because no classical computer can factor a number hundreds of digits long in less than the age of the universe. A quantum computer running Shor’s algorithm could do it in hours.

The trick is to find a rhythm. Take powers of some number, divide them by the number to be factored, and the remainders repeat. Once you know how often, a little arithmetic gives the factors. A classical computer would have to work out the remainders one after another; a quantum computer works them all out at once and lets them interfere, so that only the rhythm is left.

Where does all that computing happen? Factoring a large enough number, Deutsch later works out, would take some 10⁵⁰⁰ times the computational resources that can be seen to be present. “There are only about 10⁸⁰ atoms in the entire visible universe, an utterly minuscule number compared with 10⁵⁰⁰,” he writes. “So if the visible universe were the extent of physical reality, physical reality would not even remotely contain the resources required to factorize such a large number. Who did factorize it, then? How, and where, was the computation performed?” Only other universes, he argues, can explain it.

Not everyone is impressed. In May, at a meeting in Santa Fe where Shor’s algorithm is presented, the American physicist Rolf Landauer of IBM objects that a quantum computer could never correct its errors. Weeks later, the Canadian physicist William Unruh calculates how quickly a quantum computer’s surroundings would ruin its computation: far too quickly, it seems, to factor a large number.

Shor answers the critics himself. Classical computers guard against errors by keeping copies and taking a vote. Quantum states can’t be copied, and looking at them disturbs them. But Shor finds a way to spread one qubit, the quantum version of a bit, over nine, tied together so that checks on how they relate to each other reveal an error, and how to undo it, without revealing what the qubit holds. Months later, the British physicist Andrew Steane, at Oxford, finds a code that does it with seven.

Meanwhile, experimenters start building. In December, at the National Institute of Standards and Technology in Boulder, Colorado, the American physicists Christopher Monroe, David Wineland, and their colleagues make the first quantum logic gate, with a single charged atom held in a trap.

Correcting errors takes more qubits and more steps, and they err too. In August, the French physicists Serge Haroche and Jean-Michel Raimond, who trap single atoms and photons in their laboratory in Paris, warn that quantum computing is the computer scientist’s dream but may be the experimenter’s nightmare. The many entangled qubits such a computer needs are extremely fragile, and the extra ones that error correction brings would only add to the trouble.

That fall, three groups answer, independently: at Los Alamos, the Polish-born American physicist Wojciech Zurek, who has spent years working out how a quantum system’s surroundings wash out its quantum behavior, with his colleagues Emanuel Knill and Raymond Laflamme; in Jerusalem, the Israeli computer scientists Dorit Aharonov and Michael Ben-Or; and soon after, in Moscow, the Russian physicist Alexei Kitaev. They prove what’s now called the threshold theorem. Spread each qubit over several, as Shor’s code does, then each of those over several more, and so on, layer upon layer. If each step errs less often than a certain threshold, the layers correct errors faster than they arise, so a quantum computation can run as long as needed, as accurately as wanted.

In 2012, Haroche shares the Nobel Prize in Physics with Wineland, for their ways of handling single quantum systems without destroying them.

Sixty years after Turing’s paper, no program can think. Programs beat the best players at chess and answer quiz questions, but none comes up with new ideas the way people do. Deutsch asks why, in an essay for the online magazine Aeon, and first argues that such a program, which he calls an AGI, an artificial general intelligence, must be possible.

The reason is universality. Everything the laws of physics let a physical object do, a universal computer can imitate, given the right program and enough time and memory, as Deutsch argued in his paper of 1985. Babbage and Lovelace were the first to guess it, he writes, but they stopped short: “They thought that some cognitive functions of the human brain were beyond the reach of computational universality” (italics in the original). Originating ideas is something brains do, and brains are made of atoms obeying the laws of physics. So with the right program, an Analytical Engine would originate ideas too.

What’s missing is the program, and to write it, we’d need to understand how creativity works, which nobody yet does. A test of behavior like Turing’s imitation game, Deutsch argues, can’t make up for that: it gives no clue how to build what it tests for. Nor can a program be evolved to pass it, since the test can’t be automated: “the ‘judges’ of a program need to have the target ability themselves.”

Since then, programs trained on huge amounts of human writing have learned to converse so much like people that in a study at the University of California, San Diego, in 2025, interrogators chatting with a person and a program at once picked the program as the human 73 percent of the time. Whether such programs originate anything is hotly debated.

Twenty years on, there’s still no quantum computer that does anything a classical one can’t. The Israeli mathematician Gil Kalai, at the Hebrew University of Jerusalem, argues that there never will be. In the Notices of the American Mathematical Society, he explains why. The noise in real devices, he argues, isn’t like the scattered, independent errors the threshold theorem assumes. Small noisy quantum devices can produce only very simple patterns of results, and the errors in entangled qubits go together. So no device will ever get far enough below the threshold for error correction to work, nor beat a classical computer at anything.

Can a quantum computer beat a classical one at anything? In October 2019, Google’s quantum computing team in Santa Barbara, California, claims its 53-qubit chip has done in 200 seconds what would take the best supercomputer 10,000 years: drawing samples from a random quantum circuit. IBM counters, two days before the paper appears, that the supercomputer would need only 2.5 days, and within five years, better methods let classical computers do the task in under two minutes.

Error correction is the real test. On its new chip, Willow, Google spreads one qubit’s worth of information, a logical qubit, over a square of 3 by 3 physical qubits, then 5 by 5, then 7 by 7, and checks them for errors again and again. If the noise were as bad as the skeptics say, the bigger codes would fail more often. But they fail less often: each step up in size cuts the failures by more than half, and the biggest logical qubit outlives the best of the physical qubits it’s made of.

Google’s announcement also reports that at another task, Willow did in under five minutes what would take one of today’s fastest supercomputers 10 septillion years. “It lends credence to the notion that quantum computation occurs in many parallel universes,” it says, “in line with the idea that we live in a multiverse, a prediction first made by David Deutsch.”

The next day, Kalai urges caution about Google’s claims, though he hasn’t studied these ones yet, he writes, and his specific objections don’t apply directly to the error-correction experiment. The American computer scientist Scott Aaronson, at the University of Texas at Austin, replies that the 2019 experiment Kalai keeps re-analyzing was long ago superseded: other experiments since then challenge Kalai’s position, which Kalai grants.

Where does the discussion stand today? In 2025, the Nobel Prize in Physics goes to the British physicist John Clarke, the French physicist Michel Devoret, and the American physicist John Martinis, whose experiments of 1985 led to the superconducting qubits in Google’s chips. One of Google’s researchers estimates that fewer than a million noisy qubits could break the most common of today’s codes in under a week, and governments are switching to new codes, which no known quantum algorithm breaks. Yet no quantum computer has factored a number larger than 15 with Shor’s algorithm without shortcuts that rely on knowing the answer. The universal quantum computer Deutsch described is still to be built.