News for hackers. Stuff that matters.
Re:Digital physics by aa0 on Tuesday August 06, 2013 @04:56AM (#6165531)
Chatlin's constant (http://en.wikipedia.org/wiki/Chaitin's_constant), linked by Digital physics, is also very interesting. It is the probability that a random program will halt. When we get into 'random program' all kinds of interesting questions come up.

For me, I immediately think of:

What instruction set are we considering? Is the instruction set bounded by human language?

Human language does not have the same extent as thought -- or does it? Is the indescribable as cardinal as the unthinkable?

What is the Chatlin's constant for average human thought process.. ie. a subset of our brain programming?

Man, what an interesting subject.

Re:Digital physics by chriswarbo on Tuesday August 06, 2013 @05:23AM (#6165606)
The instruction set doesn't matter. To calculate (the first few bits of) Chaitin's Constant we can enumerate and run every program in some instruction set, say x86 assembly, and measure the proportion of programs which eventually halt. One efficient way to do this is to interleave their executions using FAST http://www.idsia.ch/~juergen/toesv2/node28.html

Any (Turing-complete) instruction set can be translated/compiled/interpreted-by any other (Turing-complete) instruction set, given a suitable translator/compiler/interpreter. Since we're running all programs, we will eventually run all translators/compilers/interpreters, so no matter what instruction set we choose, we will start running programs from every other. The longer we leave it running, the more of a mixture we end up with. Since Chaitin's Constant is the (uncomputable) result of letting such a scheme run forever, it contains a perfect mixture of all instruction sets, and is thus independent of whichever one we choose.

Re:Digital physics by andyjohnson0 on Tuesday August 06, 2013 @09:28AM (#6166416)
For a deep look at Omega (Chaitin's constant) I'd recommend Chaitin's book Meta Math: The Quest for Omega [1]. A fascinating book.

Chaitin has also uploaded the full text (pdf) of the book to Arxiv.org [2].

[1] http://www.amazon.co.uk/Meta-Maths-Gregory-J-Chaitin/dp/1843...

[2] http://arxiv.org/abs/math/0404335