This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations.(July 2014) (Learn how and when to remove this message)
The chain rule[citation needed] for Kolmogorov complexity is an analogue of the chain rule for information entropy, which states:
That is, the combined randomness of two sequences X and Y is the sum of the randomness of X plus whatever randomness is left in Y once we know X.
This follows immediately from the definitions of conditional and joint entropy, and the fact from probability theory that the joint probability is the product of the marginal and conditional probability:
The equivalent statement for Kolmogorov complexity does not hold exactly; it is true only up to a logarithmic term:
(An exact version, KP(x, y) = KP(x) + KP(y|x*) + O(1),
holds for the prefix complexity KP, where x* is a shortest program for x.)
It states that the shortest program printing X and Y is obtained by concatenating a shortest program printing X with a program printing Y given X, plus at most a logarithmic factor. The results implies that algorithmic mutual information, an analogue of mutual information for Kolmogorov complexity is symmetric: I(x:y) = I(y:x) + O(log K(x,y)) for all x,y.
and 22 Related for: Chain rule for Kolmogorov complexity information
information theory (a subfield of computer science and mathematics), the Kolmogorovcomplexity of an object, such as a piece of text, is the length of a shortest...
In philosophy of logic and logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises...
_{K}(X;Y)\approx \operatorname {I} _{K}(Y;X)} ) one requires the chainruleforKolmogorovcomplexity (Li & Vitányi 1997). Approximations of this quantity via...
interested in Markov chains, eventually resulting in him publishing in 1938 a detailed study on Markov chains. Andrey Kolmogorov developed in a 1931 paper...
humans perceive relevance, cognitive complexity is defined as an extension of the notion of Kolmogorovcomplexity. It amounts to the length of the shortest...
Birkhoff, Andrey Nikolaevich Kolmogorov, Mary Lucy Cartwright and John Edensor Littlewood, and Stephen Smale. Except for Smale, these studies were all...
produce an answer A recursive step — a set of rules that reduces all successive cases toward the base case. For example, the following is a recursive definition...
ISBN 978-0-201-89683-1. (Section 1.2.1: Mathematical Induction, pp. 11–21.) Kolmogorov, Andrey N.; Fomin, Sergei V. (1975). Introductory Real Analysis. Silverman...
the Radon–Nikodym theorem. This was formulated by Kolmogorov in his famous book from 1933. Kolmogorov underlines the importance of conditional probability...
include: probability axioms, Chapman–Kolmogorov equation and Kolmogorov extension theorem in probability; Kolmogorovcomplexity etc. Maxim Kontsevich, author...
Gödel number, a contradiction results. The notion of computational complexityfor the lambda calculus is a bit tricky, because the cost of a β-reduction...
is one of the most intensively studied problems in computational complexity theory. For first-order logic (FOL), satisfiability is undecidable. More specifically...
Tennenbaum). Every Aronszajn tree is special (EATS); We have the following chains of implications: V = L → ◊ → CH, V = L → GCH → CH, CH → MA, and (see section...
necessitation rule and the distribution axiom, allowing for the derivation of necessary truths from given axioms and rules of inference. NP A complexity class...
In particular he pointed out that "The matter is especially doubtful for the rule of substitution and of replacing defined symbols by their definiens"...
string (Kolmogorov randomness), which means that random strings are those that cannot be compressed. Pioneers of this field include Andrey Kolmogorov and...
model in terms of predicting the data. It penalizes the complexity of the model where complexity refers to the number of parameters in the model. It is...
Vitányi, Paul (2019). "Inductive Reasoning". An Introduction to KolmogorovComplexity and Its Applications. Texts in Computer Science. Springer International...
other hand, proposed supplemental rulesfor the standard Venn diagram, in order to account for certain problem cases. For instance, regarding the issue of...
Global Information
