When a definition is too short to exist
The smallest positive integer not definable in under sixty letters.
Choose a counting mode to see how this phrase describes itself.
These words make the phrase refer to its own properties:
Watch the logical structure collapse as the definition tries to define itself.
Dear Mr. Russell,
I have been considering the paradoxes you mentioned, and I believe I have found another. Consider "the first ordinal not definable in a finite number of words." But this very phrase defines it in just a few words...
— G. G. Berry
Bodleian Library, Oxford
December 21, 1904
G. G. Berry (1867–1928) was a junior librarian at Oxford's Bodleian Library. Russell credited him with the paradox and published it in 1906.
Berry's Paradox formalizes as a proof that Kolmogorov complexity is uncomputable!
The paradox in code: Suppose we could compute K(x). Then we could write:
This short program would output a number requiring a long program to describe. Contradiction! Therefore K(x) is uncomputable.
Gregory Chaitin used Berry's Paradox to give an alternative proof of Gödel's incompleteness theorems, showing the deep connection between definability and provability.
Berry's Paradox underlies the proof that Kolmogorov complexity (the shortest program length) cannot be computed—a fundamental limit of computation.
The paradox reveals that "definability" is a slippery concept. What counts as a valid definition? Can definitions refer to themselves?
Like Russell's Paradox, Berry's suggests we need careful restrictions on self-reference. Modern logic uses type hierarchies to avoid such paradoxes.