On Mon, Dec 10, 2012 at 5:24 PM, Aaron Hosford <[email protected]> wrote: > Kolmogorov complexity is measured relative to an implicit descriptive > language. If we were to order algorithms by their Kolmogorov complexity > relative to a specific descriptive language, choosing a different > descriptive language could result in a complete reversal of that ordering, > or possibly any arbitrary ordering. K-complexity is thus inherently > unmeasurable without specifying the descriptive language. (Compression > algorithms take advantage of this by generating a mapping to a new language > for which the K-complexity of the data is much smaller.)
Surely you know that Kolmogorov complexity is independent of language up to a constant that depends on the choice of language but not on the input. For any of the common programming languages like C++ or Lisp, this constant will be small compared to the 2.5 x 10^7 bits that I estimate for the human genome. http://en.wikipedia.org/wiki/Kolmogorov_complexity Of course one can always argue that a smaller program exists. There is no general method to prove a lower bound on complexity. For example, a random appearing string of any length might actually be an encrypted string of zero bits and therefore have a complexity of only a few hundred bits. There is no way to know without trying every possible key. It is theoretically possible that there is a small program of a few hundred bits that outputs your DNA. But that seems unlikely because we know how evolution works. Any such program would have to work completely differently. You could not write your DNA by specifying a sequence of mutations and slice copies unless that sequence was very long. My argument for high complexity is that both evolution and humans have failed to find a short, elegant description of the human brain. For evolution, we can look at variation in genome size among species. There is a wide range even for similar species (due to copying), but a consistent trend of longer genomes for higher life forms in spite of evolutionary pressure to find more efficient codings (which would enable faster reproduction). http://www.genomesize.com/statistics.php Of course many people claim to have short programs that solve AI, or should solve it once their program is finished, which never seems to happen for one reason or another. It is the same with many other problems that we can't prove are impossible, like P = NP, or even problems that we can prove impossible, like recursive compression. Human brains are programmed to like elegant solutions because they have high predictive power. -- Matt Mahoney, [email protected] ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
