On a recent episode of The Bayesian Conspiracy, the time-complexity prior was mentioned as a plausible alternative to Solomnoff induction. And reading Abram Demski’s explanation of logical induction in Toward a New Technical Explanation of Technical Explanation, a prior over time-complexity seems like a natural consequence of the formulation.
Can anyone provide sources for more information on this, assuming such sources exist?
Two relevant papers:
The Speed Prior: A New Simplicity Measure Yielding Near-Optimal Computable Predictions by Jürgen Schmidhuber
Loss Bounds and Time Complexity for Speed Priors by myself, Jan Leike, and Marcus Hutter
You probably also want to know about Kt complexity, called Levin complexity here, which I believe is covered in Li and Vitányi’s textbook on Kolmogorov complexity.
Comment
Thanks!