4 ms·
It's Ω / Chaitin's constant for a particular encoding. It's uncomputable as a whole, but maybe we will get a couple more bits.
by Vecr 2y ago
It's Ω / Chaitin's constant for a particular encoding. It's uncomputable as a whole, but maybe we will get a couple more bits.
- HappMacDonald 2y agoAlright then how does that help anyone with text compression, and/or how would computing it's digits reveal any deep secrets of mathematics?
- Xcelerate 2y agoSee my other reply. It’s not Chaitin’s constant but the mutual information between ZFC and the halting sequence, which is precisely I(ZFC : H) bits. If you had H, you could optimally compress any non-random string of data of length n in O(n) time. The rough sketch of how you would do this is to create brute-force search programs and then instead of actually running them just look up whether they halt or not via the halting sequence. By chaining together a few of these μ-operator functions, you can build up the whole compressed string 1 bit at a time. Since we only have a few bits of H, we can’t compress at that level of magic, but what we do have still represents everything computable that ZFC can describe, which for the most part includes every algorithm we use in daily life.