Circuits and automata: How does a machine compute, deep down?

A language model running on a graphics card performs trillions of operations a second, and each one, deep down, is made of switches that are either on or off. How do you get from a switch to a machine that adds, remembers and follows a program? The answer took a century to assemble, from George Boole's algebra (1854) to the first computers with a stored program (1948), and it is the foundation on which everything else in this site stands.

The key piece came from a master's thesis. In 1937 Claude Shannon, aged twenty-one, showed that the circuits of relays in telephone exchanges obey exactly Boole's algebra: a switch is a variable that is worth $0$ or $1$ , two switches in series are an $\land$ (and) and two in parallel an $\lor$ (or). Designing a circuit became a matter of manipulating formulas, and reasoning about formulas became something a circuit could do.

One gate is enough

A Boolean function of $n$ inputs is any rule $f : {0, 1}^{n} \to {0, 1}$ . There are many of them: each of the $2^{n}$ possible inputs can be sent to $0$ or $1$ , so there are $2^{2^{n}}$ functions, already 65,536 for $n = 4$ . Yet a handful of building blocks can construct them all, and in fact a single one is enough: the NAND gate, “not and”.

NAND (x, y) = \neg (x \land y) = 1 - x y .

Theorem (functional completeness)

Every Boolean function $f : {0, 1}^{n} \to {0, 1}$ can be computed by a circuit of $\land$ , $\lor$ and $\neg$ gates. NAND gates alone are also enough.

Proof

For each input $a \in {0, 1}^{n}$ with $f (a) = 1$ , form the conjunction $m_{a} (x) = ℓ_{1} \land \dots \land ℓ_{n}$ , where $ℓ_{i} = x_{i}$ if $a_{i} = 1$ and $ℓ_{i} = \neg x_{i}$ if $a_{i} = 0$ . By construction $m_{a} (x) = 1$ exactly when $x = a$ . So

f (x) = \underset{a : f (a) = 1}{⋁} m_{a} (x),

which is $1$ exactly at the inputs where $f$ is $1$ (if there are none, $f = x_{1} \land \neg x_{1}$ ). This is the disjunctive normal form. For NAND it is enough to rebuild the three gates:

\neg x = NAND (x, x), x \land y = \neg NAND (x, y), x \lor y = NAND (\neg x, \neg y),

the last one by De Morgan's law, $\neg (\neg x \land \neg y) = x \lor y$ .

The proof builds circuits that can be huge, and Shannon showed in 1949 that, for most functions, that cannot be avoided: there are $2^{2^{n}}$ functions but far fewer small circuits, so almost every function of $n$ inputs needs on the order of $2^{n} / n$ gates. The functions we care about are the rare exceptions with small circuits. Addition is one of them.

From gates to arithmetic

To add two numbers in binary you do what you learned at school, column by column, carrying. In column $i$ three bits come in, $x_{i}$ , $y_{i}$ and the carry $c_{i}$ , and two go out: the result digit $s_{i}$ and the next carry $c_{i + 1}$ . With $\oplus$ for the exclusive or (which is $1$ when exactly one of its inputs is), the full adder is

s_{i} = x_{i} \oplus y_{i} \oplus c_{i}, c_{i + 1} = (x_{i} \land y_{i}) \lor (c_{i} \land (x_{i} \oplus y_{i})) .

Proposition (ripple-carry adder)

Chaining $n$ full adders, with $c_{0} = 0$ , computes the sum of two $n$ -bit numbers $x$ and $y$ :

\sum_{i = 0}^{n - 1} s_{i} 2^{i} + c_{n} 2^{n} = x + y .

Proof

Checking the eight possible inputs shows that the full adder writes the sum of its three bits in binary: $x_{i} + y_{i} + c_{i} = s_{i} + 2 c_{i + 1}$ . Multiplying by $2^{i}$ and adding over $i$ ,

x + y = \sum_{i} (x_{i} + y_{i}) 2^{i} = \sum_{i} (s_{i} + 2 c_{i + 1} - c_{i}) 2^{i} = \sum_{i} s_{i} 2^{i} + \sum_{i} (c_{i + 1} 2^{i + 1} - c_{i} 2^{i}),

and the last sum telescopes to $c_{n} 2^{n} - c_{0} = c_{n} 2^{n}$ .

A 4-bit adder. Click the bits of

A

and

B

to flip them. Each column is a full adder made of five gates; choose a column to see its circuit, with the wires that carry a

1

lit up. If the result does not fit in four bits, the last carry becomes a fifth bit.

Each full adder costs five gates (or nine NAND gates), so adding 64-bit numbers takes a few hundred gates. Multiplying, comparing or computing a $softmax$ is just a matter of more circuits of the same kind. What is still missing is memory.

Memory, and finite automata

A circuit whose output feeds back into its input can remember. Two NAND gates connected in a loop form a latch that keeps a bit until it is told to change it. With $k$ of those bits and a clock that ticks, a circuit has $2^{k}$ possible states and, at each tick, moves from one state to another depending on the state and on what comes in. That object, stripped of the electronics, is a finite automaton.

Definition (deterministic finite automaton)

A DFA is a tuple $M = (Q, Σ, δ, q_{0}, F)$ with a finite set of states $Q$ , an input alphabet $Σ$ , a transition function $δ : Q \times Σ \to Q$ , an initial state $q_{0}$ and a set of accepting states $F \subseteq Q$ . It reads a word $w = a_{1} a_{2} \dots a_{m}$ one symbol at a time, $q_{j} = δ (q_{j - 1}, a_{j})$ , and accepts it if it ends in $F$ . The set of accepted words is the language $L (M)$ .

The idea came from an unexpected place: the model of neurons by McCulloch and Pitts (1943), networks of threshold units that Stephen Kleene analysed in 1951 to ask which “events” they could detect. The answer, the languages that finite automata recognise, also has a very concrete description.

A finite automaton reading a word, one symbol at a time. The first one decides whether a binary number is a multiple of three without ever storing it: it only needs to remember the remainder. The last one accepts

a^{n} b^{n}

, but only up to

n = 3

. Try aaaabbbb: there is no state for “four”.

A regular expression describes a set of words with three operations: union ( $r ∣ s$ , one or the other), concatenation ( $r s$ , one after the other) and the Kleene star ( $r^{*}$ , any number of repetitions). For example, $(0 ∣ 1)^{*} 01$ is “any word that ends in $01$ ”.

Theorem (Kleene 1956)

A language is described by a regular expression if and only if it is recognised by a finite automaton.

