No. AIXItl will need to have other complexity—if you want it to work in a reasonable quantity of time—e.g. see, for example:
“Elimination of the factor 2˜l without giving up universality will probably be a very difficult task. One could try to select programs p and prove VA(p) in a more clever way than by mere enumeration. All kinds of ideas like, heuristic search, genetic algorithms, advanced theorem provers, and many more could be incorporated.”″
It seems that you think “complex” means “difficult.” It doesn’t. Complex means “requires a lot of information to specify.” There are no simple problems with complex solutions, because any specification of a problem is also a specification of its solution. This is the point of my original post.
So: a galaxy-conquering civilisation has low Kolmogorov complexity—because it has a short description—namely “a galaxy-conquering civilisation”???
If you actually attempted to describe a real galaxy-conquering civilisation, it would take a lot of bits to specify which one you were looking at—because the method of getting there will necessarily have involved time-and-space constraints.
Those bits will have come from the galaxy—which is large and contains lots of information.
More abstractly, “Find a root of y = sin(x)” is a simple problem with many K-complex solutions. Simple problems really can have K-complex solutions.
A particular galaxy-conquering civilization might have high Kolmogorov complexity, but if you can phrase the request “find me a galaxy-conquering civilization” using a small number of bits, and if galaxy-conquering civilizations exist, then there is a solution with low Kolmogorov complexity.
Hmm, okay. I should not have said “there are no simple problems with complex solutions.” Rather, there are no simple problems whose only solutions are complex. Are we in agreement?
Gah, don’t over-qualify jokes! It’s a supplicating behavior and seeking permission to be funny blunts the effect. Just throw the “X^2 = −1” out there (which is a good one by the way) and then go on to say “A more serious counterexample”. That’s more than enough for people to ‘get it’ and anyone who doesn’t will just look silly.
This is the Right (Wedrifid-Laughter-Maximising) thing to do.
How about: what is the smallest number that can’t be described by an English sentence of less than ten thousand words? ;-)
Of course, knowing that a K-simple solution existed in the form of the problem specification would not help very much in constructing/implementing it.
If you’re referring to the parameters t and l, I’ll suggest a googolplex as a sufficiently large number with low Kolmogorov complexity.
No. AIXItl will need to have other complexity—if you want it to work in a reasonable quantity of time—e.g. see, for example:
“Elimination of the factor 2˜l without giving up universality will probably be a very difficult task. One could try to select programs p and prove VA(p) in a more clever way than by mere enumeration. All kinds of ideas like, heuristic search, genetic algorithms, advanced theorem provers, and many more could be incorporated.”″
http://www.hutter1.net/ai/paixi.pdf
It seems that you think “complex” means “difficult.” It doesn’t. Complex means “requires a lot of information to specify.” There are no simple problems with complex solutions, because any specification of a problem is also a specification of its solution. This is the point of my original post.
So: a galaxy-conquering civilisation has low Kolmogorov complexity—because it has a short description—namely “a galaxy-conquering civilisation”???
If you actually attempted to describe a real galaxy-conquering civilisation, it would take a lot of bits to specify which one you were looking at—because the method of getting there will necessarily have involved time-and-space constraints.
Those bits will have come from the galaxy—which is large and contains lots of information.
More abstractly, “Find a root of y = sin(x)” is a simple problem with many K-complex solutions. Simple problems really can have K-complex solutions.
A particular galaxy-conquering civilization might have high Kolmogorov complexity, but if you can phrase the request “find me a galaxy-conquering civilization” using a small number of bits, and if galaxy-conquering civilizations exist, then there is a solution with low Kolmogorov complexity.
Hmm, okay. I should not have said “there are no simple problems with complex solutions.” Rather, there are no simple problems whose only solutions are complex. Are we in agreement?
Joke counterexample:
x^2 = −1 is a simple problem that only has complex solutions. ;)
(Of course, that’s not the meaning of “complex” that you meant.)
Serious counterexample:
The four-color theorem is relatively simple to describe, but the only known proofs are very complicated.
Gah, don’t over-qualify jokes! It’s a supplicating behavior and seeking permission to be funny blunts the effect. Just throw the “X^2 = −1” out there (which is a good one by the way) and then go on to say “A more serious counterexample”. That’s more than enough for people to ‘get it’ and anyone who doesn’t will just look silly.
This is the Right (Wedrifid-Laughter-Maximising) thing to do.
I’m sorry. :(
Was that a practical joke on wedrifid?
It is now!
Nice. Die. :P
But that complicated proof could be concisely provided via a universal proof algorithm and the statement of the four color theorem.
Exactly! The Kolmogorov complexity is not very high.
I am not sure.
How about: what is the smallest number that can’t be described by an English sentence of less than ten thousand words? ;-)
Of course, knowing that a K-simple solution existed in the form of the problem specification would not help very much in constructing/implementing it.