Problem: Universal M(x) not recursive

• M(x): Optimal but infeasible inductive inference

• More feasible watered-down approaches:

• Minimum description length (MDL, Wallace & Boulton 1968, Rissanen 1986)

• Priors based on (polynomial) time bounds (Li & Vitanyi 1997)

• But lack of obvious, plausible, a priori justification

• Which prior reflects “correct” simplicity bias?

• Next: “simple” means “quickly computable”!

Previous slide

Next slide

Back to first slide

View graphic version