3 ms·

Chatlin's constant (http://en.wikipedia.org/wiki/Chaitin's_constant http://en.wikipedia.org/wiki/Chaitin's_constant), linked by Digital physics, is also very in

by aa0 13y ago

Chatlin's constant (http://en.wikipedia.org/wiki/Chaitin'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.

chriswarbo 13y ago
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 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.
andyjohnson0 13y ago
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/184354525X/ref=sr_1_2?s=books&ie=UTF8&qid=1375795373&sr=1-2 http://www.amazon.co.uk/Meta-Maths-Gregory-J-Chaitin/dp/1843... [2] http://arxiv.org/abs/math/0404335 http://arxiv.org/abs/math/0404335

by aa0 13y ago

chriswarbo 13y ago

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 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.

andyjohnson0 13y ago

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/184354525X/ref=sr_1_2?s=books&ie=UTF8&qid=1375795373&sr=1-2 http://www.amazon.co.uk/Meta-Maths-Gregory-J-Chaitin/dp/1843... [2] http://arxiv.org/abs/math/0404335 http://arxiv.org/abs/math/0404335