Part I · Chapter 1 · The very basics · Section 1 of 3

Zeros and ones

Maksim Gurchenkov

Any modern computer is “just” zeros and ones, plus mathematical operations on them and our conventions about what it all means.

In 1703, Leibniz1 described the binary number system2: any number can be written using only zeros and ones. For example, 42 becomes 101010, and 7 becomes 111. Nothing is lost. These are the same numbers, just in a different alphabet. And if numbers can be written this way, they can also be added and multiplied right in this notation.

42 → 101010
7 → 111
42 × 7 → 101010 × 111 = 100100110 → 294

Then, in 1854, George Boole3 showed that reasoning, too, can be reduced to just three operations, AND, OR and NOT, on two values: TRUE and FALSE. It seems like too little, but in fact these bricks can build any condition and any line of reasoning, however complex. Today this is called Boolean logic4.

take an umbrella = rain AND leaving home

rain = TRUE, leaving = TRUE    →   TRUE AND TRUE  = TRUE    →   take an umbrella
rain = TRUE, leaving = FALSE   →   TRUE AND FALSE = FALSE   →   do NOT take an umbrella

So any math, any logic, any reasoning and any computation can be written with the same set of 0s and 1s and just three operations on them. And that is simply incredible.

Logic turns into math:

TRUE  is 1
FALSE is 0

NOT is subtraction from 1
    NOT FALSE = 1 − 0 = 1 = TRUE
    NOT TRUE  = 1 − 1 = 0 = FALSE

AND is multiplication
    FALSE AND FALSE = 0 × 0 = 0 = FALSE
    TRUE  AND FALSE = 1 × 0 = 0 = FALSE
    TRUE  AND TRUE  = 1 × 1 = 1 = TRUE

OR is addition with a correction
    FALSE OR FALSE = 0 + 0 − 0×0 = 0 = FALSE
    TRUE  OR FALSE = 1 + 0 − 1×0 = 1 = TRUE
    TRUE  OR TRUE  = 1 + 1 − 1×1 = 1 = TRUE

And the other way around, all of math is built from logic: addition
breaks down into a chain of AND, OR and NOT, multiplication is built
from additions, and all the rest of arithmetic is built from those.

And then, in 1937, Claude Shannon5 noticed that both 0 and 1 themselves and all three operations can be implemented in electrical circuits. A closed relay is one, an open relay is zero. Two relays in series give you AND: current flows only if both are closed. Two in parallel give you OR: either one is enough. And a relay that opens the circuit when a signal arrives gives you NOT. Nothing else is needed: if a circuit can do these three operations on zeros and ones, it can both calculate and reason! This was the master’s thesis of a 21-year-old student, and it’s called one of the most important works of the twentieth century.

Now it was possible to build electrical circuits for any logic and any computation. But such circuits have a built-in limitation: each one can do exactly what has been wired into it. One circuit adds, another compares, and a new task needs a new circuit. The famous ENIAC, the giant computing machine of those years, worked exactly like this: to switch tasks, engineers spent days replugging cables and flipping switches.

Amazingly, by then the answer already existed, though only on paper. Back in 1936, before any big machines, Alan Turing proved6 that a single universal machine is possible: it will carry out any computation if you give it the right instructions as input. All that was left was to turn the theory into hardware.

And in 1945, von Neumann7 described exactly how to build it. The idea is beautiful: if any numbers and any logic can be written as zeros and ones, then the steps of a computation themselves can be encoded as numbers and put in memory next to the data. The processor takes instruction after instruction from memory and executes them. Need a different task? Don’t resolder the hardware or switch cables by hand, just load different numbers into memory. These sets of encoded instructions came to be called programs. The same machine calculates payroll, draws pictures and runs neural networks. That is what a computer is, and the von Neumann architecture8 still underlies every standard computer in the world.

From binary numbers and Boolean logic to relays and the stored-program computer

The machine itself doesn’t know what its zeros and ones mean. We are the ones who agreed that these bits are processor instructions, these are letters, these are the colors of pixels on a screen, these are keystrokes, and those over there are the sound in your headphones. The same set of bits means different things depending on the convention it’s read by. Zeros and ones have no meaning in themselves. Meaning comes from our interpretation.

Leibniz:      any number can be written with zeros and ones
                 ↓
Boole:        zeros and ones with operations express any logic
                 ↓
Shannon:      hardware can do these operations, circuits can be built
                 ↓
von Neumann:  a program is also just numbers in memory,
              one circuit for any task

And so it turns out that any modern computer is “just” zeros and ones, plus mathematical operations on them and our conventions about what it all means. And if you want to walk this whole path with your own hands, from logic with zeros and ones to a working computer, I recommend Charles Petzold’s book “Code”9 and the Nand2Tetris10 course, where you build a computer from scratch out of a single logical operation.

From binary computation to matrices and neurons

Sources

  1. Leibniz, “Explication de l’Arithmétique Binaire,” 1703—the first description of binary arithmetic. — https://web.archive.org/web/20191218123531/http://www.leibniz-translations.com/binary.htm ↩

  2. Binary number system—an overview article. Wikipedia. — https://en.wikipedia.org/wiki/Binary_number ↩

  3. George Boole, “An Investigation of the Laws of Thought,” 1854—the book from which Boolean logic grew. — https://www.gutenberg.org/ebooks/15114 ↩

  4. Boolean algebra—an overview article. Wikipedia. — https://en.wikipedia.org/wiki/Boolean_algebra ↩

  5. Claude Shannon, “A Symbolic Analysis of Relay and Switching Circuits,” 1937—showed that Boolean algebra describes electrical circuits. — https://www.cs.virginia.edu/~evans/greatworks/shannon38.pdf ↩

  6. Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” 1936—proof that a single universal computing machine is possible. — https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf ↩

  7. John von Neumann, “First Draft of a Report on the EDVAC,” 1945—the document that set the architecture of computers. — https://web.mit.edu/STS.035/www/PDFs/edvac.pdf ↩

  8. Von Neumann architecture—an overview article. Wikipedia. — https://en.wikipedia.org/wiki/Von_Neumann_architecture ↩

  9. Charles Petzold, “Code: The Hidden Language of Computer Hardware and Software”—how a computer is built from logic and relays, for readers with no background. — https://en.wikipedia.org/wiki/Code:_The_Hidden_Language_of_Computer_Hardware_and_Software ↩

  10. Nand2Tetris—a free course: build a computer from scratch out of a single logical operation. — https://www.nand2tetris.org/ ↩

Get chapter 4 when it’s out