3 ms·
It's a mathematical device for reasoning about compressibility. It's like saying "What's the use of Shannon Entropy of fixed strings?" Algorithmic information
by cromwellian 13y ago
It's a mathematical device for reasoning about compressibility. It's like saying "What's the use of Shannon Entropy of fixed strings?"
Algorithmic information theory also allows you to re-derive Godel's Incompleteness Theorem or the Halting Theorem from it, in a sense, it's a super-set of those concepts.
For example, we can talk about the compression of knowledge into finite sets of axioms and many bits of information exist in such a system.
Or we can reason about concepts like Omega, a truly random number in mathematics, incompressible in the sense then there is provably no shorter way to encode it other than brute force calculating it, but which is a real number, and which we can know the first few bits of it. (and a quite interesting number in the sense that it's an Oracle of knowledge and if you had it's complete expansion, you could solve many questions in mathematics with it)
- kcanini 13y agoInteresting. Is this the Omega you're referring to? http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant