The Turing Machine

Before simulating one, be one. It takes ten minutes and it is genuinely clarifying.

1. Draw a long row of boxes on paper — that is the tape. Write a few 1s in it and leave the rest blank.
2. Put a coin on the leftmost box — that is the head.
3. Write this rule table down: in state A reading 1, write 1, move right, stay in A. In state A reading blank, write 1, move left, go to state HALT.
4. Now execute it strictly. Read the cell under the coin, look up the rule, do exactly what it says, and nothing else.

You have just added one to a number written in unary. More importantly, notice what you were NOT allowed to do: look ahead, remember anything beyond your current state, or make a decision the table did not cover.

The step that turns a mathematical curiosity into the entire computing industry.

1. Note that each machine above is a DIFFERENT machine — a different rule table for each task.
2. Now consider encoding a rule table as symbols ON the tape, alongside the input.
3. Design a machine whose rules are: read the encoded table, find the rule matching the simulated state and symbol, apply it, repeat.

That machine simulates any other machine given its description. It is a universal Turing machine, and it is the reason software exists.

Before this, a machine that added and a machine that multiplied were different objects, and Babbage's engine could only ever tabulate polynomials. After it, there is ONE machine and the task is data you feed it. The distinction between hardware and software is created exactly here.

Find out how little is needed to reach the ceiling of computation.

1. List the ingredients of the machine: read/write storage, conditional branching, unbounded tape.
2. Remove the unbounded tape and consider what a finite machine can still do.
3. Consider whether the relay logic from earlier in this batch, plus enough memory and a conditional jump, would qualify.

Any system with conditional branching, read/write memory and no fixed limit on that memory is Turing complete — able to compute anything computable. The bar is remarkably low, which is why it is reached accidentally: spreadsheet formulas, some card games, Conway's Game of Life and several configuration languages are all Turing complete without their designers intending it.

The one honest caveat: every real machine has finite memory, so strictly it is a finite state machine rather than a Turing machine. The idealisation is useful because the memory limit is rarely the interesting constraint.