Complexity-based induction systems: Comparisons and convergence theorems

Author

Solomonoff, R.J.

Volume

Issue

fYear

1978

fDate

7/1/1978 12:00:00 AM

Firstpage

422

Lastpage

432

Abstract

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 if $\\tilde{P}\´_{M}(x)$ is an unnormalized form of this measure, and $P(x)$ is any computable probability measure on strings, $x$ , then $\\tilde{P}\´_{M}\\geq CP(x)$ where $C$ is a constant independent of $x$ . 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 of $P\´_{M}$ 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) \\ln C$ . With this error criterion, and when used as the basis of a universal gambling scheme, $P\´_{M}$ is superior to Cover\´s measure $b\\ast$ . When $H\\ast \\equiv -\\log _{2} P\´_{M}$ is used to define the entropy of a rmite sequence, the equation $H\\ast (x,y)= H\\ast (x)+H^{\\ast }_{x}(y)$ holds exactly, in contrast to Chaitin\´s entropy definition, which has a nonvanishing error term in this equation.

Keywords

Automata; Entropy functions; Probability; Contracts; Convergence; Entropy; Equations; Information theory; Military computing; Probability; Public healthcare; Random sequences; Turing machines;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.1978.1055913

Filename

1055913

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=928819