The History of AI, Part 2: Alan Turing and the Question "Can Machines Think?"

The History of AI, Part 2 of 24. Last time we followed the dream of thinking machines from ancient myth to Boole's algebra of logic. Now the dream gets a mathematical definition, and a man who dared to ask the question out loud. [Start from Part 1 if you missed it.]

If you could pick one person to stand at the doorway of artificial intelligence, you would pick Alan Turing. He didn't coin the term "AI" (that came later). He didn't build the first neural network or write the first chess program that played an actual game on a real machine, although he came close. But before almost anyone else, he saw clearly three things:

What it means, mathematically, to compute something.
That one machine can be built to do the work of every other computing machine.
That the right way to ask "Can machines think?" is to stop arguing about definitions and start testing behavior.

Those three ideas define the field. This chapter is about how he got to them, what he did in between (including helping win a war), and why a paper he wrote in 1950 is still being argued over today by people who have never heard of the man.

A strange young man in Cambridge

Alan Mathison Turing was born on 23 June 1912 in London. By most accounts he was a brilliant, awkward, intensely literal boy who preferred experiments to conversation. At school he was frequently told off for being untidy and absentminded, and he was more interested in science than the classics his school preferred.

Alan Turing in 1951. Public domain, via Wikimedia Commons.

The central emotional event of his youth was the death of his close friend Christopher Morcom in 1930, from bovine tuberculosis. Morcom had been Turing's intellectual companion, and his loss pushed Turing toward a question that would shadow his work: what is the relationship between mind and matter? Could a mind survive in some other physical form?

He went to King's College, Cambridge, to study mathematics, was elected a fellow of the college at just 22, and in 1935 he sat in a lecture by the logician Max Newman about Hilbert's Entscheidungsproblem, the "decision problem" we left hanging at the end of Part 1.

The problem he set out to solve

Quick recap. In the early 20th century, the mathematician David Hilbert asked whether there could be a mechanical procedure, a definite step-by-step method, that could decide, for any mathematical statement written in formal logic, whether that statement was provable. If such a procedure existed, mathematics could in principle be automated.

To answer this, you first had to say what you meant by a "mechanical procedure." People had an intuitive notion, but no precise definition. You can't prove that something is impossible until you know exactly what counts as possible.

So Turing did something that, in retrospect, seems both obvious and miraculous. He asked: what does a human being do when they carry out a calculation by following rules? And he stripped that down to the absolute essentials.

Picture a person with a pencil and a very long strip of paper divided into squares. At any moment they:

look at one square,
depending on what they see and what "state of mind" they're in, they write or erase a symbol,
move one square left or right,
and switch to a new state of mind.

That's it. Nothing else is necessary. Whatever a human can compute by following rules, Turing argued, can be broken down into those tiny steps.

The Turing machine

This imaginary device, which he described in a paper submitted in 1936 titled "On Computable Numbers, with an Application to the Entscheidungsproblem," is now called a Turing machine. It has:

A tape: infinitely long, divided into cells, each holding a symbol (say 0, 1, or blank).
A head: which reads and writes one cell at a time.
A state register: remembering which of a finite number of states the machine is in.
A table of rules: for every combination of (current state, symbol under the head), it says what symbol to write, whether to move left or right, and which state to enter next.

It looks absurdly simple, and that is the point. Let's make it concrete with a tiny simulator. This one adds 1 to a binary number written on the tape:

def run_turing_machine(tape, rules, state="start", blank="_", max_steps=1000): tape = dict(enumerate(tape)) head = 0 for _ in range(max_steps): symbol = tape.get(head, blank) if (state, symbol) not in rules: break write, move, state = rules[(state, symbol)] tape[head] = write head += 1 if move == "R" else -1 if state == "halt": break cells = range(min(tape), max(tape) + 1) return "".join(tape.get(i, blank) for i in cells).strip(blank) # Binary increment: go to the right end, then carry leftwards. rules = { ("start", "0"): ("0", "R", "start"), ("start", "1"): ("1", "R", "start"), ("start", "_"): ("_", "L", "carry"), ("carry", "1"): ("0", "L", "carry"), # 1 + 1 = 0, carry  ("carry", "0"): ("1", "L", "halt"), # 0 + 1 = 1, done  ("carry", "_"): ("1", "L", "halt"), # overflow: new leading 1 } print(run_turing_machine("1011", rules)) # 1100 (11 + 1 = 12) print(run_turing_machine("111", rules)) # 1000 (7 + 1 = 8)

Eleven lines of rules, and it correctly does arithmetic. Add more rules and you can make a machine that multiplies, sorts, plays checkers, or, in principle, runs a neural network. Every algorithm you will ever write is a very fancy Turing machine in disguise.

The universal machine

Here is where Turing went from clever to profound. He observed that the table of rules defining a Turing machine could itself be written down as a string of symbols on a tape. So you could build one special machine, the universal Turing machine, that reads another machine's description from its tape and then simulates it, step by step.

Read that again, because it is the foundation of modern computing. A single fixed machine can do the work of any other machine, as long as you give it the right description. The description is what we now call a program. The universal machine is what we now call a computer.

This is the same idea al-Jazari's pegs and Jacquard's cards had hinted at, and Babbage had designed in brass, but Turing provided something they never had: a rigorous mathematical definition. And that gave him a tool for the problem Hilbert had left behind.

Undecidable

Using this notion of a machine, Turing proved that some perfectly well-defined questions can never be answered by any mechanical procedure. His famous example is the halting problem: given a program and its input, can you always determine in advance whether the program will eventually stop or run forever?

The answer is no, and the proof is delightfully slippery. Suppose someone gave you a perfect "halting detector" function halts(program, input). You could use it to write a mischievous program like this:

def troublemaker(program): if halts(program, program): # "will this program halt when fed itself?"  while True: # ...then loop forever  pass else: return # ...otherwise halt immediately

Now ask: what happens when you run troublemaker(troublemaker)? If the detector says it halts, it loops forever. If the detector says it loops forever, it halts. Either way, the detector is wrong. So no such perfect detector can exist.

This is a landmark result. It means there are hard, provable limits to what computation can do, no matter how fast or large the computer. It answered Hilbert's question with a firm no, and in doing so it gave birth to computer science.

Almost simultaneously, the American logician Alonzo Church reached the same conclusion using a completely different formalism called the lambda calculus (which still lives on in functional programming languages). Church's paper appeared a few weeks before Turing's, so Turing had to add an appendix proving that the two approaches define the same class of computable functions. Together, the idea that "anything that can be computed in any reasonable sense can be computed by a Turing machine" became known as the Church-Turing thesis. It is not a theorem you can prove, since "reasonable" is informal, but it has held up for nearly a century.

Turing then spent two years at Princeton, completing a PhD in 1938 under Church, before returning to England as the world drifted toward war.

War: Bletchley Park

In September 1939, Britain declared war on Germany. Turing reported to Bletchley Park, the British codebreaking center, where he would spend the war.

A naval M4 Enigma cipher machine, the kind used by German U-boats. Image: Daderot, CC0, via Wikimedia Commons.

The target was Enigma, the electromechanical cipher machine used by the German military. Enigma scrambled each letter through a series of rotating wheels and a plugboard, creating an astronomically large number of possible settings, and the settings were changed daily. Polish mathematicians, led by Marian Rejewski, had broken earlier versions in the 1930s and generously shared their methods with the British and French just before the war. Without their groundwork, Bletchley's task would have been far harder.

Turing's contribution was to design a machine and a method to attack the daily Enigma settings. The machine was the Bombe, an electromechanical device that, instead of trying every key, used logical deduction. Given a "crib", a guess at some plaintext that was likely to appear in a message (such as a weather report beginning with a standard phrase), the Bombe searched for the wheel settings that did not lead to a logical contradiction, quickly ruling out huge numbers of possibilities. The first Bombe, named "Victory," entered service in March 1940, and later ones were improved with Gordon Welchman's "diagonal board."

A Turing-Welchman Bombe reconstruction at Bletchley Park. Image: Vintage Fan 5678, CC BY-SA 4.0, via Wikimedia Commons.

Turing also led the effort in Hut 8 to break the German Navy's far more secure Enigma traffic, which was vital because U-boats were strangling Britain's Atlantic supply lines. By 1941, with the help of captured codebooks and new techniques, Hut 8 was reading naval traffic more regularly. Historians generally credit this work with helping to shorten the war and save many lives, though the precise figures people quote (such as "two years" or "14 million lives") are estimates, not measurements, and should be treated with caution.

A few clarifications worth making, because the popular story often blurs them:

Turing didn't work alone. Bletchley employed thousands of people, many of them women, and Rejewski, Welchman, Hugh Alexander, Joan Clarke, and many others were vital.
Colossus, the first large-scale programmable electronic digital computer, was designed by the engineer Tommy Flowers to attack a different German cipher (the Lorenz cipher). It wasn't Turing's invention, though Turing's earlier ideas and Max Newman's team were part of that world.
The work was kept secret for decades. Even the people involved were forbidden to talk about it, so the credit came very late.

During a visit to the United States in 1943, Turing met the mathematician Claude Shannon at Bell Labs, and the two reportedly spent tea breaks discussing whether machines could be made to think. Shannon would soon found information theory and later help organize the Dartmouth workshop that named the field of AI. Keep his name in mind.

From codebreaking to "electronic brains"

When the war ended, Turing wanted to build a real universal machine, not just prove one possible. In 1945 he wrote a detailed design for the Automatic Computing Engine (ACE) for Britain's National Physical Laboratory. It was a complete stored-program computer design, written independently of (and in some respects more ambitious than) John von Neumann's famous EDVAC report of the same period. Bureaucratic delays and the sheer ambition of the plan meant the full ACE wasn't built; a smaller version, the Pilot ACE, ran in 1950.

Frustrated, Turing moved to the University of Manchester in 1948, where the Manchester Baby (the first stored-program computer to run a program, in June 1948) and its successors, the Manchester Mark 1 and Ferranti Mark 1, were being developed. There he finally had a machine to play with.

And play he did. He was thinking seriously about machine intelligence, years before the phrase existed.

"Intelligent Machinery" (1948)

In 1948, Turing wrote a report for the National Physical Laboratory called Intelligent Machinery. His employer found it too unconventional to publish, and it stayed buried until 1968. In it, he sketched ideas that were decades ahead:

He described "unorganized machines," networks of simple connected elements that look strikingly like artificial neural networks, and suggested they could be trained by modifying their connections.
He argued that the way to make a thinking machine was not to hand-code adult intelligence but to start with something like a child's mind and educate it.
He listed fields where machines could try to show intelligence: games, language learning, translation, cryptography, mathematics.

He also proposed (with his friend David Champernowne) a chess-playing algorithm called Turochamp. There was no computer powerful enough to run it, so in 1952 Turing hand-simulated the algorithm, working out each move himself with pencil and paper, spending about half an hour per move. The "paper machine" lost to a human but demonstrated the idea. Meanwhile, at Manchester, his colleague Christopher Strachey wrote a program that played a full game of draughts (checkers) around 1951 to 1952, among the first real game-playing AI programs to run on an actual computer.

The 1950 paper that started the argument

In October 1950, the philosophy journal Mind published a paper by Turing titled "Computing Machinery and Intelligence." It begins with one of the most famous sentences in the field:

I propose to consider the question, "Can machines think?"

And then, in the very next breath, he sets that question aside.

Why he replaced the question

Turing realized that "Can machines think?" would collapse immediately into an argument about what the words "machine" and "think" mean. You could argue forever. So he proposed substituting a practical test, based on behavior.

He called it the imitation game. It starts with a party game in which an interrogator, in a separate room, tries to determine which of two hidden people is a man and which is a woman, by asking written questions. Each hidden person tries to convince the interrogator of their identity, and the man is allowed to lie.

Now, Turing says, replace the man with a machine. If the interrogator is just as likely to pick the wrong answer as before, then the machine has done as well as the man. Over time the setup was simplified into what we call the Turing test: a human judge chats by text with a hidden human and a hidden machine, and if the judge can't reliably tell which is which, we say the machine has passed.

There are three clever things about this proposal:

It sidesteps metaphysics. You don't need to settle whether the machine "really" has a mind or consciousness. You only need to judge its conversational behavior.
It uses language as a window onto intelligence. Language can touch on anything: mathematics, poetry, jokes, ethics, memory. To keep up in free conversation, a machine needs broad, flexible competence.
It's based on how we judge each other. We never directly observe another person's mind. We infer it from behavior, so why should machines be held to a different standard?

Notice the echo of Descartes from Part 1. Four centuries earlier, he had said a machine could never respond appropriately to anything said in its presence. Turing turned that claim into an empirical challenge.

A prediction, and a quiet bet

Turing made a specific forecast. He believed that "in about fifty years' time" it would be possible to program computers with a storage capacity of about 10^9 (a billion) bits, which is roughly 120 megabytes, to play the imitation game so well that an average interrogator would have no more than a 70 percent chance of identifying the machine after five minutes of questioning.

Notice how modest that is. He didn't predict a computer that would be conscious or superhuman, just one that would fool a typical person a bit under a third of the time in a short chat. He was in a way too pessimistic about the hardware and optimistic about the timeline. By the year 2000 no program came close, yet in the 2020s chatbots could sustain much longer and more convincing conversations. (A 2025 preprint by researchers at UC San Diego reported that, in a controlled three-party version of the test, a state-of-the-art language model given a persona prompt was judged to be the human more often than the real human participants were. That result is debated and depends heavily on the test setup, but it shows how the ground has shifted.)

The nine objections

What makes the paper timeless is that Turing didn't just propose a test. He listed the main objections he expected and answered them. Reading them today feels like opening a transcript of any modern AI debate. In summary:

The theological objection. Thinking is a function of the immortal soul, and God hasn't given souls to machines. Turing responded that this restricts God's power and noted how such arguments have been wrong before, like religious objections to Copernicus.
The "heads in the sand" objection. The consequences of thinking machines would be too dreadful; let's hope they never happen. Turing found this more in need of consolation than refutation.
The mathematical objection. Gödel's and Turing's own results show limits of formal systems, so machines have limits humans don't. Turing replied that humans are fallible too, and nobody has shown that humans are exempt from such limits.
The argument from consciousness. A machine cannot truly think unless it feels thoughts, not merely produces words. Turing pointed out that this logic, taken to extremes, leads to solipsism: you can't know that other humans feel either. We are polite and assume they do.
Arguments from various disabilities. "Machines can never do X": be kind, have a sense of humor, fall in love, enjoy strawberries and cream, learn from experience. Turing noted that these claims were usually made with no evidence beyond the machines the person happened to have seen.
Lady Lovelace's objection. The one we met in Part 1: machines can do only what we tell them to. Turing replied that machines surprise him all the time, and suggested that a learning machine could do things its programmers never foresaw.
The argument from continuity in the nervous system. The brain is analog, not digital. Turing replied that a digital machine can approximate an analog one to any desired precision.
The argument from the informality of behavior. Humans don't follow fixed rules for every situation, so they can't be machines. Turing distinguished "rules of conduct" from "laws of behavior," noting that something can be governed by laws without following explicit rules.
The argument from extrasensory perception. If telepathy exists, it could break the test. Turing took this half-seriously, given the apparent statistical evidence researchers were then claiming, and suggested a "telepathy-proof room." Today this one is mostly a historical curiosity.

Most of these objections are still alive. If you listen to arguments about large language models, "it's just predicting text" is Lovelace's objection in modern dress. "It doesn't really understand" is the consciousness objection. "It can't do X" is the disabilities argument, with a list that keeps shrinking.

Learning machines

The final section of the paper is the most prophetic. Turing asks: how would we actually build a machine that passes the test? His answer is that trying to program the full complexity of an adult mind directly would be hopeless. Instead:

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.

He even discusses using rewards and punishments, trial and error, and randomness in the learning process, ideas that are the ancestors of reinforcement learning and modern machine learning. He imagined starting with a simple "child machine" and teaching it. That is, in a nutshell, the approach that works today: don't write the rules, grow them from experience.

This turned out to be the single most important insight in the paper, even though it took more than sixty years for the technology to catch up with it.

Criticisms of the Turing test

The test has always had critics, and several of their objections are worth knowing.

It measures deception, not intelligence. A system might win by tricking judges. This was shown in 1966, when Joseph Weizenbaum's chatbot ELIZA, which does little more than rephrase your sentences as questions, convinced some people that it understood them. (We'll meet ELIZA in Part 5.) In 2014, a chatbot called "Eugene Goostman," pretending to be a 13-year-old Ukrainian boy with limited English, was widely reported to have "passed the Turing test" at an event, but the claim was heavily criticized: the threshold was only 30 percent, the test lasted five minutes, and the persona gave the bot an excuse for evasive or odd answers.

It focuses on human-like behavior. A machine might be intelligent in ways that are not human-like. Should an AI that can't chat but can fold proteins brilliantly be said to lack intelligence? Many modern researchers prefer task-based benchmarks over imitating humans. (This is the shift from goal #2, "acting like humans," to goal #4, "acting rationally," that we discussed in Part 1.)

It doesn't test understanding. The philosopher John Searle's famous Chinese Room argument (1980) imagines a person who doesn't speak Chinese, following a rulebook to respond to Chinese messages passed under a door. From outside, the room seems fluent in Chinese. But the person inside understands nothing. Searle's point is that passing the test doesn't prove genuine understanding. We'll revisit this when we discuss symbolic AI and again in the era of large language models, because the argument has become newly urgent.

Turing might have shrugged. He had already pointed out that we attribute thinking to other people based only on their behavior. But the question whether behavior is enough remains one of the deepest unresolved problems in the field.

Morphogenesis, and a tragedy

Even as Turing was shaping the philosophy of AI, his curiosity was broader than any one field. In 1952 he published "The Chemical Basis of Morphogenesis," a paper showing how simple chemical reactions and diffusion could spontaneously produce patterns like spots and stripes on animals. It founded a whole branch of mathematical biology, and it is a surprisingly close cousin of modern ideas in neural networks and self-organization: simple local rules producing complex global structure.

But in 1952, Turing was prosecuted for homosexual acts, which were criminal offenses in Britain at the time. To avoid prison, he accepted a court-ordered hormonal treatment, a form of chemical castration. He lost his security clearance and was barred from continuing certain government work. On 7 June 1954, he was found dead of cyanide poisoning, aged 41. The inquest ruled it suicide, although some friends and later writers have questioned that conclusion; the evidence is not definitive.

The recognition came slowly. In 1966 the Association for Computing Machinery created the Turing Award, now often called the "Nobel Prize of computing." In 2009, British Prime Minister Gordon Brown issued a public apology on behalf of the government for the way Turing had been treated. In 2013, he received a royal pardon, and in 2017 "Turing's Law" retroactively pardoned many other men convicted under similar laws. In 2021, his portrait appeared on the Bank of England's £50 note.

It is hard to overstate what was lost. Turing died at 41. If you want to know what the early history of AI might have looked like with him alive through the 1960s and 1970s, you can only imagine.

Why Turing still matters for AI

Let's connect the dots back to the story we're telling.

A definition of computation. The Turing machine gave AI its foundation. When researchers say a machine can "in principle" do anything a brain can do, they're leaning on the Church-Turing thesis.
The universal machine. The idea that hardware and software are separate, and that one machine can emulate any other, is why we can run AI on general-purpose computers rather than on special-purpose brains. It's why the same laptop runs a spreadsheet and a chatbot.
A behavioral standard. The imitation game moved the question from "what is thinking?" to "what can this system do?" That style of thinking still underlies most AI evaluation.
Learning over programming. His "child machine" and "unorganized machines" pointed straight at machine learning, the approach that finally worked.
A realistic temperament. Turing took the hard objections seriously and answered them honestly, a habit the field has not always maintained.

And it set up a tension that will drive the next few chapters. If thinking is computation, then in principle we can write it as a program. The first generation of researchers, inspired by Turing and by the new electronic computers, set out to do exactly that, writing down the rules of reasoning by hand. Meanwhile, a second group asked a different question: what if we didn't write the rules, but built something inspired by the brain and let it learn? That is where Part 3 begins.

Key takeaways

Turing's 1936 paper defined computation with an imaginary machine and proved the halting problem unsolvable, showing that computation has fundamental limits.
The universal Turing machine is the theoretical ancestor of every programmable computer.
At Bletchley Park, Turing helped break German Enigma traffic, working alongside many others, including Polish pioneers.
In "Computing Machinery and Intelligence" (1950), he replaced "Can machines think?" with the imitation game and answered the major objections still debated today.
He proposed building learning machines that start like children, a strikingly modern idea.
The Turing test has real weaknesses, but it remains a cultural landmark and a useful provocation.

Try it yourself

Here are three small exercises:

Extend the simulator. Modify the Turing machine above to decrement a binary number, or to check whether a string of 0s and 1s is a palindrome. Notice how awkward it feels to do anything useful with such tiny steps. That awkwardness is exactly why we invented higher-level languages.
Play the imitation game. Ask a friend to answer five of your questions by text while you chat with a chatbot in another window. Can you tell which is which? What questions give the machine away? Write down the tricks you used, because those are your informal definition of "intelligence."
Argue both sides. Pick one of Turing's nine objections and write a paragraph defending it against the best modern chatbot you know. Then write a paragraph from Turing's side.

Next up

In Part 3, we leave Turing's paper behind and visit a strange pair: a neurophysiologist and a teenage logician who in 1943 published a paper arguing that the brain can be modeled as a network of logical switches. It's the first mathematical neural network, and it introduces a thread of the story, the machines that learn, that will vanish, reappear, and finally explode in the 2010s. We'll also meet Norbert Wiener and the strange, short-lived science of cybernetics.

If this chapter was useful, follow the series and drop your own view on the Turing test in the comments. Does a chatbot passing it settle anything for you?

See you in Part 3.

☕ If this series helped you, you can support my writing on Ko-fi.