Berry paradox

The smallest positive integer not nameable in under eleven words.

It is reasonable to assume that this is a specification for a number: after all, there are a finite number of sentences of less than eleven words, and some finite subset of them specify unique positive integers, so there is clearly some positive number that is the smallest integer not in that finite set.

But the Berry sentence itself is a specification for that number in only ten words!

This is clearly paradoxical, and seems to indicate that "nameable in under ten words" is not cleanly enough defined. Using programs or proofs of bounded lengths, one may in fact construct a rigorous version of the paradox; this has been done by Gregory Chaitin in order to produce an incompleteness theorem similar in spirit to Gödel's incompleteness theorem; see algorithmic information theory for an exposition.

The Berry paradox was actually created by Bertrand Russell, who named it after G. G. Berry[?]. Berry had provided the original idea in a letter to Russell about the less specific "the first ordinal that cannot be named in a finite number of words".

References

• Charles H. Bennett, "On Random and Hard-to-Describe Numbers", IBM Report RC7483 (1979) http://www.research.ibm.com/people/b/bennetc/Onrandom.pdf

External links

• http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unm2 A discussion by Gregory Chaitin
• http://www.cs.yorku.ca/~peter/Berry