Complexity-based induction systems: Comparisons and convergence theorems

In 1964 the author proposed as an explication of {em 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 iftilde{P}'_{M}(x)is an unnormalized form of this measure, andP(x)is any computable probability measure on strings,x, thentilde{P}'_{M}geqCP(x)whereCis a constant independent ofx. The corresponding result for the normalized form of this measure,P'_{M}, is directly derivable from Willis' probability measures on nonuniversal machines. If the conditional probabilities ofP'_{M}are used to approximate those ofP, then the expected value of the total squared error in these conditional probabilities is bounded by-(1/2) ln C. With this error criterion, and when used as the basis of a universal gambling scheme,P'_{M}is superior to Cover's measurebast. WhenHastequiv -log_{2} P'_{M}is used to define the entropy of a rmite sequence, the equationHast(x,y)= Hast(x)+H^{ast}_{x}(y)holds exactly, in contrast to Chaitin's entropy definition, which has a nonvanishing error term in this equation.