Paradox and Bad Specification

In the early Twentieth Century Bertrand Russell published a variant of the so-called Liar Paradox which he attributed to Oxford librarian G. G. Berry, and which, accordingly, is now commonly known as Berry's Paradox. The paradox is constructed as follows: What is the first number with an English language description of more than, say, thirty syllables? It seems reasonable to suppose that there is such a number; we can certainly think of numbers with descriptions that long. But how can we actually locate the first one? We could count, and for each number counted go through a list of its descriptions and count their respective syllables. It seems only logical that if there exists a number with no description of less than thirty syllables, then we must eventually reach it in the process of counting. Moreover, if such numbers exist at all, then there must be a first i.e. least such number. But wait! There's a catch! Suppose we reach a number, say N, and all the possible descriptions of N are thirty syllables or more. Suppose also that N is the first such number. Then N can be uniquely described as "the least number with no description less than thirty syllables", which is a description of exactly sixteen syllables. Sixteen is indisputably less than thirty, and so it would appear that N cannot be the least number with no description less than thirty syllables. Hence, the apparent paradox: conferring the name "least number with a description of less than thirty syllables" renders the name itself incorrect and inapplicable as soon as a candidate number is discovered.

The interest in this particular paradox, I think, is that it takes the self-referential circularity of the more commonly treated Liar Paradox and elaborates it as something of a computational procedure. The paradox has a certain intuitive appeal, because it takes a number of familiar, accessible ideas and puts them together with an unexpected result. To demonstrate what I mean by this, consider a naive algorithm (call it A) that seems to implement the sort of count-and-check procedure described above:

BEGIN (A): Set N := 0;

STEP 1: DO [generate all descriptions of N; denote this list by L]

STEP 2: FOR EACH [description in L] DO [count syllables in the description; let MIN := smallest number of syllables counted so far]

STEP 3: IF (MIN > 30) THEN [output N; HALT] ELSE [N := N + 1; GOTO STEP 1]

Unfortunately, this algorithm won't work. One problem is that there are, arguably, an infinite number of descriptions for any given number. For one thing, there are infinitely many ways to define a number in terms of arithmetic expressions, for instance, as the difference of two other numbers. (That is we can use the fact that , for any N, N = (M + N) - M, for any other number M, to generate infinitely many descriptions.) For another thing, we can define infinitely many numbers in terms of the sort of "tokens" that Frege used in his argument that the natural numbers are an a priori analytic concept[1]. For instance, "the number of dishes on the table I am sitting at, at Lakota Coffee of Columbia, Missouri on September 28, 2009" and "the distance, in centimeters, rounded down to the nearest whole number, between inch marks on a ruler" are both in some sense valid descriptions of the number two. Besides the apparent infinity of such descriptions, there is also an obvious difficulty in devising a procedure that could generate them all; this is left as an exercise to the inordinately skeptical reader.

These difficulties are not wholly insurmountable though; we might be interested only in a certain class of descriptions that we can finitely generate. In this sense, "the least number with no description less than thirty syllables" smells surprisingly like a bad specification. If we were actually interested in writing such a program, we would immediately ask, "Well, what kind of descriptions do you mean?" simply because "all" is generally an unreasonable thing to ask of machines except in the most tightly constrained circumstances. The paradox thus achieves its amusing paradoxicality by dwelling on its own bad specification. Consider, for instance, what we get if we devise an algorithm (call it A') closer in spirit to the algorithm as it plays out in the human mind:

BEGIN (A'): Set N := 0; L := EMPTY;

STEP 1: DO [generate new descriptions of N; append these to list L]

STEP 2: FOR EACH [description in L] DO [count syllables in the description; let MIN := smallest number of syllables counted so far]

STEP 3: IF (MIN > 30) THEN [append "least number with no description less than thirty syllables" to L; GOTO STEP 2] ELSE [N := N + 1; L:= EMPTY; GOTO STEP 1]

This is a slight variation on A, wherein we make the accumulation of descriptions in L at least partially explicit. The details of this are not important here (but try to work them out if you don't believe me). What is important is that the program now appends the paradoxical description to its list of descriptions-to-check, and checks it. This, of course, means that the program will throw out any and all candidates, either because the ordinary name-generation process produces a name that is less than thirty syllables, or because the very same process generates only thirty-syllable or longer names, which in turn triggers STEP 3 to append "the least number with no description less than thirty syllables" to the list of names to check, which then leads to the list being rechecked, and thus to the number being rejected on the subsequent pass. Essentially, the program is written to undo its own work and hence to work endlessly in exactly the same way that Berry's Paradox appears to lead to an indefinite search for the elusive number described in its statement.

There is an interesting conceptual disconnect between A and A'. Properly constrained, A will eventually halt and output something sensible, but doesn't do anything at all paradoxical. On the other hand, A' can never halt but "acts like" the paradox as it seems to present itself. Which one of these is correct? Before you answer, consider that we could modify A' so that, in STEP 3, N is output before going back to STEP 2. In this case, we would get an infinite sequence of numbers as output, the first of which would be the same as the output of A. Moreover, we could make the output of A identical, simply by changing "HALT" in STEP 4 to "GOTO STEP 1". The programs look different, and are differently motivated, but not all that different in how they actually work. More precisely, it is only our idea of the problem that seems to influence the decision of what the program should output and when it should stop. Even more surprisingly, the presence of the paradoxical description ("the least number ...") as in A' seems to be unnecessary; we could replace it with any description of less than thirty syllables, or we could just use modified-A to get exactly the same output.

I had at first imagined a profound and sweeping essay of logic and computer science that would somehow relate Berry's Paradox to program bugs or verification procedures, but this proved far too broad, and never quite seemed to resolve into a single idea of any greater coherence than "they all lead to an indefinite search for an elusive thing." Fittingly, though, I've come to the conclusion that the paradox is best framed as an instance of bad specification, but a very particular kind of bad specification. Essentially, asking for "the least number with no description of less than thirty syllables" is asking for too much, because it requires the seeker to account for "all" descriptions, in order to prove that "none" of them violate the sought-after property. Of course, we can always narrow the scope of admissible descriptions, as we presumably did to produce A and A'. This reduces the problem to a question of "going through these finite sets in order, which is the first that contains no small things?" This question is considerably less provocative than a paradox, and the reader might join me in finding it substantially less interesting. The thrill of mystery, or the unexplained seems to be the fun of the paradox and, weirdly, constraining this away seems to give us something materially present (i.e. a halting program with output) but rather dull. Considering that people program and use computers with human motives, one must ask if we ever make paradoxical demands on our machines and attempt to implement them, only to find ourselves disappointed.

---

[1] Frege, Gottlob, J. L. Austin (Trans.). Foundations of Arithmetic. Northwestern University Press, 1968.