Qiaochu has already answered your question about SI, but to also attack your question about AIXI:
Careful about what you’re assuming. You’re implicitly assuming that the AI doesn’t know that what is being flipped is a random coin. If the AI had that knowledge, it could just replace all those convoluted descriptions with just a simple one: “Generate a pseudorandom number”. This would be just as effective as any other predictor, and indeed it would be very short and easy to run.
Now, what if the AI doesn’t know this? Then you are feeding it random numbers and expecting it to find order in them. In other words, you’re asking the hardest problem of all. It makes sense that it would expend a huge amount of computational power trying to find some order in random numbers. Put yourself in the computer’s place. How on Earth would you ever be able to know if the string of 0′s and 1′s you are being presented with is really just random or the result of some incredibly complicated computer program? No one’s telling you!
Finally, if the coin is actually a real physical coin, the computer will keep trying more and more complicated hypotheses until it has modelled your fingers, the fluid dynamics of the air, and the structure of the ground. Once it has done so, it will indeed be able to predict the outcome of the coin flip with accuracy.
Note that the optimality of AIXI is subject to several important gotchas. It is a general problem solver, and can do better than any other general problem solver, but there’s no guarantee that it will do better than specific problem solvers on certain problems. This is because a specifically-designed problem solver carries problem-specific information with it—information that AIXI may not have access to.
Even a very small amount of information (say, a few tens of bits) about a problem can greatly reduce the search space. Just 14 bits of information (two ASCII characters) can reduce the search space by a factor of 2^14 = 16384.
Qiaochu has already answered your question about SI, but to also attack your question about AIXI:
Careful about what you’re assuming. You’re implicitly assuming that the AI doesn’t know that what is being flipped is a random coin. If the AI had that knowledge, it could just replace all those convoluted descriptions with just a simple one: “Generate a pseudorandom number”. This would be just as effective as any other predictor, and indeed it would be very short and easy to run.
Now, what if the AI doesn’t know this? Then you are feeding it random numbers and expecting it to find order in them. In other words, you’re asking the hardest problem of all. It makes sense that it would expend a huge amount of computational power trying to find some order in random numbers. Put yourself in the computer’s place. How on Earth would you ever be able to know if the string of 0′s and 1′s you are being presented with is really just random or the result of some incredibly complicated computer program? No one’s telling you!
Finally, if the coin is actually a real physical coin, the computer will keep trying more and more complicated hypotheses until it has modelled your fingers, the fluid dynamics of the air, and the structure of the ground. Once it has done so, it will indeed be able to predict the outcome of the coin flip with accuracy.
Note that the optimality of AIXI is subject to several important gotchas. It is a general problem solver, and can do better than any other general problem solver, but there’s no guarantee that it will do better than specific problem solvers on certain problems. This is because a specifically-designed problem solver carries problem-specific information with it—information that AIXI may not have access to.
Even a very small amount of information (say, a few tens of bits) about a problem can greatly reduce the search space. Just 14 bits of information (two ASCII characters) can reduce the search space by a factor of 2^14 = 16384.