Kolmogorov proved there is no such thing as an infinitely powerful compressor. Not even if you have infinite computing power.
A compressor is a program that inputs a string and outputs a short description of it, like another string encoding a program in some language that outputs the original string. A string is a finite length sequence of 0 or more characters from a finite alphabet such as binary or ASCII. Strings can be ordered like numbers, by increasing length and lexicographically for strings of the same length. Suppose you had an infinitely powerful compressor, one that inputs a string and outputs the shortest possible description of it. You could use your program to test whether another compressor found the best possible compression by decompressing it and compressing again with your compressor to see if it got any smaller. The proof goes like this. How does your test program answer "the first string that cannot be described in less than 1,000,000 characters"? On Tue, May 7, 2024 at 5:50 PM John Rose <johnr...@polyplexic.com> wrote: > > On Tuesday, May 07, 2024, at 10:01 AM, Matt Mahoney wrote: > > We don't know the program that computes the universe because it would require > the entire computing power of the universe to test the program by running it, > about 10^120 or 2^400 steps. But we do have two useful approximations. If we > set the gravitational constant G = 0, then we have quantum mechanics, a > complex differential wave equation whose solution is observers that see > particles. Or if we set Planck's constant h = 0, then we have general > relativity, a tensor field equation whose solution is observers that see > space and time. Wolfram and Yudkowsky both estimate this unknown program is > only a few hundred bits long, and I agree. It is roughly the complexity of > quantum mechanics and relativity taken together, and roughly the minimum size > by Occam's Razor of a multiverse where the n'th universe is run for n steps > until we observe one that necessarily contains intelligent life. > > > Sounds like the KC of U, the maximum lossless compression of the universe > assuming infinite resources for perfect prediction. But there is a lot of > lossylosslessness out there for imperfect prediction or locally perfect > lossless, near lossless, etc. That intelligence has a physical computational > topology across spacetime where much is redundant though estimable… and > temporally changing. I don’t rule out though no matter how improbable that > there could be an infinitely powerful compressor within this universe, an > InfiniComp. Weird stuff has been shown to be possible. We can conceive of it > but there may be issues with our conception since even that is bound by > limits. > > Artificial General Intelligence List / AGI / see discussions + participants + > delivery options Permalink -- -- Matt Mahoney, mattmahone...@gmail.com ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/Teaac2c1a9c4f4ce3-Mdbff080b9764f7c48d917538 Delivery options: https://agi.topicbox.com/groups/agi/subscription
