Counting and diagonalisation

Write down every string of three bits: 000, 001, 010, 011, 100, 101, 110 and 111. A bit is one of the two symbols 0 and 1, and a string is a finite row of symbols. There are 8 strings of three bits, because each of the three positions admits 2 independent choices, and the enumeration is complete. A program is itself a string over the characters of its language, so the programs can be enumerated in the same fashion: all strings of length one, then all strings of length two, and so on [S:5:224].

A set is countable when its members can be arranged in a list with a first, a second, a third, and every member at some finite position [S:5:217]. A list is therefore a correspondence between the whole numbers and the members of the set, and a correspondence that omits nothing is a bijection in the terminology of the previous section. A diagonalisation is an argument that constructs, from any proposed enumeration, an object that cannot occur within it [S:5:223]. The collection of functions from the whole numbers to bits admits no enumeration whatever, and the demonstration is brief. !Read the diagonal, flip every bit, and the result differs from every row. The three rows are 110, 011 and 100; the marked cells are the first bit of the first row, the second of the second and the third of the third, which read 1, 1, 0. Flipped, they read 0, 0, 1, and the new string meets row one at position one with the opposite bit, row two at position two, and row three at position three. The ellipsis says the same move runs at position n against row n for every n, so no list of rows contains every string. Status: re-simulated.

Finite intuition misleads at the very first step. Adjoin one new element to the whole numbers — set −1 alongside them — and ask whether the result is larger. For a finite collection the answer is yes, because adding an element raises the count. Here send −1 to 0 and send each whole number n to n+1; every member of the enlarged collection lands on exactly one whole number, and nothing is omitted [S:5:217]. The collection has absorbed an additional member without growing, which is the first sign that the magnitude of an infinite collection, the size a count would report, cannot be a count.

The diagonal move is easiest to see on a small table. Three rows, three bits apiece: 110, 011 and 100. Read the diagonal, which consists of the first bit of the first row, the second bit of the second row and the third bit of the third row: 1, 1, 0. Flip every bit to obtain 0, 0, 1. The resulting string differs from row one at position one, from row two at position two, and from row three at position three.

With three rows the device demonstrates very little, since there are 8 strings and only 3 were listed. The construction never inspects the quantity of rows. Present it with any enumeration, however extensive, and it returns a string that differs from the nth row at the nth position, for every n [S:5:223]. No enumeration can therefore contain every string.

Worked example. Apply the identical move to an enumeration of functions.

Each function from the whole numbers to the pair of bits 0 and 1 is an infinite row of bits, so an enumeration of such functions is an enumeration of rows. Suppose that somebody presents you with such an enumeration, one row for each whole number. Define a new row by reading the diagonal and flipping every bit: at position n, place the opposite of the nth bit of the nth row. The new row is a function of precisely the same kind.

The new row differs from the nth row at position n, so it does not occur in the enumeration [S:5:223]. The enumeration was arbitrary, so no enumeration can succeed.

The identical argument, with programs in place of rows, establishes that no program can recognise exactly those programs that fail to halt [S:5:225]. A program halts when its run stops after finitely many steps, and the programs that fail to halt are the ones that run forever. To recognise a collection is to answer yes on each of its members and no on everything else.

Suppose a program R recognised that collection. Supply R with its own text, so that it must answer whether R, run on that text, halts. Build a second program that asks R that question and then does the opposite: it halts if R says it runs forever, and it runs forever if R says it halts. Run the second program on its own text, and the answer flips against itself, which is the diagonal in different clothing. The consequence is not a deficiency in current technology that a superior compiler might remedy; it is a limitation on what any program in that language can accomplish.

The argument establishes an impossibility, and it carries a price. It does not identify a particular string as missing from a particular enumeration unless you execute the construction, and the missing object depends upon the enumeration, so it is not a fixed witness that you can name in advance. It also says nothing about how difficult the unlisted objects are to describe, or about which of them you will ever require. Above all, it proves only that no enumeration exists: it gives no order in which one unlistable collection is larger than another, and it does not indicate what to do with them.

The formal statement. Two sets have the same size when a bijection joins them. A set is countable when it is finite, or when a bijection joins it to the whole numbers, which is the same as saying that its members can be listed with a first, a second, and no omissions [S:5:217]. A diagonal argument assumes a listing and constructs a member that differs from every entry.

The theorem. No function from a set $A$ to its collection of subsets is surjective. Let $S$ be the set of members $a$ of $A$ that are not members of the subset assigned to $a$. $S$ is a subset of $A$, so it is a candidate output. Suppose that $S$ is assigned to some member $d$. If $d$ belongs to $S$ then it does not belong to the subset assigned to $d$, which is $S$. If it does not belong to $S$ then it belongs to that subset, which is $S$. A sentence and its negation hold together, so no such $d$ exists.

The corollary for bit strings. Take $A$ to be the whole numbers and read a subset as an infinite row of bits. The theorem says that no listing of rows contains every row. That is the core's construction with the bookkeeping shown [S:5:223].

Why programs are countable. Fix a finite alphabet. The strings of length $k$ are finite in number, so list them all, then all strings of length $k+1$, and continue. Every program is a finite string, so every program appears at some finite position [S:5:224]. The functions that programs compute are therefore countable. The functions from the whole numbers to two bits are not countable. So most such functions are computed by no program, where "most" is a statement about cardinality.

The halting theorem. Suppose a program decides, for each string, whether the program with that text halts on its own text. Build a second program that asks the first about its own text and then does the opposite: it halts exactly when the answer says that it does not. Then it halts on itself exactly when it does not, which is impossible. The contradiction is the diagonal again, with programs in place of rows [S:5:225].

The edge case. The core's bijection from the whole numbers plus one member back to the whole numbers is explicit: send the new member to 0 and each old member $n$ to $n+1$. The general theorem that an infinite set absorbs one new member is proved by selecting a sequence of distinct members, and that selection is a countable choice principle [S:5:217]. For the whole numbers the sequence is written down; for an arbitrary infinite set it is asserted.

The other edge case. The missing object is not unknowable. Given a listing as a program, the flipped diagonal is computed by a program that flips the diagonal bit. The argument denies a witness fixed independently of the listing, not a witness altogether.

What the core left out. It left out the collection of subsets, and the difference between "no listing exists" and "the listing is unfinished". The diagonal is not a longer list; it proves that the list cannot be completed.

Original sources. Countable sets, the bijection that absorbs one new member, and the diagonal argument are section 7.1 of Mathematics for Computer Science [S:5:217]. The halting problem is section 7.2 of the same chapter, and it names Cantor's argument as its model [S:5:223]. The observation that every program is a finite string over a finite alphabet, so programs can be listed, is on the following page [S:5:224].

An open question. The general halting problem is undecidable, and the text says that diagonal arguments show that many problems cannot be solved by computation at all [S:5:223]. What is not settled is where the boundary lies for restricted classes of programs. A restricted language can make termination checkable by requiring a ranking function on every loop; general programs admit no such analysis. The classes between the two are mapped one at a time. Evidence that would settle a proposed boundary: a decision procedure for the larger class, with a proof of correctness, and an undecidability proof for the next class up. A procedure that works on examples would not locate the boundary.

A frontier result. The counting argument explains why learning theory asks for restrictions. The predictors a program can name form a countable set, while the labellings of a countable input set do not, so no program names them all [S:5:224]. Valiant's model turns the positive side into a computational question with a polynomial budget [S:159:1], and the no-free-lunch theorem closes the negative side for any learner that claims no prior [S:79:61]. The two results are the frame in which a claim about generalisation is stated.

What to read next. Read section 7.1 of [S:5:217] for countability and section 7.2 of [S:5:223] for the halting argument. Read chapter 5 of [S:79:61] for the theorem that explains why the counting limit reaches learning, and [S:159:1] for the model that states what a learner may assume.