Answer key · Unit 8

Computability.

Each lesson’s practice questions, their correct answers and the mistakes they spot. Answers read off the Scene use the same setting the learner sees.

Misconception catalogue

Answer key 4

Lesson 1 of 4 · About 20 minutes

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.

Open the lesson

The 5 steps and their answers

Step 1 of 5
Open this step
Read, write, move
Practice · Choose
Question
What does a Turing machine do in one step?

Correct answer
- Correct Reads the cell under the head, writes a symbol in it, moves one cell and goes to the next state, by the rule for that state and symbol
Setup, choices and feedback
The Scene at this step
Program
Adder
Steps run
0
The machine / No checker
The machine
Choices
Shown in a random order.
- Correct Reads the cell under the head, writes a symbol in it, moves one cell and goes to the next state, by the rule for that state and symbol
- Wrong Scans the whole tape and decides what to write
  Misconception: Thinks a Turing machine can look at the whole tape at once, rather than the one cell under its head.
  Feedback from the catalogue
  The head sees one cell only, the one beneath it. To know what is further along the tape the machine has to move there, cell by cell, remembering in its state what it is looking for. That is how the adder “finds” the end of the number: it simply keeps going right in state B until it reads a blank.
- Wrong Jumps to whichever cell the rule says
  Feedback
  The head always moves one cell, left or right. To get far it takes many steps.
- Wrong Reads its state from the tape
  Misconception: Confuses the machine's state, which it keeps in itself, with the symbols written on the tape.
  Feedback from the catalogue
  The state is the machine’s inner memory, one letter on the display on the head; it is not written on the tape. The symbol is what is in the cell under the head. Every rule joins the two: “in state A, reading 1, write…”. The same symbol can lead to different actions in different states.
Feedback for a right answer
A step is always the same: read one cell, find on the card the rule for the current state and that symbol, then write, move one cell and change state. The machine has no other action.

Worked solution
1. The head reads the symbol in the cell beneath it only.
2. On the rule card, find the row of the current state and the column of the symbol read.
3. The rule says three things: what to write, which way to move one cell, and which state to go to.
The state is kept on the display on the head, not on the tape.
Step 2 of 5
Open this step
Filling the gap
Practice · Predict, then look
Question
The adder started on 111_11 in state A, and after 3 steps the head stands on the gap. A’s rule for a blank cell: write 1, move right, go to B. Which state will the machine be in after the next step?

Correct answer
- Correct B
Setup, choices and feedback
The Scene at this step
Program
Adderfixed
Steps run
3fixed
The machine / No checker
The machine
Choices
- Correct B
- Wrong Still A, because it is still on the first number
  Misconception: Confuses the machine's state, which it keeps in itself, with the symbols written on the tape.
  Feedback from the catalogue
  The state is the machine’s inner memory, one letter on the display on the head; it is not written on the tape. The symbol is what is in the cell under the head. Every rule joins the two: “in state A, reading 1, write…”. The same symbol can lead to different actions in different states.
- Wrong Halted: the gap is filled, and the sum is done
  Feedback
  The tape is now 111111, six 1s: one too many. B and C still have to run to the end and rub one out.
Once the prediction is locked in, the Scene changes
Steps run
4fixed
The Scene then shows: 1 · The state as its row on the rule card: 0 for A, 1 for B, 2 for C; −1 once halted/nodes/machine/outputs/state
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
B: the rule says “go to B”, and the machine does exactly what the rule says. The gap is filled with a 1, and the tape is six strokes in a row.

Worked solution
1. The state is A, and the symbol under the head: a blank.
2. The rule for A and blank: write 1, move right, go to B.
3. After the step: the gap is filled, the head is on the next cell, and the state is B.
The state changes only when a rule says so; here it does.
Step 3 of 5
Open this step
The answer on the tape
Practice · Predict, then look
Question
The adder adds 3 and 2 written as tally strokes, 111_11. How many 1s will be on the tape when the machine halts?

Correct answer
5 ± 0.01
A number prediction counts as right within ± 0.01
Setup, choices and feedback
The Scene at this step
Program
Adderfixed
Steps run
0fixed
The machine / No checker
The machine
Once the prediction is locked in, the Scene changes
Steps run
60fixed
The Scene then shows: 5 · How many 1s are on the tape now/nodes/machine/outputs/ones
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Five: $3 + 2 = 5$ ⁠. The machine fills the gap, which makes six 1s in a row, then C rubs out the last one.

