Free Republic
Browse · Search
Smoky Backroom
Topics · Post Article

To: Alamo-Girl
I cannot copy the file. When I click on the link I get the 404 error too. However, I could get to look at the file by searching Google using: "chaitin omega first bits" as the search terms.
4,638 posted on 01/12/2003 11:38:49 AM PST by Doctor Stochastic (omega=.0000000000000000000010000001000000100000010000010000011100100111000....)
[ Post Reply | Private Reply | To 4633 | View Replies ]


To: Doctor Stochastic
Thank you so much for the information on how to retreive that document!

I finished reading it and naturally went looking for Chaitin's response, which I found at Paradoxes of Randomness - Complexity Vol. 7, No. 5, May/June 2002, pp. 14-21:

And that means that not only you can't compress it into a smaller algorithm, you can't compress it into fewer bits of axioms. So if you wanted to be able to determine K bits of Omega, you'd need K bits of axioms to be able to prove what K bits of this number are. It has---its bits have---no structure or pattern that we are capable of seeing.

However, you can prove all kinds of nice mathematical theorems about this Omega number. Even though it's a specific real number, it really mimics independent tosses of a fair coin. So for example you can prove that 0's and 1's happen in the limit exactly fifty percent of the time, each of them. You can prove all kinds of statistical properties, but you can't determine individual bits!

So this is the strongest version I can come up with of an incompleteness result...

Actually, in spite of this, Cristian Calude, Michael Dinneen and Chi-Kou Shu at the University of Auckland have just succeeded in calculating the first 64 bits of a particular Omega number. The halting probability Omega actually depends on the choice of computer or programming language that you write programs in, and they picked a fairly natural one, and were able to decide which programs less than 85 bits in size halt, and from this to get the first 64 bits of this particular halting probability.

This work by Calude et al. is reported on page 27 of the 6 April 2002 issue of the British science weekly New Scientist, and it's also described in Delahaye's article in the May 2002 issue of the French monthly Pour la Science, and it'll be included in the second edition of Calude's book on Information and Randomness, which will be out later this year.

But this doesn't contradict my results, because all I actually show is that an N-bit formal axiomatic theory can't enable you to determine substantially more than N bits of the halting probability. And by N-bit axiomatic theory I mean one for which there is an N-bit program for running through all possible proofs and generating all the theorems. So you might in fact be able to get some initial bits of Omega.

Verrry interesting! Thanks for the heads up to this property of Omega.

4,640 posted on 01/12/2003 1:38:12 PM PST by Alamo-Girl
[ Post Reply | Private Reply | To 4638 | View Replies ]

Free Republic
Browse · Search
Smoky Backroom
Topics · Post Article


FreeRepublic, LLC, PO BOX 9771, FRESNO, CA 93794
FreeRepublic.com is powered by software copyright 2000-2008 John Robinson