The Berry paradox (Q1361183)

G. Chaitin, one of the authors of the notion often known as \textit{Kolmogorov complexity}, gives a short popular introduction to his main ideas, by reproducing a presentation that he prepared for a 1974 meeting with Gödel, a meeting which, unfortunately, was cancelled. Gödel's incompleteness result, that no algorithm can check whether a given arithmetic statement is true or false, came from his formalization of the known Liar paradox. In this paradox, a person says ``Everything I said today is false''. If this statement is true, it must be false; if this statement is false, it must therefore be true. Gödel's careful formalization of this statement (outlined in the paper under review) lead not to a paradox but to a proof. Chaitin realized that the same incompleteness result could be obtained by formalizing a different paradox, which was originally proposed by G. G. Berry: ``The first positive integer which cannot be specified in less than a billion words'' should be non-specifiable in less than a billion words, but it has the (above) 14-word specification. Chaitin has shown that not only the formalization of this paradox (in which ``specified'' is formalized as ``computed by a program on a universal Turing machine'') leads to a new proof of Gödel's incompleteness theorem, but also that the resulting formal notion of the smallest length \(C(x)\) of the program (``specification'') that computes (``specifies'') the number \(x\) is an extremely useful notion (this notion \(C(x)\) was also independently discovered by A. Kolmogorov and R. Solomonoff and is often called Kolmogorov complexity).