Worked solution
1. In tally strokes a number is its count of 1s: 111 is $3$ ⁠, and 11 is $2$ ⁠.
2. Filling the gap joins them into one row of $3 + 1 + 2 = 6$ ⁠ ones.
3. C rubs out one, leaving $6 - 1 = 5$ ⁠.
Step 4 of 5
Open this step
Counting steps
Practice · Predict, then look
Question
How many steps will the adder take until it halts, the halting step included?

Correct answer
8 ± 0.01
A number prediction counts as right within ± 0.01
Setup, choices and feedback
The Scene at this step
Program
Adderfixed
Steps run
0fixed
The machine / No checker
The machine
Once the prediction is locked in, the Scene changes
Steps run
60fixed
The Scene then shows: 8 · Steps the machine has actually taken (it stops counting once halted)/nodes/machine/outputs/stepsRun
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Eight: three steps over 111, one on the gap, two over 11, one on the blank at the end (a step back and into C), and one that rubs out and halts.

Worked solution
1. A runs right over the three 1s: $3$ ⁠ steps.
2. A fills the gap and goes to B: $1$ ⁠ step.
3. B runs over the two 1s: $2$ ⁠ steps.
4. B reads a blank, moves left and goes to C: $1$ ⁠ step.
5. C rubs out the last 1 and halts: $1$ ⁠ step.
In all $3 + 1 + 2 + 1 + 1 = 8$ ⁠.
Step 5 of 5
Open this step
The third state
Practice · Reach the target
Question
Move Steps run until the display on the head shows state C, and press Check.

Goal
- 2 ± 0.01
  At the start of the step: 0
Setup, choices and feedback
The Scene at this step
Program
Adderfixed
Steps run
0
The machine / No checker
The machine
Read from the Scene at
The state as its row on the rule card: 0 for A, 1 for B, 2 for C; −1 once halted/nodes/machine/outputs/state
One setting that reaches it
Steps run
7
Feedback for a right answer
Step 7: B reached the blank after the number, stepped back and went to C. The machine is in C for one step only; on step 8 it has already halted.

Feedback for a wrong answer
Not yet. Step on one at a time and watch the letter on the display.

Hint
C appears only near the end, after B reaches a blank.

Worked solution
1. A is active for steps 0 to 3, until the gap is filled.
2. B is active from step 4 to 6, crossing 11 and reaching the blank.
3. On the seventh step B steps back and goes to C, so after 7 steps the state is C.

Lesson 2 of 4 · About 25 minutes

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.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
Reading a card
Practice · Predict, then look
Question
The Busy beaver starts on a blank tape, in state A. Its card: A and blank: write 1, right, B. B and blank: leave it blank, right, C. C and blank: write 1, left, C. How many 1s will be on the tape after 4 steps?

Correct answer
3 ± 0.01
A number prediction counts as right within ± 0.01
Setup, choices and feedback
The Scene at this step
Program
Busy beaverfixed
Steps run
0fixed
The machine / No checker
The machine
Once the prediction is locked in, the Scene changes
Steps run
4fixed
The Scene then shows: 3 · How many 1s are on the tape now/nodes/machine/outputs/ones
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Three, 111. Step 1 writes a 1; step 2 skips a cell; step 3 writes in the next and turns back; step 4 fills the cell that was skipped.

Worked solution
1. Step 1: A on blank, writes 1 in cell 0, moves right, B.
2. Step 2: B on blank, leaves cell 1 blank, moves right, C.
3. Step 3: C on blank, writes 1 in cell 2, moves left, stays C.
4. Step 4: C on the blank cell 1, writes 1, moves left. The tape: 111.
Step 2 of 6
Open this step
The busy beaver
Practice · Predict, then look
Question
The busy beaver is a three-state machine chosen because it writes as many 1s as it can and then halts. How many 1s will be on the tape when it halts?

Correct answer
6 ± 0.01
A number prediction counts as right within ± 0.01
Setup, choices and feedback
The Scene at this step
Program
Busy beaverfixed
Steps run
0fixed
The machine / No checker
The machine
Once the prediction is locked in, the Scene changes
Steps run
60fixed
The Scene then shows: 6 · How many 1s are on the tape now/nodes/machine/outputs/ones
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Six, on step 14. No halting machine with three states and two symbols leaves more. For five-state machines the record is 4098 ones after more than 47 million steps; for six states, nobody knows.

Worked solution
1. Run the card step by step, or move Steps run until the machine halts.
2. It halts on step 14, when A’s rule for reading a 1 sends it to halt.
3. On the tape: 111111, six 1s.
Busy beavers grow so fast with the number of states that they cannot be computed in general: this is tied directly to the halting problem.
Step 3 of 6
Open this step
A counter
Practice · Choose
Question
The Counter has three symbols: blank, 0 and 1. Its rule for state A reading 1: write 0, move left, stay in A. What does this rule do, as arithmetic?

Correct answer
- Correct It is the carry of adding 1: 1 + 1 is 0, and 1 carries to the digit on the left
Setup, choices and feedback
The Scene at this step
Program
Counterfixed
Steps run
0
The machine / No checker
The machine
Choices
Shown in a random order.
- Correct It is the carry of adding 1: 1 + 1 is 0, and 1 carries to the digit on the left
- Wrong It erases the number
  Feedback
  It writes 0 only while it crosses 1s. As soon as it reaches a 0 or a blank, a different rule writes a 1 there.
- Wrong It stops the machine
  Feedback
  No rule on the counter’s card leads to halt; it counts for ever.
Feedback for a right answer
As in column addition: adding 1 to a digit 1 gives 0 and a carry to the left. A keeps going left turning every 1 into 0, until it finds a 0 or a blank, and writes 1 there: 011 + 1 = 100.

Worked solution
1. In binary, $1 + 1 = 10$ ⁠: digit 0 and carry 1.
2. The rule writes 0 and moves the head left, to the next digit, without changing state: the carry goes on.
3. When the carry meets a 0 or a blank, A’s rule for those symbols writes 1 and goes to B, which walks back to the right end.
Step 4 of 6
Open this step
Binary on the tape
Practice · Calculate
Question
The Counter has run 30 steps, and the tape shows 1000. What number is that in base ten?

Correct answer
8 ± 0.01
Setup, choices and feedback
The Scene at this step
Program
Counterfixed
Steps run
30fixed
The machine / No checker
The machine
Accepted within
± 0.01
Computed from the Scene at this step’s setting
The 0s and 1s written on the tape, left to right, read as a binary number (blanks skipped)/nodes/machine/outputs/number
Wrong answers it recognises
- 1000 ± 0.01
  Misconception: Reads a binary numeral as if it were decimal: takes 1000 for a thousand, or 10 for ten.
  Feedback from the catalogue
  The digits on the counter’s tape are binary: the place values, right to left, are $1, 2, 4, 8, \ldots$ ⁠, not $1, 10, 100, 1000$ ⁠. So 1000 is $8$ ⁠, and 10 is $2$ ⁠, not ten. The same digits, a different base.
- 4 ± 0.01
  Misconception: Reads a binary numeral as if it were decimal: takes 1000 for a thousand, or 10 for ten.
  Feedback
  Four digits is the length, not the value. The left digit is worth $8$ ⁠.
Feedback for a right answer
$8$ ⁠: in 1000 only the fourth bit from the right is on, and its place value is $2^3 = 8$ ⁠.

Hint
The place value of the fourth digit from the right is $2^3$ ⁠.

Worked solution
1. The binary place values, right to left: $1, 2, 4, 8$ ⁠.
2. In 1000 only the left digit is 1, in the $8$ ⁠ place.
3. So the number is $8$ ⁠.
If you answered $1000$ ⁠, you read the digits as if they were base ten.
Step 5 of 6
Open this step
Counting to five
Practice · Reach the target
Question
Move Steps run until the counter has written the number 5 on its tape, that is 101, and press Check.

Goal
- 5 ± 0.01
  At the start of the step: 0
Setup, choices and feedback
The Scene at this step
Program
Counterfixed
Steps run
0
The machine / No checker
The machine
Read from the Scene at
The 0s and 1s written on the tape, left to right, read as a binary number (blanks skipped)/nodes/machine/outputs/number
One setting that reaches it
Steps run
15
Feedback for a right answer
101 is $4 + 1 = 5$ ⁠. The counter reaches it after 16 steps, and each count takes more steps, because the carry runs further and the number gets longer.

Feedback for a wrong answer
Not yet. Read the tape as a binary number.

Hint
The numbers before 5 in binary: 1, 10, 11, 100.

Worked solution
1. 101: place values $4, 2, 1$ ⁠, with the $4$ ⁠ and $1$ ⁠ digits on: $5$ ⁠.
2. The counter adds 1 each round: 1, 10, 11, 100, 101.
3. Step on until the tape shows 101; that happens on step 16.
Step 6 of 6
Open this step
As powerful as a computer
Practice · Choose
Question
A Turing machine has no registers, no ALU and no memory but its tape. What can it compute, compared with the processor from the previous Unit?

Correct answer
- Correct Anything the processor can compute, given enough tape and time
Setup, choices and feedback
The Scene at this step
Program
Counter
Steps run
0
The machine / No checker
The machine
Choices
Shown in a random order.
- Correct Anything the processor can compute, given enough tape and time
- Wrong Only simple sums like adding tally strokes
  Misconception: Thinks a Turing machine is too simple to compute what a real computer can.
  Feedback from the catalogue
  A Turing machine is slow and clumsy, but given enough tape and time it can compute anything any computer can. That is the Church–Turing thesis, and every attempt to build a “stronger” machine has hit the same limit. The processor from the previous Unit is faster, but it computes nothing the Turing machine cannot.
- Wrong More, because its tape is endless
  Feedback
  A processor can also be given more and more memory. Their power is the same: neither computes anything the other cannot.
Feedback for a right answer
Whatever any computer can compute, a Turing machine can compute too, more slowly. That is what makes it the definition of “computing”: if no Turing machine does something, no computer does either.

Worked solution
1. The processor carries out simple instructions: load, add, store, jump.
2. A Turing machine can imitate each of them: the tape is the memory, and the states are the program.
3. The other way round, a computer can imitate any Turing machine. So their power is equal; what differs is speed.

Lesson 3 of 4 · About 25 minutes

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.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
Halts or not
Practice · Predict, then look
Question
Ping-pong steps right and back, right and back. Will it ever halt, if we let it run 500 steps?

Correct answer
- Correct Never
Setup, choices and feedback
The Scene at this step
Program
Ping-pongfixed
Steps run
20fixed
The machine / No checker
The machine
Choices
- Correct Never
- Wrong In the end, yes, when it runs out of tape
  Feedback
  A Turing machine’s tape has no end, and ping-pong does not need it anyway: it uses only two cells.
- Wrong After 500 steps
  Feedback
  The machine does not know how many steps we asked for; the counter only stops our watching. Its card leads to halt nowhere.
Once the prediction is locked in, the Scene changes
Steps run
500fixed
The Scene then shows: 0 · 1 once the machine has halted, else 0/nodes/machine/outputs/halted
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Never. At step 4 the machine is back in exactly the picture of step 2: the same state, the same cell, the same tape. From there it has to repeat the same path over and over.

Worked solution
1. On step 1 A writes a 1 and moves right to B; on step 2 B moves back left to A.
2. From step 2 on, every two steps the machine is back in exactly the same picture: state A, head on cell 0, the same tape.
3. A deterministic machine that returns to a picture it has been in will repeat what followed, for ever.
Step 2 of 6
Open this step
A proof that it never halts
Practice · Choose
Question
How can we be sure that ping-pong will never halt?

Correct answer
- Correct Its picture, state, head position and tape, repeats exactly, so it will go round the same path for ever
Setup, choices and feedback
The Scene at this step
Program
Ping-pong
Steps run
20
The machine / No checker
The machine
Choices
Shown in a random order.
- Correct Its picture, state, head position and tape, repeats exactly, so it will go round the same path for ever
- Wrong It ran 500 steps without halting
  Misconception: Concludes that a machine that has run a long time without halting must run for ever.
  Feedback from the catalogue
  A long run proves nothing. A machine can run a million steps and halt on the million-and-first. The five-state busy beaver halts only after more than 47 million steps. About ping-pong you can be sure for a different reason: its picture repeats exactly, and a machine that comes back to a picture it has been in will go round the same path for ever.
- Wrong It has only two states
  Feedback
  Two-state machines can halt too. A small number of states says nothing by itself.
Feedback for a right answer
A repeating picture is a proof. A long run is only evidence: a machine can run a million steps and halt on the next.

Worked solution
1. The machine’s next step depends only on its state, the symbol under the head, and the card.
2. If the whole picture repeats, everything that followed it will happen again, and again.
3. In ping-pong the picture of step 2 comes back at step 4, so it goes round for ever.
The counter never repeats, yet it does not halt either: no rule on its card leads to halt.
Step 3 of 6
Open this step
A machine that has halted
Practice · Calculate
Question
Busy beaver, with Steps run at 500. The machine halted long ago. How many steps did it actually take?

Correct answer
14 ± 0.01
Setup, choices and feedback
The Scene at this step
Program
Busy beaverfixed
Steps run
500fixed
The machine / No checker
The machine
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Steps the machine has actually taken (it stops counting once halted)/nodes/machine/outputs/stepsRun
Wrong answers it recognises
- 500 ± 0.01
  Misconception: Concludes that a machine that has run a long time without halting must run for ever.
  Feedback
  A machine that has halted does not run on; 500 is only the number we asked for.
Feedback for a right answer
14: a machine that has halted stops counting. The Scene’s counter can ask for 500, but after halting there is no rule to apply.

