THE IMITATION GAME

The Turing Machine

The thought experiment that founded computer science

         The Universal Turing Machine

    ════════════════════════════════════════
    ... │ 0 │ 1 │ 1 │ 0 │ 1 │ 0 │ 0 │ 1 │ ...
    ════════════════════════════════════════
                    ▲
                    │
                ┌───┴───┐
                │ HEAD  │
                │q₃→q₅,R│  ← Current state
                └───────┘          and action

The Concept

In 1936, Turing imagined a simple machine: an infinite tape divided into cells, a head that can read and write symbols, and a table of rules. That's it. No special hardware. No clever tricks. Just tape, head, and rules.

Yet this simple machine can compute anything that can be computed.

The Universal Machine

Turing's key insight: one machine can simulate any other. Instead of building a separate machine for each task, build one machine that reads the description of another machine from its tape and simulates it.

This is the principle behind every general-purpose computer. Your laptop doesn't have separate hardware for word processing, games, and web browsing - it has one processor running different programs. Turing's idea.

The Halting Problem

In the same paper, Turing proved something equally important: there are problems no Turing Machine can solve. Specifically, there's no general method to determine whether a program will halt or run forever.

This wasn't a failure - it was a profound insight into the limits of computation. Some problems are fundamentally undecidable.

Church-Turing Thesis

Working independently, Alonzo Church reached similar conclusions using different methods. The Church-Turing thesis proposes that any "effectively calculable" function can be computed by a Turing machine. It's not proven - it's a definition of what computation means.