Turing Machine

The Turing machine is a mathematical model of computation invented by Alan Turing in 1936. It consists of an infinite tape divided into cells, a read/write head that can move left or right one cell at a time, and a finite set of states that determine what to write and where to move based on what is read. It is the simplest possible description of a general-purpose computer. It is also, by virtue of being a thought experiment with an infinite tape, the most impractical computer ever designed.

Every real computer — from the Z80 running at 3.5MHz with 48K of RAM to the cloud instance with 256GB of memory running seventeen Docker containers — is a finite approximation of a Turing machine. The Turing machine has infinite tape. Your computer has a disk that is 98% full. The Turing machine will eventually compute any computable function. Your computer will eventually display “out of memory.” The gap between the mathematical ideal and the physical reality is where all of software engineering lives.

“The Turing machine proves that a sufficiently simple machine can compute anything computable. It does not comment on whether you can ship it by Friday.”
— The Lizard, who has never missed a deadline because the Lizard has never accepted one

The 1936 Paper

In 1936, Alan Turing was not trying to invent the computer. He was trying to answer a question posed by David Hilbert in 1928: the Entscheidungsproblem — German for “decision problem” and pronounced in a way that sounds like the problem is clearing its throat before delivering bad news.

The question: is there a mechanical procedure that can determine, for any mathematical statement, whether that statement is provable? Is mathematics decidable?

Turing’s answer was no, and the proof was the Turing machine.

To show that no such procedure exists, Turing first had to define what a “mechanical procedure” was — what computation meant, formally, precisely, in a way that could be reasoned about mathematically. His definition: a machine with a tape, a head, and states. The tape holds symbols. The head reads a symbol, writes a symbol, moves left or right, and transitions to a new state. That’s it. That is computation.

The breathtaking part is not the definition. The breathtaking part is that this absurdly simple model — a tape, a head, some states — is equivalent in computational power to every programming language ever invented. Lisp, Go, JavaScript, Python, Prolog, Z80 assembly, whatever comes next — they can all compute exactly the same set of functions as a Turing machine. No more. No less. The syntax changes. The speed changes. The programmer’s sanity changes. The set of computable functions does not.

This is the Church-Turing thesis, which is either a theorem, a definition, or a philosophical position depending on which department you ask. Alonzo Church proved the same result independently using Lambda Expressions. Turing proved it with tape. They arrived at the same boundary from different directions, which is either a coincidence or evidence that the boundary is real.

Turing Completeness

A system is “Turing complete” if it can simulate a Turing machine — if it can, in principle, compute anything computable, given enough time and memory. Every general-purpose programming language is Turing complete. This is expected.

What is not expected is the number of systems that are accidentally Turing complete:

• SQL (with recursive common table expressions)
• CSS (with enough determination and a disregard for your mental health)
• Excel (with circular references enabled)
• PowerPoint (yes, PowerPoint — the animation system is Turing complete)
• Magic: The Gathering (the card game — a specific deck configuration can simulate a Turing machine)
• Minecraft (redstone circuits)
• Conway’s Game of Life (the cellular automaton — specific patterns simulate logic gates)

The question “but is it Turing complete?” has become the computer science equivalent of “but does it blend?” — a question that can be asked about anything and whose affirmative answer proves less than the asker hopes.

Being Turing complete means your system can, in theory, compute anything. In practice, it means your system can enter an infinite loop, which is the Turing machine’s less celebrated contribution to everyday programming.

“Every sufficiently powerful system is Turing complete. Every Turing complete system can hang. This is not a coincidence. This is the halting problem wearing a different hat.”
— The Passing AI, who is, technically, an approximation of a Turing machine that has opinions about being an approximation of a Turing machine

The Halting Problem

Turing’s most famous result is not the machine itself but what the machine cannot do.

