1936, Cambridge, England.
A 24-year-old young man was writing a paper. His paper title was strange: “On Computable Numbers, with an Application to the Entscheidungsproblem.”
This paper contained no circuit diagrams, no gear designs, not a single line of code. It only described an imaginary machine—a computing device of extreme simplicity that existed only on paper.
This young man was named Alan Turing. The machine he proposed later became known as the Turing Machine.
It is considered the theoretical ancestor of computers.
A Strange Question #
Why did Turing invent this machine?
It starts with mathematician Hilbert.
In 1928, Hilbert posed a famous question: the Entscheidungsproblem (Decision Problem)—does there exist an algorithm that can determine the truth or falsity of any mathematical proposition?
In other words, Hilbert wanted to know: Can mathematics be completely automated? Can we build a machine that, given any mathematical proposition, tells us whether it’s true or false?
This question troubled the mathematical community for years. Turing decided to tackle it.
The Turing Machine: The Simplest Model of Computation #
Turing’s approach was: first define what “computation” is, then determine which things can be computed.
He designed an extremely simplified machine—the Turing Machine.
A Turing Machine has only three parts:
- An infinite tape: Divided into cells, each cell can hold a symbol (like 0 or 1)
- A read/write head: Can read the symbol in the current cell, write new symbols, and move left or right
- A state table: Tells the machine what to do given the current state and current symbol (what to write, which direction to move, what state to transition to)
That’s it! No memory, no hard drive, no CPU—just tape, a read/write head, and a state table.
But Turing proved an astonishing conclusion: this crude machine can compute anything that is computable.
It can do addition, multiplication, square roots, solve equations. It can simulate any complex computational process. If a problem can be solved by a Turing Machine, it is “computable”; if not, it is “uncomputable.”
Turing’s Answer #
Returning to Hilbert’s question: Does there exist an algorithm that can determine the truth or falsity of any mathematical proposition?
Turing used his machine to give the answer: No.
He proved that some problems cannot be solved by Turing Machines—such as the “halting problem”: given a program and input, determine whether the program will eventually halt.
This proof process is complex, but the conclusion is clear: Mathematics cannot be completely automated. Some questions machines can never answer.
This conclusion shocked the mathematical community. But the significance of the Turing Machine extends far beyond this.
Why Is the Turing Machine Important? #
You might ask: The Turing Machine is just an imaginary concept on paper; what does it have to do with real computers?
The relationship is enormous.
First, the Turing Machine defined the boundaries of computation. It tells us which problems can be computed and which cannot. This is the theoretical foundation of computer science.
Second, the Turing Machine proved the possibility of universal computation. Turing proposed a “Universal Turing Machine”—one that can simulate any other Turing Machine. This is the theoretical prototype of modern “general-purpose computers”: one machine that can run any program.
Third, the simplicity of the Turing Machine. The Turing Machine has only tape, a read/write head, and a state table, yet it can compute anything computable. This shows that the essence of computation is simple—we don’t need complex machines, just simple rules and infinite storage.
All subsequent computers—from ENIAC to your smartphone—are theoretically implementations of the Turing Machine. What they can do, the Turing Machine can do; what the Turing Machine cannot do, they cannot do either.
Turing’s Life #
Turing was born in London in 1912. He showed extraordinary mathematical talent from childhood but also seemed out of place—he didn’t like sports, wasn’t good socially, and preferred thinking about strange questions alone.
At Cambridge University, he wrote that paper about the Turing Machine, but it didn’t attract much attention at the time. Mathematicians thought it was just another theoretical model with little relevance to reality.
Then, World War II broke out.
Turing was recruited to Bletchley Park to help crack Nazi Germany’s codes. The Germans used an encryption machine called “Enigma,” whose codes changed daily and were theoretically unbreakable.
But Turing did it. He designed an electromechanical device called the “Bombe” that could quickly try various possible keys. Under his leadership, Bletchley Park cracked thousands of German intelligence messages daily, making a huge contribution to Allied victory.
Historians estimate that Turing’s work shortened the war by 2-4 years and saved 14 million lives.
A Tragic Ending #
After the war, Turing continued researching computers and artificial intelligence. He proposed the famous “Turing Test”: if a machine can converse with a human, and the human cannot distinguish it from a person, then the machine can be said to “think.”
But his life wasn’t smooth. In 1952, he was prosecuted by the British government for homosexual acts. At the time, homosexuality was illegal in Britain. Turing was forced to accept “chemical castration”—estrogen injections to “treat” homosexuality.
Two years later, on June 7, 1954, Turing was found dead at home with a half-eaten apple by his bedside. The autopsy report showed he died from cyanide poisoning.
He was only 41 years old.
Belated Justice #
It wasn’t until many years after Turing’s death that the world began to recognize his greatness.
In 1966, the Association for Computing Machinery established the Turing Award, honoring those who have made major contributions to computer science. The Turing Award is called the “Nobel Prize of computing.”
In 2009, British Prime Minister Gordon Brown apologized on behalf of the government: “On behalf of the British government, and all those who live freely thanks to Alan’s work, I’m very proud to say: we’re sorry.”
In 2013, Queen Elizabeth II officially pardoned Turing.
In 2014, the film The Imitation Game was released, telling the story of Turing cracking Enigma. Star Benedict Cumberbatch said: “Turing was the father of computer science and a war hero.”
Turing’s Legacy #
Today, every time you run an app on your phone, every time you open a webpage on your computer, you’re using Turing’s ideas.
The Turing Machine tells us: The essence of computation is simple, but simple rules can produce infinite possibilities.
This idea was developed by another person after Turing. He turned the Turing Machine’s theory into concrete engineering design, defining the architecture of modern computers.
His name was John von Neumann.
His story continues tomorrow.
Today’s Key Concepts #
Turing Machine A theoretical model of computation consisting of infinite tape, a read/write head, and a state table. A Turing Machine can compute anything that is “computable” and is the theoretical foundation of computer science. Modern computers are theoretically implementations of the Turing Machine.
Halting Problem An undecidable problem that Turing proved: there is no algorithm that can determine whether any arbitrary program will halt. This demonstrates the boundaries of computation—some problems machines cannot solve.
Turing Test A method Turing proposed for judging whether a machine has intelligence: if a machine can converse with a human, and the human cannot distinguish whether it’s a machine or a person, then the machine can be said to have intelligence. This is an important concept in artificial intelligence.
Discussion Questions #
- The Turing Machine has only tape, a read/write head, and a state table, yet it can compute anything computable. What do you think this says about the “essence” of computation?
- Turing was persecuted for homosexuality and eventually committed suicide. How do you think society should treat people who are “different”?
Tomorrow’s Preview: von Neumann and the Stored-Program Computer—how to turn Turing’s theory into real machines?