Introduction
While Alonzo Church was in America building a universe out of abstract functions, a young British mathematician named Alan Turing was tackling the exact same problem from a completely different, and more mechanical, angle.
Turing wasn’t thinking about pure logic. He was trying to imagine the simplest possible machine that could perform computation. He wanted to strip away all the complexity and get to the absolute essence of what it means to follow a set of instructions. The result was a thought experiment, a machine that was never built but became the blueprint for every computer that followed. He called it an “automatic machine”; we call it the Turing Machine.
The Machine’s Anatomy
Imagine a machine that is incredibly simple, almost comically so. It consists of just three parts:
-
An Infinite Tape: Think of a roll of paper, like a receipt from a cash register, that’s infinitely long in both directions. The tape is divided into squares, and each square can either be blank or have a single symbol written on it (like ‘1’, ‘0’, or ‘X’). This tape acts as the machine’s memory.
-
A Read/Write Head: This is a little device that sits over a single square on the tape at any given time. It can do three things:
- Read the symbol on the square.
- Erase or Write a new symbol on the square.
- Move the tape one square to the left or right.
-
A State Register (The “Brain”): This is the machine’s only internal memory. It keeps track of the machine’s current “state” or “mood.” For example, it could be in a state like “Looking for a 1” or “Ready to add.” The machine has a finite number of these states it can be in.
How It All Works: A Simple Recipe
The “program” for a Turing machine is a set of simple rules based on its current state and what it sees on the tape. Each rule is like a line in a recipe:
“If you are in [current state] and you read [current symbol] on the tape, then you should [write a new symbol], move [left or right], and change to [new state].”
That’s it. That’s all it can do.
Let’s imagine a simple Turing machine whose job is to add 1 to a number. The number “3” might be represented on the tape as three consecutive “1”s: ...[B][1][1][1][B]... (B for blank).
The rules might look something like this:
- Start State: “Moving Right”
- Rule 1: If in state “Moving Right” and you see a “1”, don’t change it, move right, and stay in the “Moving Right” state.
- Rule 2: If in state “Moving Right” and you see a Blank square, write a “1” in it, move nowhere, and change to the “Halt” state.
The machine would start at the first “1”, move right past all three “1”s (following Rule 1), and when it hits the first blank square, it would write a “1” and stop (following Rule 2). The tape now has four “1”s. It has successfully computed 3 + 1 = 4.
The Universal Machine
This seems incredibly basic, right? Almost useless. But here is Turing’s genius: he proved that this simple machine, with the right set of rules and symbols, could simulate any algorithm, no matter how complex. It could perform the calculations of Church’s Lambda Calculus. It could run any program that any other computer, even the supercomputers of today, could run. It would be incredibly slow, but it could do it.
This is the concept of Turing Completeness - a system is Turing complete if it can be used to simulate a universal Turing machine.
Turing’s mechanical approach and Church’s logical approach had, by completely different paths, arrived at the exact same definition of what is computable. This powerful conclusion became known as the Church-Turing Thesis: If a problem can be solved by any effective, step-by-step algorithm, it can be solved by a Turing machine.
They had defined the ultimate limits of what machines could ever do. But this also raised a terrifying question: what about the problems they couldn’t solve?