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:
“... looped with the creep of varying light,
Monkey-brown, fish-grey, a string of infected circles
Loitering like bullies, about to coagulate....”
—Philip Larkin (1922–1986)
“He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
—Herman Melville (1819–1891)