"The Solomonoff prior is not computed from the s..."


by Gurkenglas Gurkenglas Sep 23 2017 updated Sep 23 2017

The Solomonoff prior is not computed from the space each hypothesis needs to compute its answer, it's its program length, the space needed to pass the hypothesis to our UTM!

Any other form of induction one could try, like the space or time complexities of evaluating a hypothesis you described, or other machine models that Turing machines can describe, or human intuition, is included by Solomonoff induction as a hypothesis, and will replace it after finite error if it outperforms.

How would you even compute each program's space/time complexity? Rice's theorem says it cannot be done in general.