The Coding Theorem of L.A. Levin connects unconditional prefix Kolmogorov complexity with the discrete universal distribution. There are conditional versions referred to in several publications but as yet there exist no written proofs in English. Here we provide those proofs. They use a different definition than the standard one for the conditional version of the discrete universal distribution. Under the classic definition of conditional probability, there is no conditional version of the Coding Theorem.
We can enumerate all lower semicomputable probability mass functions with one argument. For convenience these arguments are elements of @math . The enumeration list is denoted [ P = P_1, P_2, . ] There is another interpretation possible. Let prefix Turing machine @math be the @math th element in the standard enumeration of prefix Turing machines @math Then @math where @math is a program for @math such that @math . This @math is the probability that prefix Turing machine @math outputs @math when the program on its input tape is supplied by flips of a fair coin. We can thus form the list [ R = R_1, R_2, . ] Both lists @math and @math enumerate the same functions and there are computable isomorphisms between the two @cite_4 Lemma 4.3.4.
@cite_4
1638203394
The book is outstanding and admirable in many respects. ... is necessary reading for all kinds of readers from undergraduate students to top authorities in the field. Journal of Symbolic Logic Written by two experts in the field, this is the only comprehensive and unified treatment of the central ideas and their applications of Kolmogorov complexity. The book presents a thorough treatment of the subject with a wide range of illustrative applications. Such applications include the randomness of finite objects or infinite sequences, Martin-Loef tests for randomness, information theory, computational learning theory, the complexity of algorithms, and the thermodynamics of computing. It will be ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. The book is self-contained in that it contains the basic requirements from mathematics and computer science. Included are also numerous problem sets, comments, source references, and hints to solutions of problems. New topics in this edition include Omega numbers, KolmogorovLoveland randomness, universal learning, communication complexity, Kolmogorov's random graphs, time-limited universal distribution, Shannon information and others.