Proof of Impossibility - Is This String of 1's and 0's Random? Chaitin's Proof

Is This String of 1's and 0's Random? Chaitin's Proof

For an exposition suitable for non-specialists see Beltrami p. 108ff. Also see Franzen Chapter 8 pp. 137–148, and Davis p. 263-266. Franzén's discussion is significantly more complicated than Beltrami's and delves into Ω -- Gregory Chaitin's so-called "halting probability". Davis's older treatment approaches the question from a Turing machine viewpoint. Chaitin has written a number of books about his endeavors and the subsequent philosophic and mathematical fallout from them.

"A paraphrase of Chaitin's result is that there can be no formal proof that a sufficiently long string is random..." (Beltrami p. 109)

Beltrami observes that "Chaitin's proof is related to a paradox posed by Oxford librarian G. Berry early in the twentieth century that asks for 'the smallest positive integer than cannot be defined by an English sentence with fewer than 1000 characters.' Evidently, the shortest definition of this number must have at least 1000 characters. However, the sentence within quotation marks, which is itself a definition of the alleged number is less than 1000 characters in length!" (Beltrami, p. 108)