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:
“First you find a little thread, a little thread leads you to a string, and the string leads you to a rope. And from the rope you hang by the ... neck.”
—A.I. (Albert Isaac)
“Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
—Henry David Thoreau (1817–1862)