Worked solution
1. The busy beaver halts when A’s rule for reading a 1 sends it to halt, on step 14.
2. The halting state has no row on the card, so there are no more steps.
3. The steps actually taken: 14.
If you answered $500$ ⁠, you counted the steps we asked for, not the ones the machine took.
Step 4 of 6
Open this step
A halt checker
Practice · Choose
Question
Look inside at Halt checker: H is a sealed cabinet that takes a rule card and lights HALTS or RUNS FOREVER. What would H have to do to be a real halt checker?

Correct answer
- Correct Answer correctly for every card, and always finish
Setup, choices and feedback
The Scene at this step
Program
Adder
Steps run
0
The machine / No checker
Halt checker
Choices
Shown in a random order.
- Correct Answer correctly for every card, and always finish
- Wrong Answer correctly for the four cards in the Scene
  Misconception: Takes the halting problem to mean that you can never tell whether any particular program halts.
  Feedback from the catalogue
  The halting problem says there is no single method that works on every program. For many particular programs the answer is easy: the adder halts on step 8, and ping-pong repeats itself, so it never halts. What is impossible is a checker that is always right, on any rule card it is handed.
- Wrong Run the machine and wait to see
  Misconception: Concludes that a machine that has run a long time without halting must run for ever.
  Feedback from the catalogue
  A long run proves nothing. A machine can run a million steps and halt on the million-and-first. The five-state busy beaver halts only after more than 47 million steps. About ping-pong you can be sure for a different reason: its picture repeats exactly, and a machine that comes back to a picture it has been in will go round the same path for ever.
Feedback for a right answer
The four cards here are easy to check, and that is what H does in the Scene. Turing’s question is about a general checker: one machine that answers correctly on any card it is given, and always finishes.

Worked solution
1. A checker that only runs and waits never finishes on a machine that runs for ever, so it gives no answer.
2. A checker that works only on a few known cards does not answer the general question.
3. A real halt checker: for every card, a correct answer, in finite time.
Step 5 of 6
Open this step
Turing's argument
Practice · Choose
Question
Look inside at No checker: D takes a card, asks H what that machine will do when fed its own card, and does the opposite: if H says HALTS, D runs for ever; if H says RUNS FOREVER, D halts. What happens when D is given its own card?

Correct answer
- Correct Whatever H answers is wrong, so H cannot exist
Setup, choices and feedback
The Scene at this step
Program
Adder
Steps run
0
The machine / No checker
No checker
Choices
Shown in a random order.
- Correct Whatever H answers is wrong, so H cannot exist
- Wrong D runs for ever, and that is the whole answer
  Feedback
  If D runs for ever, that is because H said HALTS, and then H was wrong. Each of the two possibilities ends with H wrong.
- Wrong A faster computer is needed to find out
  Misconception: Thinks the halting problem is a matter of speed, so a fast enough computer could decide it.
  Feedback from the catalogue
  The halting problem has nothing to do with speed. Turing’s proof shows that no algorithm answers correctly for every program, however long it is allowed: against any checker anyone builds, you can build D, which does the opposite of what the checker says about it. A faster computer only reaches the same contradiction sooner.
- Wrong Nobody knows yet; maybe mathematicians will solve it
  Misconception: Thinks a universal halt checker simply has not been written yet, rather than being proved impossible.
  Feedback from the catalogue
  It is not that the program has not been found yet: it has been proved that it cannot exist. If H existed, you could build D from it and feed D its own card; every answer H gave would then be wrong. Like “this sentence is false”, the question turns back on itself.
Feedback for a right answer
If H says D halts, D runs for ever; if H says it runs for ever, it halts. Either way H is wrong, so a checker that is always right cannot exist. That is the halting problem: Turing, 1936.

Worked solution
1. Suppose H exists and is always right.
2. If H answers “D halts”, D does the opposite and runs for ever: H was wrong.
3. If H answers “D runs for ever”, D halts: H was wrong again.
4. Every answer contradicts the assumption, so the assumption is false: there is no such H.
This is a proof, not a technical difficulty: no speed and no amount of time will help.
Step 6 of 6
Open this step
What it means
Practice · Choose
Question
What does the halting problem not say?

Correct answer
- Correct That you can never tell whether any program halts
Setup, choices and feedback
The Scene at this step
Program
Counter
Steps run
0
The machine / No checker
No checker
Choices
Shown in a random order.
- Correct That you can never tell whether any program halts
- Wrong That no single algorithm answers correctly for every program
  Feedback
  That is exactly what it says.
- Wrong That there are well-defined questions no computer can solve
  Feedback
  It says that too: the halting question is well defined, and still no algorithm always answers it.
Feedback for a right answer
For many particular programs the answer is easy, as for the four machines here. What is impossible is one method that always works.

