In which the reader is made acquainted with a most singular Algebra, wherein there are but two numbers, and the sum of one and one is nothing at all.
Being an account of Mr. Boole’s Laws of Thought, set down in the year 1854 by a Professor of Queen’s College, Cork; of young Mr. Shannon’s relays, and the little gates that came of them; and of how one humble operation — the adding of One to a number — may be performed in three several fashions: by Logic, by Wire, and by the Machine of Mr. Turing.
Wherein the reader is required to lend a thumb, and to consult a partner upon sundry occasions; wherein it is demonstrated that the Carry may very conveniently be kept upon the thumb of the other hand; and wherein, at the last, Logic, Circuit and Machine are discovered to be one and the same contrivance in three different coats.
“We may say that thinking is essentially the activity of operating with signs.”
— Ludwig Wittgenstein, The Blue Book (1933–1934), p. 6 of the common...
It is misleading then to talk of thinking as of a “mental activity”. We may say that thinking is essentially the activity of operating with signs. This activity is p...
Question of the day: why does counting in binary work — and what is a machine doing when it counts?You already know how: fold every 1 down, carry to the left, raise the fi...
In pairs. One of you counts in binary on one hand, from 0 up to 11. The other watches and says “stop!” at the first mistake.Swap. Then count from 0 1 1 1 (7) —...
1854: George Boole, professor at Queen’s College Cork, publishes An Investigation of the Laws of Thought.His claim: reasoning itself can be calculated — like algebra...
XOR (exclusive or): true if the two inputs differ — one thumb up, not both.aba XOR b000011101110Note the last row: 1 XOR 1 = 0. Remember it — it will carry the whole...
In pairs. Take turns reading these sentences aloud; your partner decides OR or XOR and defends the choice with one sentence about the situation:• “You can pay by card...
In pairs. Each of you hides a thumb behind your back (up = 1, down = 0) and shows it on three. The teacher calls the gate:abANDORXORNAND000001010111100111111...
Boole discovered that these operations obey laws, like numbers do:lawin wordsa AND 1 = aAND with 1 changes nothinga AND 0 = 0AND with 0 kills everythinga OR 0 = aOR with 0 chang...
Why is it called algebra? Because the operations behave like arithmetic on 0 and 1:AND is multiplication: a · b. NOT is 1 − a.XOR is addition — but one that f...
1937: Claude Shannon, 21, writes his master’s thesis at MIT: A Symbolic Analysis of Relay and Switching Circuits.His discovery: electrical switches obey Boole’s alge...
One gate is enough to build all the others: NAND (NOT(a AND b)), Sheffer 1913.NOT a = a NAND aa AND b = NOT (a NAND b) — i.e. a NAND followed by a NAND with itself.a OR b ...
In pairs. One of you is the architect, the other the inspector.Architect: on paper, draw XOR using only NAND gates (hint: four NANDs suffice; one of them is shared).Inspector: f...
Put the two observations together: to add two bits b and c you need exactly two gates.sum = b XOR c carry = b AND cThis tiny circuit is called the half-adder. All arithme...
Our algorithm increment is not a special case: to add 1, put a carry of 1 into the lowest position, then let every position run a half-adder.c0 = 1 (that is the “+1”...
In pairs. Four numbers: 0101, 0111, 1011, 1111. Increment each using only the two formulas — no counting.Split the labour like a circuit: one of you computes every XOR, th...
Build the circuit literally: one half-adder per bit, the carry wired from each to its left neighbour.It is called a ripple-carry circuit: change the input and the carry ripples ...
Now the other idea. Do not build five adders. Build one and walk it along the number.Each step it reads one bit from a tape, computes XOR and AND, writes the result, and moves o...
Look again at the rule table of our Turing machine — the one from the Alan session — and write the state as a bit: CARRY = 1, HALT = 0.state creads bwritesnext state...
Alone, then compare. Right hand = tape (thumb is the lowest bit). Left thumb = the state c.Raise your left thumb: you are adding 1. Now walk along the right hand, thumb to littl...
In pairs. Two roles. TAPE: write six cells on paper, e.g. 0 1 0 1 1 1, and cover all but the cell under the head with your hand. MACHINE: you have only a rule card (the table of...
In pairs. First: the forgetful machine. It has no thumb: at every cell it behaves as if c = 1 (it always flips the bit and always moves on).Run it on 0101. What should the answe...
Logic (Boole 1854)Wire (Shannon 1937)Machine (Turing 1936)what it isformulascircuit of gatestape, head, statessum digitout = b XOR cXOR gatewrite rulecarryc′ = b AND cAND ...
Every neural network, every language model, runs on chips made of billions of gates just like the ones you drew today — XOR, AND, NAND, wired by algebra and clocked throug...
In pairs, three minutes: explain to each other, without notes, why the sum digit is XOR and the carry is AND.Then answer the question of the day in two sentences: why does count...