Speed Prior-Based Inductive Inference

Given , as we observe an initial segment of some string,
which is the most likely continuation?
According to Bayes,

**Proof.**
Since no program that requires at least steps for producing
can compute in a PHASE with number , we have

Here we have used the Kraft inequality [13] to obtain a rough upper bound for the enumerator: when no is prefix of another one, then

Hence, if we know a rather fast finite program for , then Theorem
1 allows for predicting: if we observe some (
sufficiently large) then it is very unlikely that it was produced by an
-computing algorithm much slower than .

Among the fastest algorithms for is **FAST** itself, which is at
least as fast as , save for a constant factor. It outputs after
steps.

Back to Speed Prior page