Worked solution
1. The proof builds, for any proposed checker, one machine it gets wrong: D.
2. It says nothing against checking the adder, ping-pong or any other particular program.
3. So “you can never tell about any program” is false; the true claim is “no checker is always right”.

Lesson 4 of 4 · About 25 minutes

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.

Open the lesson

The 8 steps and their answers

Step 1 of 8
Open this step
The rules
Practice · Choose
Question
Under the Game of Life’s rules, Born with 3 and Survives with 2 or 3. A live cell with four live neighbours: what happens to it next generation?

Correct answer
- Correct It dies
Setup, choices and feedback
The Scene at this step
Born with
3 (Life)
Survives with
2 or 3 (Life)
Start
R-pentomino
Cells / Patterns
Neighbours
Other settings
First generation/nodes/board/props/firstGeneration = 0
Choices
Shown in a random order.
- Correct It dies
- Wrong It survives, because it has more than two
  Feedback
  It survives only with exactly 2 or 3. With four or more it dies, “of overcrowding”.
- Wrong It gives birth to a new cell beside it
  Feedback
  A cell is born only in a dead cell with exactly three live neighbours. Live cells do not give birth; a birth depends only on the empty cell’s own count.
Feedback for a right answer
Four neighbours are too many: only 2 or 3 keep a cell alive. With 0 or 1 it dies “of loneliness”, and with 4 or more “of overcrowding”.

Worked solution
1. The cell is alive, so the survival rule applies, not the birth rule.
2. It survives only if its count of live neighbours is 2 or 3.
3. It has 4, so next generation it dies.
Step 2 of 8
Open this step
One generation
Practice · Predict, then look
Question
Start is R-pentomino: five live cells, and Look inside at Neighbours shows how many live neighbours each cell has. How many live cells will there be in generation 1?

Correct answer
6 ± 0.01
A number prediction counts as right within ± 0.01
Setup, choices and feedback
The Scene at this step
Born with
3 (Life)fixed
Survives with
2 or 3 (Life)fixed
Start
R-pentominofixed
Cells / Patterns
Neighboursfixed
Other settings
First generation/nodes/board/props/firstGeneration = 0
Once the prediction is locked in, the Scene changes
Other settings
First generation/nodes/board/props/firstGeneration = 1
The Scene then shows: 6 · Live cells in view at firstGeneration/nodes/board/outputs/population
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Six: one live cell dies, the one in the middle, with four neighbours, and two empty cells are born, each with three. $5 - 1 + 2 = 6$ ⁠.

Worked solution
1. For each of the five live cells count neighbours: the middle cell has 4, the rest 2 or 3. The middle one dies; four survive.
2. For the empty cells around: two of them, on the left, have exactly 3 live neighbours, and are born.
3. In generation 1: $4 + 2 = 6$ ⁠ live cells.
All cells update at once, by the counts of the current generation.
Step 3 of 8
Open this step
Counting births
Practice · Calculate
Question
In the same R-pentomino, at generation 0: in how many empty cells will new cells be born on the way to generation 1?

Correct answer
2 ± 0.01
Setup, choices and feedback
The Scene at this step
Born with
3 (Life)fixed
Survives with
2 or 3 (Life)fixed
Start
R-pentominofixed
Cells / Patterns
Neighboursfixed
Other settings
First generation/nodes/board/props/firstGeneration = 0
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Dead cells in view that are born in the next generation/nodes/board/outputs/births
Wrong answers it recognises
- 0 ± 0.01
  Misconception: Counts only the four neighbours above, below and to the sides of a cell, leaving out the four diagonals.
  Feedback from the catalogue
  In the Game of Life every cell has eight neighbours: four at the sides and four on the diagonals, like the squares around a king in chess. In the R-pentomino, the empty cell at the top left touches three live cells only when the diagonal is counted, so it is born.
Feedback for a right answer
Two: the empty cell left of the top row and the empty cell left of the bottom row. Each has exactly three live neighbours, counting the diagonals too.

Hint
At Neighbours the numbers in the empty cells are their counts.

Worked solution
1. The shape, top to bottom: .OO, OO., .O..
2. The empty cell at the top left has live neighbours to its right, below it, and diagonally below right: three. It is born.
3. The empty cell at the bottom left: above it, to its right, and diagonally above right: three. It is born too.
4. Every other empty cell has fewer or more than three.
If you answered $0$ ⁠, you counted only four neighbours per cell; the diagonals count too.
Step 4 of 8
Open this step
Shapes that move
Practice · Predict, then look
Question
Start is Pattern zoo: a block, blinkers, a pulsar, and at the lower right a glider, five cells shaped like an arrow. What will the glider do?

Correct answer
- Correct Travel diagonally across the board, coming back to the same shape every four generations
Setup, choices and feedback
The Scene at this step
Born with
3 (Life)fixed
Survives with
2 or 3 (Life)fixed
Start
Pattern zoofixed
Cells / Patterns
Cells
Other settings
First generation/nodes/board/props/firstGeneration = 0
Choices
- Correct Travel diagonally across the board, coming back to the same shape every four generations
- Wrong Stay where it is, like the block
  Feedback
  The block is still because every cell in it has exactly three neighbours and no empty cell around it is born. In the glider, cells die and are born every generation.
- Wrong Die, because some of its cells have only one neighbour
  Feedback
  One cell dies, but each generation new cells are born beside it. The shape as a whole survives and moves.
Once the prediction is locked in, the Scene changes
Cells / Patterns
Patterns
Other settings
First generation/nodes/board/props/firstGeneration = 40
The Scene then shows: 2 · Groups that move across the board, the gun's gliders included (needs firstGeneration ≥ 30)/nodes/board/outputs/spaceships
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
It moves: after four generations the shape returns, one cell along the diagonal. No cell moves; cells die on one side and are born on the other, and the shape creeps. At Patterns the glider is coloured as a spaceship.

Worked solution
1. Each generation cells die at the back of the glider and are born at the front.
2. After four generations the shape is the same as at the start, shifted one cell right and one cell forward.
3. So it carries on diagonally, four generations per step, until it meets something.
Step 5 of 8
Open this step
Still or blinking
Practice · Calculate
Question
Look inside at Patterns, at generation 40 of the zoo: each group is coloured by what it does. How many of the groups are still lifes, ones that do not change at all?

Correct answer
4 ± 0.01
Setup, choices and feedback
The Scene at this step
Born with
3 (Life)fixed
Survives with
2 or 3 (Life)fixed
Start
Pattern zoofixed
Cells / Patterns
Patternsfixed
Other settings
First generation/nodes/board/props/firstGeneration = 40
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Groups of cells that stay exactly the same (needs firstGeneration ≥ 30, else 0)/nodes/board/outputs/stillLifes
Wrong answers it recognises
- 9 ± 0.01
  Misconception: Counts an oscillator, which keeps changing and comes back, as a still life.
  Feedback from the catalogue
  A still life does not change at all, from generation to generation: block, beehive, loaf, boat. An oscillator changes every generation and comes back to its first shape after a few, like the blinker, which flips between a standing line and a lying one. At Patterns they are coloured differently.
Feedback for a right answer
Four: the block, the beehive, the loaf and the boat, in the back row. The blinker, toad, beacon, pulsar and pentadecathlon are oscillators: they change and come back.

Hint
Compare the colours with the key: still, oscillator, spaceship.

Worked solution
1. A still life: every live cell in it survives (2 or 3 neighbours), and no empty cell around it is born.
2. The back row has four of these: block, beehive, loaf, boat.
3. The oscillators return to their shape only after a few generations, so they are not still.
If you answered $9$ ⁠, you also counted the five oscillators.
Step 6 of 8
Open this step
Changing the rule
Practice · Predict, then look
Question
Survives with will change to Never: every live cell dies next generation unless it is born again. What will happen to the random soup?

Correct answer
- Correct Everything will die, and the board will empty
Setup, choices and feedback
The Scene at this step
Born with
3 (Life)fixed
Survives with
2 or 3 (Life)fixed
Start
Random soupfixed
Cells / Patterns
Cells
Other settings
First generation/nodes/board/props/firstGeneration = 30
Choices
- Correct Everything will die, and the board will empty
- Wrong The board will boil, because cells keep being born
  Feedback
  Births on 3 alone, with no survival at all, cannot last: groups that are born die at once, and fewer and fewer births are left.
- Wrong About the same as in the Game of Life
  Misconception: Assumes complex behaviour can only come from complex rules.
  Feedback from the catalogue
  The Game of Life’s rules fit in one sentence, and still they give rise to gliders, guns that fire gliders, and even a whole computer built from cells: it has been proved that Life can compute anything a Turing machine can. A Turing machine itself is a few simple rules too. The complexity comes from repeating a simple rule an enormous number of times, not from the rule.
Once the prediction is locked in, the Scene changes
Survives with
Neverfixed
The Scene then shows: 1 · How the rule treats a random soup: 1 dies out, 2 freezes into a few still shapes, 3 grows into a frozen crust, 4 boils for ever, 5 shapes last, move and collide/nodes/board/outputs/regime
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
The board empties. One small change to the rule, and nothing is left of the Game of Life’s rich world. With another Survives with setting the board would boil or freeze: the behaviour is very sensitive to the rule.

Worked solution
1. With no survival, every live cell dies after one generation.
2. A cell is born only in an empty cell with exactly three live neighbours, and each generation there are fewer live cells to give birth.
3. Within a few generations not a cell is left.
Step 7 of 8
Open this step
A rule that freezes
Practice · Reach the target
Question
Find a rule, with Born with and Survives with, under which the random soup freezes within a hundred generations into a few still shapes and blinkers, and press Check.

Goal
- 2 ± 0.01
  At the start of the step: 5
Setup, choices and feedback
The Scene at this step
Born with
3 (Life)
Survives with
2 or 3 (Life)
Start
Random soupfixed
Cells / Patterns
Cells
Other settings
First generation/nodes/board/props/firstGeneration = 30
Read from the Scene at
How the rule treats a random soup: 1 dies out, 2 freezes into a few still shapes, 3 grows into a frozen crust, 4 boils for ever, 5 shapes last, move and collide/nodes/board/outputs/regime
One setting that reaches it
Born with
4
Survives with
2 or 3 (Life)
Feedback for a right answer
Born with 4, Survives with 2 or 3: birth is too hard, so shapes cannot grow and move, and the board settles fast. Only one combination out of sixteen gives this.

Feedback for a wrong answer
Not yet. A rule that freezes needs harder births.

Hint
Keep Survives with as in the Game of Life, and change Born with.

Worked solution
1. Life is balanced: enough births for shapes to move, and enough death that the board does not fill up.
2. For the board to freeze it needs fewer births: Born with 4 instead of 3.
3. With Life’s survival on 2 or 3, what remains settles into still shapes.
With Survives with Never everything dies, and with Always or 1 to 5 the board turns into a dense frozen crust.
Step 8 of 8
Open this step
A computer made of cells
Practice · Choose
Question
The Game of Life’s rule fits in one sentence. What has been proved to be buildable from it?

Correct answer
- Correct A whole computer: Life can compute anything a Turing machine can
Setup, choices and feedback
The Scene at this step
Born with
3 (Life)
Survives with
2 or 3 (Life)
Start
Glider gun
Cells / Patterns
Patterns
Choices
Shown in a random order.
- Correct A whole computer: Life can compute anything a Turing machine can
- Wrong Only simple shapes, because the rule is simple
  Misconception: Assumes complex behaviour can only come from complex rules.
  Feedback from the catalogue
  The Game of Life’s rules fit in one sentence, and still they give rise to gliders, guns that fire gliders, and even a whole computer built from cells: it has been proved that Life can compute anything a Turing machine can. A Turing machine itself is a few simple rules too. The complexity comes from repeating a simple rule an enormous number of times, not from the rule.
- Wrong Only random noise
  Feedback
  The Game of Life is entirely deterministic: the same start always gives the same board. Gliders, guns and logic gates have been built from it.
Feedback for a right answer
Gliders can carry bits, and a glider gun is a clock. From these people have built logic gates, memory, and even a whole Turing machine out of cells. So the halting problem applies to the Game of Life too: there is no method that can always say whether a pattern will die out in the end.

Worked solution
1. A glider gun fires a glider every thirty generations: a stream of bits.
2. Collisions between gliders can cancel or pass them: these are logic gates.
3. From gates and memory you build a computer, so the Game of Life is Turing complete.
The complexity is not in the rule; it comes from repeating it millions of times.

Across the unit · 11 misconceptions

Misconception catalogue

Each common mistake this unit recognises, in a few words. Open one for what the learner reads when an answer matches it, and where it is asked.

Index

A Turing machine

Read, write, move

Question

Correct answer

The Scene at this step

Choices

Worked solution

Filling the gap

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Worked solution

The answer on the tape

Question

Correct answer

The Scene at this step

Once the prediction is locked in, the Scene changes

Worked solution

Counting steps

Question

Correct answer

The Scene at this step

Once the prediction is locked in, the Scene changes

Worked solution

The third state

Question

Goal

The Scene at this step

One setting that reaches it

Hint

Worked solution

State tables

Reading a card

Question

Correct answer

The Scene at this step

Once the prediction is locked in, the Scene changes

Worked solution

The busy beaver

Question

Correct answer

The Scene at this step

Once the prediction is locked in, the Scene changes

Worked solution

A counter

Question

Correct answer

The Scene at this step

Choices

Worked solution

Binary on the tape

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

Counting to five

Question

Goal

The Scene at this step

One setting that reaches it

Hint

Worked solution

As powerful as a computer

Question

Correct answer

The Scene at this step

Choices

Worked solution

The halting problem

Halts or not

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Worked solution