4 ms·

If we aren't concerned about the Kolmogorov complexity of any fixed finite strings, then what exactly is it useful for?

• cromwellian 12y 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 12y ago
    Interesting. Is this the Omega you're referring to? http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant