Complexity-based induction systems: Comparisons and convergence theorems

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