Complexity-based induction systems: Comparisons and convergence theorems

In 1964 the author proposed as an explication of a priori probability the probability measure induced on output strings by a universal Turing machine with unidirectional output tape and a randomly coded unidirectional input tape. Levin has shown that if tildeP'₌ (x) is an unnormalized form of this measure, and P (x) is any computable probability measure on strings, x, then P'₌ (x) where C is a constant independent of x. The corresponding result for the normalized form of this measure, P'₌, is directly derivable from Willis' probability measures on nonuniversal machines. If the conditional probabilities of P'₌ are used to approximate those of P, then the expected value of the total squared error in these conditional probabilities is bounded by - (1/2) C. With this error criterion, and when used as the basis of a universal gambling scheme, P'₌ is superior to Cover's measure b. When H -₂ P'₌ is used to define the entropy of a rmite sequence, the equation H (x, y) = H (x) +H^ₗ (y) holds exactly, in contrast to Chaitin's entropy definition, which has a nonvanishing error term in this equation.