Build a computer from two instructions
Homework for after the workshop, or for a class: start with the counter machine’s two step cards and build, one level at a time, the instructions a real processor has. Try each one before opening the solution. Every solution here has been checked by running it.
Level 0 · Two instructions
Bins are numbered or named; a bin’s number is how many tokens it holds. Every line is one step card, numbered from the top.
take b, s, e take a token from bin b: got one → line s, bin empty → line e add b, n put a token in bin b, then go to line n
Lines can have labels, like top:, so you can jump to them by name. Three special targets: next (the following line), stop, and, inside a new instruction, done (finished: carry on after it). Each new instruction below is written only with ones defined before it. An assembler, the program a computer uses for exactly this job, replaces each new instruction with the take and add lines it stands for.
Level 1 · Jumping and clearing
goto L
Jump to a label without changing anything. You may keep one bin, Z, that is always empty. Why can’t you just use any bin?
Solution
goto $L take Z, $L, $L
clear b
Empty a bin.
Solution
clear $b top: take $b, top, done
ifzero b, L
If bin b is empty, jump to L. Otherwise carry on, with b unchanged.
Solution
ifzero $b, $L take $b, back, $L back: add $b, done
Level 2 · Moving numbers
move a, b
Pour all of a into b. Afterwards a is empty.
Solution
move $a, $b top: take $a, put, done put: add $b, top
copy a, b
Add a copy of a to b, leaving a as it was. You may use a private scratch bin.
Solution
copy $a, $b (scratch: $t) top: take $a, p1, back p1: add $b, p2 p2: add $t, top back: move $t, $a
Level 3 · Arithmetic and comparing
addto a, b
a = a + b, keeping b.
Solution
addto $a, $b copy $b, $a
sub a, b
a = a − b, keeping b. If b is bigger, a ends at 0.
Solution
sub $a, $b (scratch: $t) top: take $b, p1, back p1: add $t, p2 p2: take $a, top, top back: move $t, $b
iflt a, b, L
If a is less than b, jump to L. Leave a and b unchanged.
Solution
iflt $a, $b, $L (scratch: $x, $y) copy $a, $x copy $b, $y loop: take $x, p1, xout p1: take $y, loop, no xout: take $y, yes, no yes: clear $x clear $y goto $L no: clear $x clear $y
Level 4 · Multiplying and dividing
mul c, a, b
c = c + a × b, keeping a and b.
Solution
mul $c, $a, $b (scratch: $t) copy $a, $t top: take $t, p1, done p1: addto $c, $b goto top
divmod a, b, q
Divide a by b (b not 0): add the quotient to q and leave the remainder in a.
Solution
divmod $a, $b, $q top: iflt $a, $b, done sub $a, $b add $q, top
Level 5 · Real algorithms
swap a, b
Exchange the contents of a and b.
Solution
swap $a, $b (scratch: $t) move $a, $t move $b, $a move $t, $b
gcd a, b
Euclid’s algorithm: leave the greatest common divisor of a and b in a. Hint: replace a by the remainder of a ÷ b, swap, and repeat until b is 0.
Solution
gcd $a, $b (scratch: $q) top: ifzero $b, done divmod $a, $b, $q clear $q swap $a, $b goto top
Five lines, which the assembler turns into 34 cards. The hand-written Euclid program in the workshop needs only 10: each new instruction brings its own careful steps. Real compilers face the same trade-off between programs that are easy to write and programs that are small and fast.
Level 6 · Memory with numbered cells
getcell m, i, r
Pack many small numbers into one bin as the digits of one big number: 4207 holds 4, 2, 0 and 7. Put digit number i of bin m (counting from 0 on the right) into r.
Solution
getcell $m, $i, $r (scratch: $t, $j, $ten, $q) copy $m, $t copy $i, $j set $ten, 10 top: take $j, shift, last shift: divmod $t, $ten, $q clear $t move $q, $t goto top last: divmod $t, $ten, $q clear $q clear $ten move $t, $r
Writing a cell works the same way: subtract the old digit times 10i, add the new one. With numbered cells you have arrays, lists and pointers: everything a real computer’s memory offers, just very slowly. Reading one digit of 4207 takes about 5.4 million moves.
Level 7 · Subroutines that return
So far every new instruction is copied in wherever it is used. A real program keeps one copy of a subroutine and jumps to it from different places. To get back, the caller first puts a return number in bin R: 1 token for “come back to place 1”, 2 for place 2. The subroutine ends by counting R with take, which empties R and jumps to the right place. It also needs its input in an agreed bin, here x: that agreement is a calling convention.
move a, x add R, call1 call1: goto pour back1: move b, x add R, p2 p2: add R, call2 call2: goto pour back2: move total, out take Z, stop, stop pour: move x, total ret: take R, r1, stop r1: take R, r2, back1 r2: take R, stop, back2
That is what a processor’s CALL and RETURN do: CALL saves a return address and jumps; RETURN jumps back to it. The return address is just another number in memory. With more return places the counting chain gets longer; with the arithmetic from Level 4 it can be done without a long chain. Try it: make mul share one copy of addto.
Level 8 · A whole processor
A real processor runs one loop forever: fetch the next instruction from memory, decode which one it is, carry it out. Number its instructions (1 LOAD, 2 STORE, 3 ADD, 4 JUMP-IF-ZERO, …) and store a program as numbered cells (Level 6). Keep a bin for the program counter. The loop is: getcell the instruction at the program counter; use a chain of ifzero tests to find which instruction it is; run the matching subroutine; add one to the program counter; repeat. Every piece is something you have already built.
That loop is a program for the counter machine that runs any program written for the processor. So the counter machine can do anything that processor can: a spreadsheet, a web browser, an AI model. It would need more tokens than there are grains of sand and take longer than the age of the universe, but nothing more is needed. That is Turing completeness. Marvin Minsky proved in 1961 that even two bins are enough, if you pack everything into one enormous number.