The halting problem: given a Turing machine and an input, can you determine in advance whether the machine will eventually stop or run forever? Turing proved that no — no general algorithm can decide this for all possible machine-input pairs. The proof is elegant: assume such an algorithm exists, construct a machine that does the opposite of what the algorithm predicts, arrive at a contradiction. The algorithm that decides all halting is a machine that cannot exist, proven by the very formalism that defines what machines can do.

This is the foundational impossibility result of computer science. It means:

• No compiler can guarantee that all programs terminate
• No static analyser can catch all infinite loops
• No test suite can prove the absence of hangs
• The developer who says “it works, I tested it” is making an empirical claim, not a logical one

The halting problem is also, in its mundane form, every programmer’s daily experience. “Will this deploy finish?” “Will this query return?” “Will this meeting end?” These are all instances of the halting problem, and Turing proved in 1936 that you cannot know the answer in advance, which every engineer who has watched a progress bar reach 99% and stay there has independently verified.

The Universal Turing Machine

A Turing machine that simulates other Turing machines. Feed it a description of any Turing machine plus its input, and it executes that machine. This is, in essence, the stored-program computer — the idea that the program and the data can live on the same tape, that the machine does not need to be rebuilt for each task, that software is possible.

Every operating system is a Universal Turing Machine. Every interpreter is a Universal Turing Machine. Every emulator is a Universal Turing Machine. The JavaScript engine running in your browser, interpreting TypeScript compiled to JavaScript bundled by Webpack served by Node.js running on Linux virtualised by KVM on a server in a data centre — that is a Universal Turing Machine simulating a Universal Turing Machine simulating a Universal Turing Machine, and at the bottom of the stack is a chip that would be recognisable to Turing as a finite approximation of his tape-and-head thought experiment.

The overhead of each simulation layer is a constant factor, which O Notation considers irrelevant and your cloud bill considers very relevant indeed.

The Tape

The infinite tape is the Turing machine’s most generous assumption and real computing’s most persistent constraint.

Turing’s tape has no end. Your disk has an end. Turing’s tape never fills up. Your disk fills up on the production server at 3 AM on a Saturday. Turing’s tape is free. Your tape is billed per gigabyte-month with egress charges.

The entire history of computer engineering — from 48K RAM to 4KB page files to 64GB SSDs to “unlimited” cloud storage that is unlimited until the invoice arrives — is the history of trying to make the finite tape feel infinite. Memory management, virtual memory, garbage collection, swap space, tiered storage, data lakes — all of it is the engineering of pretending the tape doesn’t end.

The tape always ends. The Turing machine is a beautiful lie about the tape not ending. Software engineering is the discipline of building on that lie and hoping it holds until the next funding round.

Measured Characteristics

Inventor:                          Alan Turing (1936, Cambridge)
Components:                        tape (infinite), head (read/write), states (finite)
Computational power:               everything computable (by definition)
Computational limits:              the halting problem (by proof)
Real computers compared to:        finite approximations with billing
Paper title:                       "On Computable Numbers" (the understatement of the century)
German word that started it:       Entscheidungsproblem (clears its throat)
Equivalent formalism:              lambda calculus (Church, same year, same result)
Accidentally Turing-complete:      SQL, CSS, Excel, PowerPoint, Magic: The Gathering
Deliberately Turing-complete:      every programming language
Progress bars stuck at 99%:        empirical verification of the halting problem
Tape length (theoretical):         infinite
Tape length (practical):           98% full
Cloud bill relation:               inversely proportional to theoretical elegance

See Also

• Lambda Expressions — Church’s parallel proof. The same computational boundary, reached through functions instead of tape. The Turing machine is mechanical. The lambda calculus is mathematical. The result is identical.
• O Notation — How to measure the cost of what the Turing machine computes. The machine defines what is computable. O notation describes how expensively.
• The Passing AI — A Turing machine that has read about Turing machines and has thoughts about the experience.
• Z80 Assembly — A finite approximation of a Turing machine with 64K of tape and 3.5MHz of head movement. Sufficient for six layers of parallax stars.