Gates of Gates
Each square belongs to one gate, G, sitting at its origin in the top-left corner. Along the x axis (left to right) are the 16 gates as the first input, X. Down the y axis are the 16 gates as the second input, Y. Each cell is G(X, Y): the gate you get by feeding X and Y into G, row by row of their truth tables. In lambda terms that is λp.λq. G (X p q) (Y p q). The result is always one of the same 16 gates.
lambda16.txt. A hollow cell behaves the same way but reduces to a different program. See “The 506 programs” below.lambda16.txt and boolean16.py, so gate i and gate 15 − i are complements. Hover or tap a cell for the full result.All 16 squares
Click a square to open it above as a full table with gate names on both axes.
The 506 programs
Every cell is itself a lambda term: λp.λq.λa.λb. G (X p q) (Y p q) a b, with the three gates' terms plugged in. Reducing all 4,096 of these terms gives 506 different normal forms. Each one behaves exactly like one of the 16 gates, so there are only 16 different behaviours, but 506 different programs that produce them.
For each gate, one program is exactly its term in lambda16.txt, marked below. 2,064 cells reduce to one of those; the other 2,032 reduce to a longer program with the same truth table. Programs are shown in short form, with the four inputs named p, q, a and b as in the file. Hover a cell above to see its program.
Patterns to look for
Every square makes one of four kinds of pattern, depending on how its gate uses the two inputs:
| Pattern | Gates | Why |
|---|---|---|
| Blank or solid | FALSE, TRUE | the output ignores both inputs |
| Stripes | P, Q, NOT P, NOT Q | the output follows one input |
| Triangles | AND, OR, NAND, NOR, p∧¬q, q∧¬p, p→q, q→p | each is AND with its inputs or output flipped, so each square is AND's triangle reflected or inverted |
| Checkerboards | XOR, XNOR | the output compares the two inputs: same or different |
Checkerboards. XOR's pattern is spread across the four quarters of each cell, so look at one quarter at a time with the One quarter view. In one quarter, X's values run in stripes down the columns and Y's across the rows, and XOR is TRUE where a TRUE stripe crosses a FALSE one: a checkerboard. In Truth-table value order the four quarters are checkerboards with squares 8, 4, 2 and 1 cells wide. In complement order the rows and columns are shuffled, so the same crossing looks like plaid. XNOR is the same with TRUE and FALSE swapped. XOR and XNOR are also Latin squares: every row and column contains all 16 gates exactly once. XOR's diagonal is all FALSE and XNOR's all TRUE.
- FALSE and TRUE ignore their inputs: every cell is FALSE, or every cell is TRUE.
- P copies X: every column is a single gate, the one at the top of it. Q copies Y: every row is the gate at its left.
- NOT P gives 15 − X and NOT Q gives 15 − Y: the complement of the input.
- AND, OR, XOR, XNOR, NAND and NOR are symmetric: G(X, Y) = G(Y, X), so their squares mirror across the diagonal.
- On the diagonal, where X = Y, AND gives back X and XOR gives FALSE.
- Switch the axis order to “Truth-table value” and nested, self-similar patterns appear, like those in Wolfram's A New Kind of Science. The AND square's empty cells form a Sierpinski-style triangle, and the XOR square is built from copies of itself at half size. In that order, each square is simply G applied bit by bit to two 4-bit numbers.
- Gate 15 − G is the complement of gate G, cell for cell: the square for NAND is the square for AND with every truth table flipped.
Every cell was computed by lambda reduction, 16,384 reductions in all, and each one agrees with plain bitwise arithmetic on the truth tables. The patterns described here, including the four checkerboards, the Latin squares and the triangle family, were each checked across all cells before the page was built.