j is one more than i, counting round — as a grid, with both quantifier readings
relation-grid is one function. Everything below came out of it during this
build, at parameters taken from the essays rather than invented for this page — so a figure
here is the same figure a reader meets in an essay, and if the generator changes, this page
changes with it.
With nothing chosen
Does this set contain that one — and the row that is missing
The diagonal, and the row built to be off the list
13 + 11 = 24, checked column by column with one bit of memory
Addition as a machine with two states
A machine for the powers of two, and one for doubling
What it checks while it draws
Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.
- the machine for "x = 2y" is right on 0, 0 ×4096
- the machine for "x is a multiple of 3" is right on 0 ×256
- the machine for "x is a power of two" is right on 0 ×256
- the machine for "x is even" is right on 0 ×256
- column 2 ×59
- column 2 is empty exactly when 2 is prime ×59
- functions pairing off 1 points ×7
- one-to-one maps of 1 points missing a point ×7
- column 0 of the sum is right ×6
- Abelard's winning strategies on 2 points ×5
- slice a = 1: a solution exists exactly when the eliminated formula says so ×2
- the formula for ∀x ∃y at n = 2 ×2
- the shadow repeats every 5 ×2
- ∀x ∀y R(x, y) holds for R exactly when its dual fails for the complement ×1
- ∀x ∀y R(x, y) implies ∃x ∀y R(x, y) with nothing between ×1
- ∀x ∀y R(x, y) implies ∃y ∀x R(x, y) with nothing between ×1
- ∀x ∃y R(x, y) holds for R exactly when its dual fails for the complement ×1
- ∀x ∃y R(x, y) implies ∃x ∃y R(x, y) with nothing between ×1
- ∀y ∃x R(x, y) holds for R exactly when its dual fails for the complement ×1
- ∀y ∃x R(x, y) implies ∃x ∃y R(x, y) with nothing between ×1
- ∃x ∀y R(x, y) holds for R exactly when its dual fails for the complement ×1
- ∃x ∀y R(x, y) implies ∀y ∃x R(x, y) with nothing between ×1
- ∃x ∃y R(x, y) holds for R exactly when its dual fails for the complement ×1
- ∃y ∀x R(x, y) holds for R exactly when its dual fails for the complement ×1
- ∃y ∀x R(x, y) implies ∀x ∃y R(x, y) with nothing between ×1
- 240 labelled tournaments on seven players have the property, 5,040 / 21 ×1
- 7³ = 343 relations have a mark in every row ×1
- a column holds a mark exactly when its values of a satisfy |a| ≥ 2 ×1
- a full column forces every row to carry a mark, so one reading implies the other ×1
- a machine that keeps writing and never halts exists ×1
- a machine that ran three thousand steps does not halt in the classifier ×1
- a machine that runs six steps and leaves four ones exists ×1
- a match is at least as long as the run it writes out, less the cells the rewriting dominoes take two or three at a time ×1
- a matching covers every point exactly when the number of points is even ×1
- a program computing how many times f occurs in it gets it right about itself ×1
- a program computing its own length gets it right about itself ×1
- a program computing its own text reversed, first 24 characters gets it right about itself ×1
- a program computing whether its length is even gets it right about itself ×1
- a row copied from the table is found in the table ×1
- a shifted repeat visible within sixty steps exists ×1
- a tournament with every pair beaten by a third is found ×1
- a two-state machine recognises the pairs (x, largest power of two dividing x) ×1
- almost every cell is checked against the formula ×1
- and 512 − 343 = 169 have a full row ×1
- and for ∃x ∀y ×1
- and none leaves more than four ones ×1
- and one predecessor ×1
- at 16 points almost every relation has a mark in every row ×1
- between 3 and 7 points ×1
- carrying out the instruction prints the instruction itself ×1
- each generation prints exactly the next one ×1
- each point has one successor ×1
- each writer's match is found and is shortest ×1
- Erdős's expectation falls below one at 21 players ×1
- every friendship graph searched is a windmill ×1
- every halting machine is counted once ×1
- every point is in exactly one colour class ×1
- every step of the match is legal ×1
- every step of the witness follows an edge ×1
- every total past the largest gap can be made ×1
- every winning pair has f = g ×1
- every x makes it positive exactly when a² − 4b < 0 ×1
- five logics in the table ×1
- following successors from any point visits all eight before returning ×1
- functions from five points to five points ×1
- in a line, every row can be answered ×1
- in a line, the sentence holds from two points on ×1
- M′ computes the successor exactly when M halts ×1
- most halting machines never read all four entries of their table ×1
- most of the unexplained machines spread like the square root of time ×1
- no carry is left over after the last column ×1
- no drawn row agrees with the built row everywhere it has been checked ×1
- no edge joins two points of one class ×1
- no halting two-state machine runs more than six steps ×1
- no language defines truth for its own sentences ×1
- no match is shorter than the drawn depth ×1
- no row of the table is the Russell row ×1
- no shorter match could have escaped the search ×1
- no three-state machine leaves more than six 1s ×1
- no tournament of two to six players has every pair beaten by a third ×1
- no unexplained machine halts within two hundred thousand steps ×1
- of which 1,379 halt ×1
- on one point Abelard wins, since x ≠ y cannot hold ×1
- one half begins 0.5000 ×1
- pairing six points off makes the branching sentence true ×1
- pi minus three begins 0.14159 ×1
- six machines are chosen, halting and not ×1
- slice a = -1: a solution exists exactly when the eliminated formula says so ×1
- some relation satisfies ∀x ∃y R(x, y) but not ∀y ∃x R(x, y) ×1
- some relation satisfies ∀x ∃y R(x, y) but not ∃y ∀x R(x, y) ×1
- some relation satisfies ∀y ∃x R(x, y) but not ∀x ∃y R(x, y) ×1
- some relation satisfies ∃x ∀y R(x, y) but not ∀x ∃y R(x, y) ×1
- some x makes it zero exactly when a² − 4b ≥ 0 ×1
- the backtracking search never tries more than all colourings ×1
- the backward test never refutes a machine that does halt ×1
- the bottom row is ahead after every domino but the last ×1
- the built row differs from row n in place n ×1
- the chart counts table entries read or ones left ×1
- the check in a line makes at most n⁴ plays ×1
- the coins share no common factor, so every large enough total is reachable ×1
- the compressor sees no pattern in pi and a strong one in the periodic string ×1
- the count k over the root of k − 1 is a whole number only for k = 2 ×1
- the count of phrases grows no faster than the alphabet's powers ×1
- the diagram has six arrows ×1
- the dominoes of a halting machine have a match ×1
- the drawn range contains the largest total that cannot be made ×1
- the drawn window is at least as wide as it is tall ×1
- the first number is a whole number between 1 and 63 ×1
- the friendship sentence holds exactly at the odd sizes searched ×1
- the gaps between squares keep growing ×1
- the labelling is one this figure knows ×1
- the largest number is a whole number between 20 and 80 ×1
- the longest halting run is 21 steps ×1
- the machine accepts exactly the powers of two ×1
- the machine accepts exactly the true sums ×1
- the machine for "x + y = z" is right ×1
- the machine is one the family encodes ×1
- the machine stays on the tape it was given ×1
- the match spells one string twice ×1
- the match writes out the machine's run, configuration by configuration ×1
- the new number's i-th digit differs from phrase i's ×1
- the number of columns is a whole number between 2 and 14 ×1
- the number of drawn columns is a whole number between 3 and 16 ×1
- the number of drawn rows is a whole number between 3 and 12 ×1
- the number of levels is a whole number between 3 and 9 ×1
- the number of rows is a whole number between 2 and 14 ×1
- the number of sets in the table is a whole number between 3 and 10 ×1
- the option is one this view reads ×1
- the Petersen graph can be coloured with three colours ×1
- the phrase itself has fewer than ninety characters ×1
- the program's output is its own text, character for character ×1
- the property is rare at seven players and usual at thirty, above the counting floor ×1
- the range is a whole number between 16 and 96 ×1
- the relation is one this figure knows how to draw ×1
- the residue tournament on seven players has every pair beaten by a third ×1
- the row of 'does not describe itself' differs from each adjective's row on the diagonal ×1
- the Russell row disagrees with row k at column k ×1
- the search agrees with 256b³ ≤ 27a⁴ ×1
- the search is drawn between 4 and 12 dominoes deep ×1
- the search stays within its budget of states ×1
- the second machine accepts exactly x = 2y ×1
- the second number is a whole number between 1 and 63 ×1
- the set defined by ∃y (x = y + y) is eventually periodic ×1
- the set defined by ∃y (y + y + y ≤ x ≤ y + y + y + 1) is eventually periodic ×1
- the set defined by ∃y ∃z (x = 3y + 5z) is eventually periodic ×1
- the set defined by ∃y ∃z ∃w (x = 6y + 9z + 20w) is eventually periodic ×1
- the shadow is exactly the x whose remainder a·x mod b lies within c of a multiple of b ×1
- the share with every row marked eventually only rises ×1
- the shortest match of the three dominoes has thirty-six of them ×1
- the slope's rise is a whole number between 1 and 9 ×1
- the slope's run is a whole number between 2 and 9 ×1
- the slow ones grow like the logarithm of the time, as a binary counter does ×1
- the squares are not eventually periodic with any small period on the range checked ×1
- the three dominoes have a match ×1
- the three-state tree has 16,549 machines ×1
- the tournament found has every pair beaten by a third ×1
- two coins: the largest total that cannot be made is ab − a − b ×1
- two or three states ×1
- two to four coin values ×1
- winning pairs (f, g) ×1
- with f a rotation, every column asks two different values of v ×1
Where it is called
Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.
A game that decides what can be said
Two players take turns pointing at elements of two structures; if the second can survive k rounds, then no sentence with k quantifiers tells the structures apart — a statement about infinitely many formulas, settled by a finite search.
LogicA list that cannot contain itself
The set of all sets that do not contain themselves is not a set. The argument is the diagonal again, applied to a table whose rows and columns are the same objects, and it destroyed the foundations of mathematics in a postcard.
LogicA machine that carries one bit
Write three numbers in base two, one above another, and read the columns from the right. Whether the bottom number is the sum of the top two can be checked with one bit of memory — the carry. That two-state machine is the whole of addition, and machines can be combined, negated and made to guess a missing number. So every sentence about whole numbers built from addition can be decided by building a machine for it, and the same machines can also handle 'x is a power of two', which addition alone cannot say.
LogicA quantifier is a shadow
'There is an x such that …' asks whether a column of a grid contains a mark — which is the same as asking whether a shape casts a shadow on the axis below it. Over the real numbers every such shadow can be described without the quantifier, by polynomial inequalities: 'x² + ax + 1 = 0 has a solution' is just a² ≥ 4. Over the whole numbers the same kind of shadow can carve out the primes, and any set a computer can list.
LogicAn infinite tree has an infinite path
A tree that goes on forever, in which every node has only finitely many children, must contain a single branch that goes on forever. The proof is a rule for walking, and the rule is the whole of why finite information can decide an infinite question.
LogicArithmetic with addition alone
Over the real numbers, a quantifier's shadow is described by inequalities. Over the whole numbers with addition and multiplication, a shadow can be any set a computer can list. In between lies arithmetic with addition and no multiplication, and there the shadows are always the same kind of thing: a finite exception, then a pattern that repeats. The whole numbers made from coins worth 6, 9 and 20 are every number from 44 on; the squares, which need multiplication, never repeat at all.
LogicDominoes that no algorithm can match
Emil Post's puzzle has no machines and no programs in it: a handful of dominoes, each with a string on top and a string underneath, and the question whether some row of them, repeats allowed, spells the same word along both edges. No algorithm can answer it for every set of dominoes, because a set can be built whose only matches are a machine's run written out twice, one step out of phase — and three dominoes with strings of three characters already need thirty-six in a row before the edges agree.
LogicEvery row, or one column
For every person there is someone who loves them, and there is someone who loves everyone, are the same six words in a different order. Draw the relation as a grid and they become two obviously different questions — one about rows, one about columns.
LogicFour quantifiers, one of them blind
In 'for every x there is a y, and for every u there is a v', the last choice may depend on everything before it. Leon Henkin asked in 1961 what happens if v may depend on u alone. Using nothing but the equals sign, four such quantifiers then say that a set has an even number of points, or that it is infinite — things no ordinary sentence can say — and the game behind the sentence can end with neither player able to win.
LogicNo algorithm can read what a program does
Whether a program halts cannot be decided by any algorithm. Henry Rice showed in 1953 that the halting problem is not special: no algorithm can decide any property of what a program does — whether it ever prints a 7, whether it computes the successor function, whether it is a virus — except the two properties that hold of every program or of none. Every one of the 20,736 smallest Turing machines can be checked by hand; the theorem says why that stops.
LogicSix sentences from two quantifiers
One relation, two variables, 'for every' and 'there is': there are eight ways to arrange them and six different sentences come out. Which of them imply which is a small, complete diagram, found by checking all 512 relations on three points — and the diagram crosses over in the middle, which is where every confusion about the order of quantifiers lives.
LogicThe arithmetic that loses subtraction
Adding one to an infinite collection changes nothing, and neither does doubling it, or squaring it. What that costs is the two operations that were doing the work — an equation between infinite sizes cannot be cancelled, and how many are left stops being a question.
LogicThe machines that need a reason never to stop
Run every three-state machine on a blank tape and the ones that halt announce themselves: the longest stops after 21 steps. The work is in the others. Each needs a reason it will never stop, and four simple kinds of reason settle all but 27 of them — machines that sweep back and forth over a growing tape and defeat every check that looks for a repeat.
LogicThe program that prints itself
The diagonal argument has always been used to destroy — to show that a list misses something, that a sentence cannot be proved. Run the same move the other way and it builds. Kleene's recursion theorem says every program can be given its own text to work with, and the proof is a program that prints itself, thirty-two characters long, which can be run and checked.
LogicThe row that is not on the list
Write down a list of infinite sequences, any list at all, and there is a rule that builds a sequence missing from it. The rule reads one entry from each row, and it is the single most reused argument in this field.
LogicThe sentence that says it has no proof
Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable.
LogicThe shortest description nobody can certify
A string's complexity is the length of the shortest program that prints it. Counting shows almost every string has no short program, and diagonal arguments show nothing can compute the length, or even prove it large for any single string past a fixed point. All 16,777,216 three-state Turing machines leave only 95 strings on their tapes, and a compressor treats π exactly as it treats random bits.
LogicThe sizes at which a sentence can come true
Write a sentence about a relation and ask for which numbers of points some relation makes it true. "Every two points have exactly one common neighbour" comes true at every odd size and no even one, and every graph that satisfies it is a windmill of triangles. "Every two players are both beaten by some third" fails for every tournament of two to six players and holds from seven on. A search can settle one size at a time; only a proof settles all of them, and the two sentences need different kinds.
LogicThe word that cannot describe itself
Some adjectives describe themselves — 'short' is short — and some do not — 'lengthy' is not lengthy. Call the second kind heterological, and ask whether 'heterological' is heterological. It is exactly when it is not. The diagonal that beat every list of numbers, every set of sets and every provability predicate has been turned on words that describe words, and it proves that no language can contain a word for its own notion of describing, naming or truth.
LogicThere is a relation such that
A graph can be coloured with three colours exactly when there are three sets of its points such that every point lies in one and no edge joins two points of the same set. The sets are a guess; once guessed, the rest is a list of simple checks. Ronald Fagin proved in 1974 that this shape of sentence — 'there exist relations such that' followed by first-order conditions — describes exactly the problems whose solutions can be checked quickly, the class called NP. The central question of computer science is therefore also a question about what sentences can say.