##
Chaitin’s Omega

Posted by geoffreyzheng under

Science and Technology
Leave a Comment
I made up my mind to read all my backlog magazines like DDJ, IEEE Spectrum, ACM Communications, etc. I read 08/04 DDJ today by not doing work for 1 hour 🙂

A very interesting article in Programming Paradigms column (need subscription) talks about digital universe, incompleteness of formal axiomatic systems, and Chaitin’s Omega.

Chaitin’s Omega is the probability that a particular Turing machine will eventully halt given an input of a truly random sequence of 0’s and 1’s.

Some interesting thoughts from the article: Math is empirical because of Gödel’s incompleteness theorem. The universe is a computation (computer + program) but there’s no other computation that’s faster, so the future is still unpredictable.

I read an abbreviated Chinese version of “Gödel, Escher, Bach: An Eternal Golden Braid” as a child and again lately and didn’t finish it either time. I should buy the English version soon.

The article also mentions that Steve Wolfram’s A New Kind of Science is available online in full text. Wish I could find time to read it…

UPDATE 03/06: March 2006’s Scientific American has an article by Gregory Chaitin himself explaining his omega. It’s based on Turing’s halting problem, stating that it’s impossible to answer generally whether a program will halt in a Turing machine. The precise definition of omega is \sum_{N=1}^{inf} \sum_{all N-bit programs that halt) (0.5^N). The binary value of omega is 0.110110001… (of course 0 and 1 are random) Omega is incompressible: you cannot use a program substantially shorter than N bits long to compute the first N bits of it. Because the binary omega is irrational, there’s an infinite number of digits that any finite-length program cannot compute. The general implication on a formal system is that it has infinite complexity, in other words to prove everything in it there must be an infinite number of axioms (irreducible principles).

UPDATE 12/09/05: I’ve bought GEB, so now I need to say “I should read the English version soon”…

UPDATE 11/23/07: From Gell-Mann’s Quark and Jaguar I learned that Chaitin was only in his late teens (17 when he started, according to his own time line) when he worked out these things. Wow.

### Like this:

Like Loading...

*Related*

## Leave a Reply