To go from expressions to automata it is convenient to let the automaton guess. A nondeterministic automaton (NFA) can have several transitions with the same symbol, or none, and accepts if some choice leads to an accepting state. Each operation of an expression then becomes a small piece of NFA (Thompson's construction, 1968, still at the heart of many regular-expression engines). Guessing seems to give extra power. It does not:

Theorem (subset construction, Rabin and Scott 1959)

For every NFA with $n$ states there is a DFA that recognises the same language with at most $2^{n}$ states.

Proof

The DFA keeps track of all the states the NFA could be in. Its states are the subsets $S \subseteq Q$ ; it starts at ${q_{0}}$ ; reading $a$ it moves to $δ^{'} (S, a) = ⋃_{q \in S} δ (q, a)$ ; and it accepts if $S \cap F \neq \emptyset$ . By induction on the length of the word, after reading $w$ the DFA is in exactly the set of states the NFA can reach with $w$ , so it accepts if and only if some run of the NFA does. There are $2^{n}$ subsets.

The exponential is real: the language “the $n$ -th symbol from the end is a $1$ ” has an NFA with $n + 1$ states, and every DFA for it needs at least $2^{n}$ . Rabin and Scott received the Turing Award in 1976 for this paper, which also introduced nondeterminism, an idea that a decade later would underlie the $P$ versus $NP$ question.

What finite memory cannot do

The automaton in the figure cannot be extended to recognise $a^{n} b^{n}$ for every $n$ , however many states we give it. It is not a lack of ingenuity: it is a theorem.

Theorem (pumping lemma, Bar-Hillel, Perles and Shamir 1961)

If $L$ is regular, there is a number $p$ such that every word $w \in L$ with $| w | \geq p$ can be split as $w = x y z$ with $| x y | \leq p$ and $| y | \geq 1$ , so that $x y^{i} z \in L$ for every $i \geq 0$ .

Proof

Let $p$ be the number of states of a DFA for $L$ . Reading the first $p$ symbols of $w$ , the automaton goes through $p + 1$ states, so by the pigeonhole principle it repeats one: there are positions $j < k \leq p$ with $q_{j} = q_{k}$ . Let $x$ be the first $j$ symbols, $y$ the following $k - j$ and $z$ the rest. Reading $y$ takes the automaton from $q_{j}$ back to the same state, so it can do it zero times or a hundred, and it will still end up where it ended with $w$ : in an accepting state.

Take $L = {a^{n} b^{n} : n \geq 0}$ and suppose it were regular, with constant $p$ . The word $a^{p} b^{p}$ is in $L$ , and since $| x y | \leq p$ , the piece $y$ consists only of $a$ 's. Pumping it, $x y^{2} z$ has more $a$ 's than $b$ 's, and it is not in $L$ . Contradiction. A finite automaton cannot count without limit: to check that there are as many $b$ 's as $a$ 's it would have to remember a number that can be arbitrarily large.

Chomsky's hierarchy

In 1956 the linguist Noam Chomsky asked which kind of grammar could describe a human language, and by 1959 he had ordered the formal languages into four levels. Each kind of grammar corresponds exactly to a kind of machine, which differ only in their memory:

Type	Grammar	Machine	Memory	Example beyond the previous level
3	Regular	Finite automaton	Finite	$(0 ∣ 1)^{*} 01$
2	Context-free	Pushdown automaton	A stack	$a^{n} b^{n}$
1	Context-sensitive	Linear-bounded automaton	A tape as long as the input	$a^{n} b^{n} c^{n}$
0	Unrestricted	Turing machine	An unbounded tape	The halting problem

REG ⊊ CFL ⊊ CSL ⊊ RE .

A single stack is enough for $a^{n} b^{n}$ : push a token for each $a$ and pop one for each $b$ . Context-free grammars, written in the Backus–Naur notation of ALGOL 60, describe the syntax of almost every programming language, and so every compiler starts with a finite automaton that splits the text into tokens and a pushdown automaton that builds the syntax tree. Human languages turned out to be more slippery: a few constructions, such as the cross-serial dependencies of Swiss German, are beyond context-free grammars. Sixty years later the models that best predict language are not grammars at all, but that is another chapter.

The machine underneath

With adders, memory and a finite automaton to coordinate them, a computer can be built. In 1945 John von Neumann described the design of the EDVAC: a memory that holds both the data and the program, a unit that does arithmetic and a control unit that repeats the same cycle forever. On 21 June 1948 the Manchester “Baby” became the first computer to run a program stored in its own memory.

Fetch: read from memory the instruction the program counter points to, and advance the counter.
Decode: the control automaton works out which operation it is and which memory cell it refers to.
Execute: the adder or the memory does the work, and the cycle starts again.

A toy processor with an accumulator and 24 memory cells. Instructions are numbers too: 322 means “add the contents of cell 22”. Step through the fetch–decode–execute cycle and watch the program counter jump back to repeat a loop.

A real computer is, strictly speaking, a finite automaton: with $k$ bits of memory it has at most $2^{k}$ states. But with 16 gigabytes, $k$ is about $1.4 \times 10^{11}$ , and $2^{k}$ is a number that nothing in the universe can enumerate. It makes more sense to think of memory as a tape that can always be extended. That idealization, the infinite tape, is exactly Turing's machine.

References

G. Boole (1854). An Investigation of the Laws of Thought. Walton and Maberly.
C. E. Shannon (1938). “A Symbolic Analysis of Relay and Switching Circuits”. Transactions of the AIEE, 57(12).
W. S. McCulloch and W. Pitts (1943). “A Logical Calculus of the Ideas Immanent in Nervous Activity”. Bulletin of Mathematical Biophysics, 5.
J. von Neumann (1945). First Draft of a Report on the EDVAC.
C. E. Shannon (1949). “The Synthesis of Two-Terminal Switching Circuits”. Bell System Technical Journal, 28(1).
S. C. Kleene (1956). “Representation of Events in Nerve Nets and Finite Automata”. In Automata Studies, Princeton University Press.
N. Chomsky (1956). “Three Models for the Description of Language”. IRE Transactions on Information Theory, 2(3).
N. Chomsky (1959). “On Certain Formal Properties of Grammars”. Information and Control, 2(2).
M. O. Rabin and D. Scott (1959). “Finite Automata and Their Decision Problems”. IBM Journal of Research and Development, 3(2).
Y. Bar-Hillel, M. Perles and E. Shamir (1961). “On Formal Properties of Simple Phrase Structure Grammars”. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14.
K. Thompson (1968). “Regular Expression Search Algorithm”. Communications of the ACM, 11(6).
J. E. Hopcroft, R. Motwani and J. D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation, 3rd ed. Addison-Wesley.

§One gate is enough

§From gates to arithmetic

§Memory, and finite automata

§What finite memory cannot do

§Chomsky's hierarchy

§The machine underneath

§References

One gate is enough

From gates to arithmetic

Memory, and finite automata

What finite memory cannot do

Chomsky's hierarchy

The machine underneath

References