Overview

Before computers existed, Alan Turing invented the idea of a computer. He wanted to solve a math problem: “Is there a machine that can solve any logical problem?” He imagined a simple machine with an infinite roll of tape. It turns out, this imaginary machine is as powerful as every supercomputer we have ever built.

Core Idea

The core idea is Universal Computation. A simple set of rules (Read, Write, Move Left, Move Right) is enough to compute anything that is computable.

Formal Definition

A mathematical model of computation consisting of:

  1. Tape: Infinite memory.
  2. Head: Reads and writes symbols.
  3. State Register: Remembers what it is doing.
  4. Table of Instructions: The code.

Intuition

  • The Machine: Imagine a person in a room with an infinite roll of toilet paper and a pencil. They follow a rule book: “If you see a 1, erase it, write a 0, move right, and turn to page 5.”
  • The Insight: This simple person can run Microsoft Windows. It would take a trillion years, but they could do it.

Examples

  • The Halting Problem: Turing proved that there are some problems a computer cannot solve. You cannot write a program that checks if another program will run forever. This was a shock to mathematics.
  • Game of Life: A simple grid of cells that is “Turing Complete.” It can simulate a Turing Machine.

Common Misconceptions

  • It’s a physical machine: It’s a thought experiment. You can’t build one because you can’t have infinite tape.
  • Quantum Computers are “more” than Turing Machines: No. They are faster, but they can’t solve uncomputable problems (like the Halting Problem). They are still Turing Machines.
  • Church-Turing Thesis: “Everything that can be computed can be computed by a Turing Machine.”
  • P vs NP: The biggest unsolved problem in Computer Science. (Can we solve hard problems quickly, or just check the answers quickly?)

Applications

  • Complexity Theory: Classifying problems by how hard they are. (P, NP, NP-Complete).

Criticism / Limitations

  • Efficiency: Turing Machines don’t care about time. They only care about possibility.

Further Reading

  • Petzold, Charles. The Annotated Turing.
  • Hodges, Andrew. Alan Turing: The Enigma.