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)
Read more about this topic: Proof Of Impossibility
Famous quotes containing the words string and/or proof:
“Amongst the learned the lawyers claim first place, the most self-satisfied class of people, as they roll their rock of Sisyphus and string together six hundred laws in the same breath, no matter whether relevant or not, piling up opinion on opinion and gloss on gloss to make their profession seem the most difficult of all. Anything which causes trouble has special merit in their eyes.”
—Desiderius Erasmus (c. 1466–1536)
“There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
—Herman Melville (1819–1891)