In addition to the issues raised by cousin_it I’d like to raise another related issue: If one uses a strict Solomonoff prior, then one can’t ever have a non-zero probability for a sequence to be uncomputable. So say for example we look at the first few thousand digits of the fine-structure constant in binary and find that they correspond exactly to some easily specifiable uncomputable sequence (say involving the Halting problem or the Busy Beaver function). An entity using Solomonoff induction cannot, no matter how many digits it sees, assign the obvious hypothesis any likelyhood.
I think this issue is a red herring. SI can be viewed as a purely predictive device that doesn’t assign probabilities to hypotheses, only to observable events. You will find that even if you’re endowed with the privileged knowledge that the fine structure constant is a halting oracle, that knowledge provably can’t help you win a prediction game against SI, because your computable brain is not very good at predicting a halting oracle. When you’re losing to a machine, saying it can’t “really entertain a hypothesis” is like saying a submarine can’t “really swim” or Rybka can’t “really play chess”.
You will find that even if you’re endowed with the privileged knowledge that the fine structure constant is a halting oracle, that knowledge provably can’t help you win a prediction game against SI
We can frequently compute the first several terms in a non-computable sequence, so this statement seems false.
In that case, I’d say that your response involves special pleading. SI priors are uncomputable. If the fine structure constant is uncomputable, then any uncomputable prior that assigns probability 1 to the constant having its actual value will beat SI in the long run. What is illicit about the latter sort of uncomputable prior that doesn’t apply to SI priors? Or am I simply confused somehow? (I’m certainly no expert on this subject.)
SI belongs to a class of priors that could be described as “almost computable” in a certain technical sense. The term is lower-semicomputable semimeasure. An interesting thing about SI is that it’s also optimal (up to a constant) within its own class, not just better than all puny computable priors. The uncomputable prior you mention does not belong to that class, in some sense it’s “more uncomputable” than SI.
An entity using Solomonoff induction cannot, no matter how many digits it sees, assign the obvious hypothesis any likelyhood.
Uncomputable sequences have computable approxiomations. Solomonoff induction could do very well at predicting such sequences. However, it wouldn’t assume that they are uncomputable. Why should it? That is a bizarre hypothesis—not an “obvious” one. It is surely more likely that the observed finite prefix was generated by some computable method.
Solomonoff induction only deals with finite sequences. It doesn’t assign p=0 to any sequence consistent with its observations so far. Uncomputable sequences are necessarily inifinite—and though Solomonoff induction can’t handle them, neither can the observable universe. I think that the case that they matter remains to be made.
In addition to the issues raised by cousin_it I’d like to raise another related issue: If one uses a strict Solomonoff prior, then one can’t ever have a non-zero probability for a sequence to be uncomputable. So say for example we look at the first few thousand digits of the fine-structure constant in binary and find that they correspond exactly to some easily specifiable uncomputable sequence (say involving the Halting problem or the Busy Beaver function). An entity using Solomonoff induction cannot, no matter how many digits it sees, assign the obvious hypothesis any likelyhood.
I think this issue is a red herring. SI can be viewed as a purely predictive device that doesn’t assign probabilities to hypotheses, only to observable events. You will find that even if you’re endowed with the privileged knowledge that the fine structure constant is a halting oracle, that knowledge provably can’t help you win a prediction game against SI, because your computable brain is not very good at predicting a halting oracle. When you’re losing to a machine, saying it can’t “really entertain a hypothesis” is like saying a submarine can’t “really swim” or Rybka can’t “really play chess”.
We can frequently compute the first several terms in a non-computable sequence, so this statement seems false.
When people talk about the impossibility of “winning” against SI, they usually mean it’s impossible to win by more than a constant in the long run.
In that case, I’d say that your response involves special pleading. SI priors are uncomputable. If the fine structure constant is uncomputable, then any uncomputable prior that assigns probability 1 to the constant having its actual value will beat SI in the long run. What is illicit about the latter sort of uncomputable prior that doesn’t apply to SI priors? Or am I simply confused somehow? (I’m certainly no expert on this subject.)
SI belongs to a class of priors that could be described as “almost computable” in a certain technical sense. The term is lower-semicomputable semimeasure. An interesting thing about SI is that it’s also optimal (up to a constant) within its own class, not just better than all puny computable priors. The uncomputable prior you mention does not belong to that class, in some sense it’s “more uncomputable” than SI.
Uncomputable sequences have computable approxiomations. Solomonoff induction could do very well at predicting such sequences. However, it wouldn’t assume that they are uncomputable. Why should it? That is a bizarre hypothesis—not an “obvious” one. It is surely more likely that the observed finite prefix was generated by some computable method.
Being a less likely hypothesis is not the same thing as having probability zero.
Solomonoff induction only deals with finite sequences. It doesn’t assign p=0 to any sequence consistent with its observations so far. Uncomputable sequences are necessarily inifinite—and though Solomonoff induction can’t handle them, neither can the observable universe. I think that the case that they matter remains to be made.