If I live in a universe which is not Turing computable but try and apply Solomonoff induction, I may end up in trouble—I may be unable to accept the existence of a black box for the halting problem, for example, even when believing in such a thing is useful. There are several possible solutions to this problem, but I have not seen any here which I find satisfactory.
My solution is this. Instead of considering a prior on the space of models for the universe (since you can’t really have a prior on the uncountable space of ways the universe could work if it weren’t as restricted as Solomonoff induction thinks it is) consider all computable strategies you could use to achieve whatever goal you are interested in (e.g., to predict what the universe will do next). Rather than disqualifying a model when it fails to conform to our expectations, we penalize a strategy (say by reducing its weight by some constant factor) when it fails to perform well (e.g., makes an incorrect prediction or fails to make a useful prediction) and follow the strategy which currently has the highest weight.
If your goal is predicting the next bit handed to you by the universe,
this is the same as Solomonoff induction where every model includes random noise. However, it can be argued convincingly that this is the correct way to incorporate the possibility of e.g. a black box for the halting problem into your world view, while it is not at all clear why Solomonoff induction is reasonable if the universe isn’t computable.
In general you get theoretical guarantees whenever you are trying to solve a problem which doesn’t have too much state—ie, in which it is very difficult to pursue a strategy so bad that it will ruin your current performance and all future performance. The proof is probably not surprising to anyone here, but it is worth pointing out that if you use a multiplicative update rule you get particularly fast convergence to a good prediction strategy (this is an infinite analog of multiplicative weights).
There is some question about why we restrict to computable strategies when implementing our induction procedure is already uncomputable. I don’t really want to include a discussion of this here, but if we are going to think about induction as a useful tool to apply in reality then we should probably adopt a view of it which doesn’t involve us solving the halting problem (for example, as a framework for evaluating suggestions as to what we should believe etc.). In this case it hopefully makes sense to restrict to computable strategies.
If I live in a universe which is not Turing computable but try and apply Solomonoff induction, I may end up in trouble—I may be unable to accept the existence of a black box for the halting problem, for example, even when believing in such a thing is useful. There are several possible solutions to this problem, but I have not seen any here which I find satisfactory.
My solution is this. Instead of considering a prior on the space of models for the universe (since you can’t really have a prior on the uncountable space of ways the universe could work if it weren’t as restricted as Solomonoff induction thinks it is) consider all computable strategies you could use to achieve whatever goal you are interested in (e.g., to predict what the universe will do next). Rather than disqualifying a model when it fails to conform to our expectations, we penalize a strategy (say by reducing its weight by some constant factor) when it fails to perform well (e.g., makes an incorrect prediction or fails to make a useful prediction) and follow the strategy which currently has the highest weight.
If your goal is predicting the next bit handed to you by the universe, this is the same as Solomonoff induction where every model includes random noise. However, it can be argued convincingly that this is the correct way to incorporate the possibility of e.g. a black box for the halting problem into your world view, while it is not at all clear why Solomonoff induction is reasonable if the universe isn’t computable.
In general you get theoretical guarantees whenever you are trying to solve a problem which doesn’t have too much state—ie, in which it is very difficult to pursue a strategy so bad that it will ruin your current performance and all future performance. The proof is probably not surprising to anyone here, but it is worth pointing out that if you use a multiplicative update rule you get particularly fast convergence to a good prediction strategy (this is an infinite analog of multiplicative weights).
There is some question about why we restrict to computable strategies when implementing our induction procedure is already uncomputable. I don’t really want to include a discussion of this here, but if we are going to think about induction as a useful tool to apply in reality then we should probably adopt a view of it which doesn’t involve us solving the halting problem (for example, as a framework for evaluating suggestions as to what we should believe etc.). In this case it hopefully makes sense to restrict to computable strategies.