Answers are grounded in this paper and cite their sources.
Based on program-size complexity, a logical basis for information theory and probabilitytheory has been proposed by A. N. Kolmogorov. The aim of this paper is to furtherstrengthen this logical basis and make it more perfect. First, for the general case of com-putable probability distributions. sufficient and necessary conditions are given for an infinitesequence x∈A ∞ to be a Martin-lof (M. L.) infinite random sequence of a computable proba-bility distribution. These sufficient and necessary conditions give a complexity-baseddefinition of an infinite random sequence which is equivalent to P. Martin-lof's statisticaldefinition of the concept of randomness. Consequently, a common complexity-based theoryof finite and infinite random sequences is established. Finally, inequalities between Chaitincomplexity and Shannon information content of a single event are given, and asymptoticallyequivalent relationships between them are also presented.
No takes yet. Share an insight, caveat, or question.
En‐Hua Yang (1991) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: