Alan Turing: Defining Computation Before Computers Existed

The Mind That Gave Machines Their Limits

A Question About Numbers

Alan Mathison Turing was born in 1912 in London. By his early twenties, he was already grappling with one of the most profound questions in mathematics: the Entscheidungsproblem, or “decision problem,” posed by David Hilbert. Could there be a mechanical procedure that would determine, for any mathematical statement, whether it was provable or not?

To answer this question, Turing first had to define what “mechanical procedure” meant. His insight was to imagine the simplest possible machine that could still perform any calculation a human could perform. The result was what we now call the Turing machine: an abstract device with an infinite tape of symbols, a read/write head, and a finite set of rules determining what to do next based on the current symbol.

This imaginary machine wasn’t meant to be built. It was a thought experiment. Yet it captured something fundamental about the nature of computation itself.

The Universal Machine

Turing’s most remarkable discovery wasn’t the machine itself — it was what he called the “universal machine.” He proved that a single Turing machine could simulate any other Turing machine if given a description of that machine as input. In other words, the same hardware could run any program.

This is so obvious to us today that we struggle to see its revolutionary nature. Of course the same computer can run a word processor, a game, and a database — we just install different software. But before Turing, the assumption was that each type of calculation required its own specialized machine. Charles Babbage’s Analytical Engine was programmable — as Ada Lovelace recognized — but nobody had proven that a single design could handle all possible computations.

Turing proved exactly that. His universal machine is the theoretical ancestor of every general-purpose computer. The laptop, the smartphone, the cloud server — they are all physical implementations of Turing’s paper machine.

The Limits of Computation

Turing answered Hilbert’s question with a negative: no, there cannot be a general mechanical procedure to decide all mathematical statements. His proof introduced the halting problem — the demonstration that no algorithm can determine, for all possible programs and inputs, whether a given program will eventually stop or run forever.

This wasn’t a failure. It was a fundamental truth about the nature of computation. Some things simply cannot be computed, not because our machines are too weak, but because computation itself has inherent limits.

For software practitioners, this matters more than it might seem. Every time a program attempts to analyze another program’s behavior — whether for optimization, security scanning, or verification — it runs into walls that Turing identified in 1936. The halting problem isn’t academic trivia; it’s why we cannot write a perfect bug-finder, why code coverage doesn’t guarantee correctness, and why formal verification remains challenging.

Bletchley Park: Theory Meets Practice

When World War II began, Turing’s theoretical brilliance found urgent practical application. At Bletchley Park, he led the effort to decrypt messages encoded by the German Enigma machines. The work he did there saved countless lives and shortened the war by an estimated two years.

Turing designed the Bombe, an electromechanical device that could rapidly test possible Enigma settings. He also contributed to breaking the even more complex Lorenz cipher. This wasn’t merely applying theory — it was inventing new techniques under extreme pressure, combining mathematical insight with engineering pragmatism.

The secrecy surrounding Bletchley Park meant that Turing’s wartime contributions remained classified for decades. But the experience shaped his thinking about building actual computing machines.

After the War: Building Real Computers

After 1945, Turing worked on the design of actual stored-program computers. At the National Physical Laboratory, he wrote the first detailed design for a stored-program computer, the ACE (Automatic Computing Engine). Later, at the University of Manchester, he worked on programming the Manchester Mark 1, one of the world’s first true computers.

Turing wrote some of the earliest actual computer programs. He also wrote the first programming manual. The gap between his 1936 paper and these practical machines was remarkably small — his theoretical framework had been so precise that building physical implementations confirmed his predictions.

The Question of Machine Intelligence

In 1950, Turing published “Computing Machinery and Intelligence,” asking whether machines could think. Rather than debating definitions, he proposed a practical test: if a human conversing with a hidden machine couldn’t reliably distinguish it from another human, the machine should be considered intelligent.

The “Turing test” remains central to AI discussions today. Turing anticipated objections ranging from religious arguments to claims about consciousness, addressing each methodically. He predicted that by the year 2000, machines would be able to fool average interrogators about 30 percent of the time. Large language models have since surpassed that threshold, proving his intuition about the trajectory of artificial intelligence.

More importantly, Turing framed the question correctly. He didn’t ask whether machines “really” think in some metaphysical sense — he asked whether their behavior would become indistinguishable from human thought. That pragmatic framing continues to guide AI research.

Why Turing Matters to Software Practitioners

Turing gave software development its theoretical foundation. The Church-Turing thesis — the idea that any reasonable definition of computation is equivalent to what Turing machines can do — means that all programming languages are fundamentally equivalent in power. Python, JavaScript, C++, and assembly language can all compute exactly the same things.

This universality underlies everything we do. When we abstract away implementation details, when we trust that an algorithm will work regardless of hardware, when we believe that a correct program on one machine will be correct on another — we are relying on principles Turing established.

But Turing also gave us our limits. The halting problem tells us that perfect automated testing is impossible. The incompleteness of computation tells us that some problems cannot have algorithmic solutions. Understanding these limits helps us avoid chasing impossible goals and focus on what engineering can actually achieve.

A Life Cut Short

Alan Turing died in 1954 at age 41, after being prosecuted for homosexuality — then a criminal offense in Britain. He was subjected to chemical castration as an alternative to prison. His death was ruled a suicide, though some have questioned this conclusion.

The tragedy of his treatment has been widely acknowledged. In 2009, the British government issued a formal apology. In 2013, Queen Elizabeth II granted Turing a posthumous royal pardon. His face now appears on the British £50 note.

But the truest memorial to Turing is not official recognition — it is the billions of devices running software today. Every computation proves his ideas correct. Every program exists within the framework he defined.

The Foundation We Build On

We remember Alan Turing not for any single machine or program, but for defining computation itself. Before Turing, “computing” meant human calculators working through arithmetic. After Turing, we had a precise, mathematical definition of what any mechanical process could accomplish — and what it could never do.

Every developer writes programs that are Turing machines. Every algorithm operates within limits Turing proved. Every debate about AI capability starts from the questions Turing asked. The field of computer science exists because Turing showed that computation was worth studying as a subject in its own right.

Computation has boundaries. Turing drew them.