Unit 8
Computability.
What it means to compute: a Turing machine, a question no program can always answer, and the Game of Life.
Before this unit
The unit, lesson by lesson
Lessons
4 lessons · 25 practice questions · about 2 hours
A Turing machine
The simplest machine that can compute anything: a tape, a head that reads and writes one cell, one state in memory, and a rule card. Run, step by step, a machine that adds three and two.
State tables
Reading a rule card like a program: the busy beaver, which writes as many 1s as it can and halts, and a counter that counts in binary for ever, with the carry of addition inside one rule. And why a machine like this can do anything a computer can.
The halting problem
Some machines halt and some run for ever. Can a checker be built that always says which? Turing's proof that the answer is no, and what that does, and does not, say about what computers can do.
Simple rules, complex behaviour
Conway's Game of Life: a board of cells, each counting its eight neighbours. A one-sentence rule, and out of it still shapes, blinkers, gliders that travel across the board, and even a computer.