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?

New Answer
New Comment

1 Answers sorted by

DanielFilan

110

Two relevant papers:

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.