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.
Step 1 of 6 · Reading a card
Step 1 of 6
Reading a card
The rule card is a state table: the whole program, and nothing else. To know what the machine will do, find the row of its state and the column of the symbol under the head, and read the square: what to write, which way to move and which state to go to.
Program is set to Busy beaver, and the tape is completely blank. Follow the card in your head, step by step.
Step 2 of 6
The busy beaver
You can ask: of all the machines with three states and two symbols that halt in the end, which writes the most 1s on a blank tape? The winner is called the busy beaver, and it is the machine in the Scene. It scurries back and forth, filling holes and widening the row, then halts.
Step 3 of 6
A counter
The Counter has three symbols, blank, 0 and 1, and two states. A adds 1 to the number ending under the head, and B walks back to its right end. Look at A’s row on the card.
Step 4 of 6
Binary on the tape
Each round of A and B makes the number on the tape one bigger: 1, 10, 11, 100… While the carry runs left, the tape shows for a moment a number in the middle of the sum.
Step 5 of 6
Counting to five
Now move Steps run yourself.
Step 6 of 6
As powerful as a computer
A machine like this looks able to do only small things: add strokes, count. But Turing showed that a universal machine can be built, one that takes another machine’s card on its tape and runs it. That is exactly how a computer works: a program is data in memory, as on the chip in the previous Unit.
Loading the interactive version…
Loading the interactive version…
Each step sets up the Scene for you, and a control marked “fixed” stays put for that step.
Practice · Predict, then look
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?
Practice · Predict, then look
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?
Practice · Predict, then look
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?
Practice · Predict, then look
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?
Practice · Choose
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?
Practice · Choose
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?
Practice · Calculate
The Counter has run 30 steps, and the tape shows 1000. What number is that in base ten?
Practice · Calculate
The Counter has run 30 steps, and the tape shows 1000. What number is that in base ten?
Practice · Reach the target
Move Steps run until the counter has written the number 5 on its tape, that is 101, and press Check.
Practice · Reach the target
Move Steps run until the counter has written the number 5 on its tape, that is 101, and press Check.
Practice · Choose
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?
Practice · Choose
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?
Lesson complete. Every practice question here is done.