#solomonoff induction

[tetraspace-west]

confused about the simplicity prior

From what I have heard of the simplicity prior, you assign probability 2^(-L) to each description of length L being the one that describes the environment. For each length L, there are 2^L possible descriptions of that length.

So the total probably you assign to all hypotheses is sum(2^(-L) * 2^(L)) = sum(1) = unnormalisable.

What am I missing?

[michaelgogins]

The Physical Church-Turing Thesis and Solomonoff Induction

I have just read through "Solomonoff Induction" by Thomas K. Sterkenburg (https://arxiv.org/pdf/2603.20274v1). I quote:

2.3. Universal optimality. One philosophical concern is the identification of universal reliability with reliability for computability, that is, reliability for all the ways the sequence under investigation could be computably generated. While certainly general, this is still a restriction, an inductive assumption (cf. Howson, 2000, p. 77). To maintain that this inductive assumption is truly universal is to commit to a stance that we will or can only ever encounter sequences that are computably generated, perhaps a “physical Church-Turing thesis” that nature is computable (see Copeland and Shagrir, 2020); a stance that is hard to evaluate.

I have two responses to this paragraph, which attempts with some (partial, in my view) success to expose circular reasoning in contemporary philosophy (of science in particular, and of metaphysics in general).

Any finite sequence can be computably generated.

Any non-terminating sequence might or might not be computably generated. A finite observed string is always computably generable; an infinite sequence may or may not be computable. If the infinite sequence is algorithmically random in the Martin-Löf / incompressibility sense, then it is not computable.

As Sterkenburg notes, whether a non-terminating sequence is computable (or, I would add, recursively enumerable) is "hard to evaluate." That's an understatement. It is impossible to evaluate. No finite empirical procedure can decide the unrestricted physical Church–Turing thesis, because every finite dataset is compatible both with computable and incomputable continuations.

Sterkenburg points out that Solomonoff induction as originally formulated was not quite precise, and could be diagonalized. But Solomonoff and Levin introduced semi-predictors corresponding to semi-measures on the conditional probabilities. In other words, by enabling the enumeration of predictors to include those that do not halt, can diagonalization be escaped? But!...

3.3. Diagonalization strikes again. Could we say that the Solomonoff-Levin semi-predictors are universally optimal predictors? To retrace the same kind of reasoning as in section 2.3, which started with the identification of the possible predictors with those predictors that are computable, we would now have to weaken the required level of computability, and still allow as possible predictors elements which are only semi-computable. The hope would be that we could then unite versions of Putnam’s two requirements on a universal predictor: a predictor that is universal for the class of possible predictors, while still being a legitimate predictor itself. On a first glance, it seems that with the Solomonoff-Levin semi-predictors we have exactly that. It follows directly from the fact that the Solomonoff-Levin semi-predictors are aggregating predictors for the semi-predictors corresponding to the semi-computable semi-measures that the Solomonoff-Levin semi-predictors are optimal among the semi-predictors corresponding to the semi computable semimeasures. Moreover, the Solomonoff-Levin semi-predictors are themselves semi-predictors corresponding to semi-computable semi-measures. There is, however, a catch. The weakened desideratum of computability—semi-computability—applies to the underlying probability measures. It does not necessarily carry over to the corresponding semi-predictors. Indeed, the Solomonoff-Levin semi-predictors are no longer semi-computable.

So Sterkenburg proves:

Theorem 6. The Solomonoff-Levin semi-predictors are not semi-computable.

Sterkenburg's discussion concludes in the context of machine learning: is there a universal prior on which learning models can be based? And the answer is, not so you can see it.

If there is no epistemically accessible universal prior, then predictive success gives no non-circular Solomonoff-style warrant for the physical Church–Turing thesis. Any induction to that thesis must rest on additional methodological or metaphysical assumptions about the character of physical law.

This may seem but a slight weakness in the physical Church-Turing thesis. However, if Nature involves lawlike relations between real quantities, let us not forget that the measure of uncomputable reals on any unit interval is 1. And almost all such values are uncomputable.

The gap between the uncomputable reals and the measured values that are, as we know, very very precisely predictable, is called, as a term of art, "effective."

In short, we cannot support the physical Church-Turing thesis; but we can support the effective physical Church-Turing thesis. For some philosophers, that is good enough. These philosophers are nominalists, or pragmatists. For others, it could never be good enough, because "effective" hides what is really going on. These philosophers are realists.

This post was evaluated and corrected with the assistance of ChatGPT 5.5.

[houshalter-blog]

Approximating Solomonoff Induction

Solomonoff Induction is a sort of mathematically ideal specification of machine learning. It works by trying every possible computer program and testing how likely they are to have produced the data. Then it weights them by their probability.

Obviously Solomonoff Induction is impossible to do in the real world. But it forms the basis of AIXI and other theoretical work in AI. It's a counterargument to the no free lunch theorem; that we don't care about the space of all possible datasets, but ones which are generated by some algorithm. It's even been proposed as a basis for a universal intelligence test.

Many people believe that trying to approximate Solomonoff Induction is the way forward in AI. And any machine learning algorithm that actually works, to some extent, must be an approximation of Solomonoff Induction.

But how do we go about trying to approximate true Solomonoff Induction? It's basically an impossible task. Even if you make restrictions to remove all the obvious problems like infinite loops/non-halting behavior. The space of possibilities is just too huge to reasonably search through. And it's discrete - you can't just flip a few bits in a program and find another similar program.

We can simplify the problem a great deal by searching through logic circuits. Some people disagree about whether logic circuits should be classified as Turing complete, but it's not really important. We still get the best property of Solomonoff Inducion; that it allows most interesting problems to be modelled much more naturally. In the worst case you have some overhead to specify the memory cells you need to emulate a turing machine.

Logic circuits have some nicer properties compared to arbitrary computer programs, but they still are discrete and hard to do inference on. To fix this we can easily make continuous versions of logic circuits. Go back to analog. It's capable of doing all the same functions, but also working with real valued states instead of binary.

Instead of flipping between discrete states, we can slightly increase connections between circuits, and it will only slightly change the behavior. This is very nice, because we have algorithms like MCMC that can efficiently approximate true bayesian inference on continuous parameters.

And we are no longer restricted to boolean gates, we can use any function that takes real numbers. Like a function that takes a sum of all of it's inputs, or one that squishes a real number between 0 and 1.

We can also look at how much changing the input of a circuit slightly, changes the output. Then we can go to all the circuits that connect to it in the previous time step. And we can see how much changing each of their input changes their output, and therefore the output of the first logic gate.

And we can go to those gates' inputs, and so on, chaining it all the way through the whole circuit. Finding out how much a slight change to each connection will change the final output. This is called the gradient, and we can then do gradient descent. Basically change each parameter slightly in the direction that increases the output the way we want.

This is a very efficient optimization algorithm. With it we can rapidly find circuits that fit functions we want. Like predicting the price of a stock given the past history, or recognizing a number in an image, or something like that.

But this isn't quite Solomonoff Induction. Since we are finding the best single model, instead of testing the space of all possible models. This is important because essentially each model is like a hypothesis. There can be multiple hypotheses which also fit the data yet predict different things.

There are many tricks we can do to approximate this. For example, if you randomly turn off each gate with 50% probability and then optimize the whole circuit to deal with this. For some reason this somewhat approximates the results of true bayesian inference. You can also fit a distribution over each parameter, instead of a single value, and approximate bayesian inference that way.

Although I never said it, everything I've mentioned about continuous circuits is equivalent to Artificial Neural Networks. I've shown how they can be derived from first principles. My goal was to show that ANNs do approximate true Solomonoff Induction. I've found the Bayes-Structure.

It's worth mentioning that Solomonoff Induction has some problems. It's still an ideal way to do inference on data, it just has problems with self-reference. An AI based on SI might do bad things like believe in an afterlife, or replace it's reward signal with an artificial one (e.g. drugs.) It might not fully comprehend that it's just a computer, and exists inside the world that it is observing.

Interestingly, humans also have these problem to some degree.

Comments on Lesswrong and Hacker News.