Because what matters is not whether the universe is computable, but whether our methods of reasoning are computable. Or in other words, whether the map is computable. Solomonoff's induction is at least as "good" as any computable inference method (up to a constant), regardless of the complexity of the universe. So if you, as a human, are trying to come up with a systematic way to predict things (even uncomputable things), Solomon's induction is better.

Note that Solomonoff induction is not itself computable.

If the environment has uncomputable features, Alice's hypotheses act like oracle machines. She can't predict those features, but she can use them to predict other features of the environment.

I don't think this is straightforwardly true, because Solomonoff induction does not seem to be capable of learning the statistical dependency, i.e. while Solomonoff induction agrees that the digits known so far have been spookily predictive, it thinks this is just a coincidence and that further digits have no reason to be predictive.

I've always thought of it like, it doesn't rely on the universe being computable, just on the universe having a computable approximation. So if the universe is computable, SI does perfectly, if it's not, SI does as well as any algorithm could hope to.

This post seems to be about justifying why Solomonoff induction (I presume) is a good way to make sense of the world. However, unless you use it as another name for "Bayesian reasoning", it clearly isn't. Rather, it's a far-removed idealization. Nobody "uses" Solomonoff induction, except as an idealized model of how very idealized reasoning works. It has purely academic interest. The post sounds (maybe I'm misunderstanding this completely) like this weren't the case, e.g., discussing what to do about a hypothetical oracle we might find.

In practice, humanity will only ever care about a finite number of probability distributions, each of which has finite support and will be updated a finite number of times using finite memory and finite processing power. (I guess one might debate this, but I personally usually can't think of anything interesting to say in that debate) As such, for all practical purposes, the solution to any question that has any practical relevance is computable. You could also put an arbitrary fixed but very large bound on complexity of hypotheses, keeping all hypotheses we might ever discuss in the race, and thus make everything computable. This would change the model but make no difference at all in practice, since the size of hypotheses we may ever actually assess is miniscule. The reason why we discus the infinite limit is because it's easier to grasp (ironically) and prove things about.

Starting from this premise, what is this post telling me? It's saying something about a certain idealized conception of reasoning. I can see how to transfer certain aspects of Solomonoff induction to the real world: you have Occam's razor, you have Bayesian reasoning. Is there something to transfer here? Or did I misunderstand it completely, leading me to expect there to be something?

Of course, I'm not sure if this "focus on finite things and practicality" is the most useful way to think about it, and I've seen people argue otherwise elsewhere, but always very unconvincingly from my perspective. Perhaps someone here will convince me that computability should matter in practice, for some reasonable concept of practice?

Because what matters is not whether the universe is computable, but whether our methods of reasoning are computable. Or in other words, whether the map [? · GW] is computable. Solomonoff’s induction is at least as “good” as any computable inference method (up to a constant), regardless of the complexity of the universe. So if you, as a human, are trying to come up with a systematic way to predict things (even uncomputable things), Solomonoff’s induction is better. Here is the precise statement:

The claim that SI is at least as good as human reasoning is a relative claim. If human reasoning is limited or useless in absolute terms, so is SI.

Also , there is no proof that human reasoning would still be computable in a hypercomputational universe. We don't have separate evidence about the world and the mind. That's the computational circle.

But then I realized this understanding of why to use Solomonoff induction is incorrect. We do not use it because of the physical church-turing thesis, we use it because of the original church-turing thesis:

We don't use it, on the whole.

Because what matters is not whether the universe is computable, but whether our methods of reasoning are computable

Rationalists like Yudkowsky make more extensive claims than the mainstream about SI, specifically that it is a formalised epistemology ... in fact a complete formalised ontology, that tells you what reality is, capable of solving long standing philosophical problems, and not restricted to making predictions.

So they think SI actually is revealing the territory. In saying that it is only concerned with the map, you are going back to the relatively modest, mainstream view of SI.

"Solomonoff's theory of inductive inference is a mathematical proof that if a universe is generated by an algorithm, then observations of that universe, encoded as a dataset, are best predicted by the smallest executable archive of that dataset"

An uncomputable universe doesnt have to be a computable universe with an oracle bolted on. For instance, a universe containing an SI has to be uncomputable.

An uncomputable universe doesnt have to be a spooky. Classical physics isn’t exactly computable, because some systems are critically dependent on their initial conditions, and an exact specification of the initial conditions requires an infinite amount of information (unlimited precision real number). The supposedly weird theiry of quantum mechanics is more computable than the supposedly intuitive theory of classical physics.

There is another problem with Solomonoff Induction: Overfitting. It only consideres hypotheses which predict the past data perfectly, and only based on that, it predicts future data.

If a Solomonoff inductor (like AIXI) observes its environment with a digital camera, it will only consider predictions about the future made by hypotheses which perfectly predict the past camera data, including random noise.

But the noise is very irrelevant for what the future will most likely be. Maybe there is a much simpler hypothesis, which retrodicts the past data only approximately, but which makes much better predictions, because the most successful theories are those which trade-off simplicity of a hypothesis with its fit to the "training sample", in this case, the data observed in the past.

It is often said that successful prediction has a lot to do with compression. But it has a lot to do with lossy compression, not lossless compression. Solomonoff Induction relies entirely on lossless compression, and so it overfits. When animals or humans make predictions based on past observation, they don't normally pick a hypothesis which predicts the past observations perfectly, because this hypothesis would be unnecessarily complex and would make, consequently, probably bad predictions.

Solomonoff induction optimizes not for both simplicity and fit, it demands perfect fit first and only then optimizes for simplicity, but this simplicity might not very simple at all.

Consider again the noisy input from the camera. The SI compression is like compressing all the camera frames as PNG, a lossless image format. The compression rate on video frames or photos is terrible with PNG, because photos contain a lot of noise and little ordered data which could be well compressed with a lossless algorithm. In photos or video frames JPEG (a lossless format) gives a result which has still pretty good quality but is massively smaller.

So how much better would Solomonoff Induction be than PNG on noisy data like photos? I think not much better. SI would be much better than PNG on some images without noise, which contain e.g. something like a large Game of Life board. SI would figure out the simple GoL algorithm which generated the image, and PNG wouldn't. But I see no reason why SI would be significantly better on noisy data.

Okay, maybe the noise and the whole universe is deterministic (some deterministic interpretation of QM, like Bohemian mechanics, is true). Then SI could perhaps deduce the laws of nature and the initial conditions of the universe with high confidence from some amount of video data, which would compress the past data incredibly well and which would give it excellent prediction capabilities, similar to Laplace's demon.

Is this plausible? Even if the camera noise is perfectly determined by the laws and the initial conditions of the universe, it seems not clear whether SI could deduce them, since random noise is not the only sort of uncertainty. Another source is indexical uncertainty. Many different space time locations in the universe may be consistent with the available data, and different laws / initial conditions may make different predictions for different locations. So the space of possible laws / initial conditions may not be very strongly constrained by the available data. Then a system which trades off simplicity and fit could perhaps still beat Solomonoff prediction.

Moreover, even the deterministic Many Worlds interpretation of quantum mechanics would lead to unpredictable noise for the Solomonoff inductor, again because of indexical uncertainty: It doesn't know in which of the many worlds it is located in, so it must regard it's location as random, which is equivalent to regarding the noise as random.

So it seems SI would most likely fail against conventional intelligences (which make a trade-off between fit and simplicity) in indeterministic or Many Worlds universes, because this leads to (real or pseudo) indeterministic noise which can't be well compressed/predicted losslessly. And for deterministic Bohemian mechanics style universes, the success of SI is questionable because of indexical uncertainty about space time location.

The problem of Solomonoff induction having 100% probability in being a computable isn't actually, by itself logically contradictory with seeing universes that are uncomputable.

Now, to address the post's claims:

Because what matters is not whether the universe is computable, but whether our methods of reasoning are computable. Or in other words, whether the map is computable.

So to answer the question, the answer is basically yes, because of the fact that humans have a finite and fixed memory + finite speed of computation, meaning that it's trivial to compute all reasoning strategies that a human does by a Turing Machine.

In general the Church-Turing thesis that the set of reasoning strategies/the set of computers is equal to the set of Turing machines is false, as the set of computers/the set of reasoning strategies are way, way bigger than the set of Turing machines.

So either the Church-Turing thesis is tautologically true, or if we wanted to generalize it is simply false.

So Solomonoff induction, as it's usually considered would beat any strategy that's computable, or recursively enumerable strategies that doesn't have the complement of the set, but compared to the set of all computers/strategies as we currently know of, Solomonoff induction doesn't do very well, as it's only on the first floor of a halting oracle, or equivalently it's at the 2nd floor of the arithmetical hierarchy, but compared to the vastness of reasoning and computation, it's still way, way worse than the current optimal reasoners/optimal computers in math. It's superior to the Accelerating Turing Machine, an uncomputable machine, and superior to all other computable strategies, but is inferior to the Malament-Hogarth machine, possibly an infinite time turing machine depending on how many time steps we allow, and the 3 equivalent current champions of reasoning machines/computers.

1. The infinite state turing machine.

2. The Blum-Shub-Smale machine over the reals.

3. A recurrent neural network with real valued weights with exponential time to compute.

Solomonoff induction isn't ideal, compared to the current champions of computation/reasoning engines.

Does this chatlin's constant differ for different Turing machines and their instruction sets?