In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Andrey Nikolaevich Kolmogorov (Андрей Николаевич Колмогоров ( April 25, 1903 - October 20, 1987) was a Soviet Computation is a general term for any type of Information processing. For example, consider the following two strings of length 64
The first string admits a short English language description, namely "32 repetitions of '01'", which consists of 20 characters. In Computer programming and some branches of Mathematics, a string is an ordered Sequence of Symbols. English is a West Germanic language originating in England and is the First language for most people in the United Kingdom, the United States The second one has no obvious simple description other than writing down the string itself, which has 64 characters.
More formally, the complexity of a string is the length of the string's shortest description in some fixed description language. In general usage complexity often tends to be used to characterize something with many parts in intricate arrangement The sensitivity of complexity relative to the choice of description language is discussed below. It can be shown that the Kolmogorov complexity of any string cannot be too much larger than the length of the string itself. Strings whose Kolmogorov complexity is small relative to the string's size are not considered to be complex. The notion of Kolmogorov complexity is surprisingly deep and can be used to state and prove impossibility results akin to Gödel's incompleteness theorem and Turing's halting problem. In Mathematical logic, Gödel's incompleteness theorems, proved by Kurt Gödel in 1931 are two Theorems stating inherent limitations of all but the most In computability theory, the halting problem is a Decision problem which can be stated as follows given a description of a program and a finite input
To define Kolmogorov complexity, we must first specify a description language for strings. Such a description language can be based on a programming language such as Lisp, Pascal, or Java Virtual Machine bytecode. Lisp (or LISP) is a family of Computer Programming languages with a long history and a distinctive fully parenthesized syntax Pascal is an influential imperative and procedural Programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small A Java Virtual Machine ( JVM) is a set of computer software programs and data structures which use a Virtual machine If P is a program which outputs a string x, then P is a description of x. The length of the description is just the length of P as a character string. In determining the length of P, the lengths of any subroutines used in P must be accounted for. The length of any integer constant n which occurs in the program P is the number of bits required to represent n, that is (roughly) log2n.
We could alternatively choose an encoding for Turing machines, where an encoding is a function which associates to each Turing Machine M a bitstring <M>. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm If M is a Turing Machine which on input w outputs string x, then the concatenated string <M> w is a description of x. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature. In this article we will use an informal approach.
Any string s has at least one description, namely the program
function GenerateFixedString() return s
If a description of s, d(s), is of minimal length--i. e. it uses the fewest number of characters--it is called a minimal description of s. Then the length of d(s)--i. e. the number of characters in the description--is the Kolmogorov complexity of s, written K(s). Symbolically,
We now consider how the choice of description language affects the value of K and show that the effect of changing the description language is bounded.
Theorem. If K1 and K2 are the complexity functions relative to description languages L1 and L2, then there is a constant c (which depends only on the languages L1 and L2) such that
Proof. By symmetry, it suffices to prove that there is some constant c such that for all bitstrings s,
To see why this is so, there is a program in the language L1 which acts as an interpreter for L2:
function InterpretLanguage(string p)
where p is a program in L2. In Computer science, an interpreter normally means a Computer program that executes, i The interpreter is characterized by the following property:
Thus if P is a program in L2 which is a minimal description of s, then InterpretLanguage(P) returns the string s. The length of this description of s is the sum of
This proves the desired upper bound.
See also invariance theorem. In Algorithmic information theory, the invariance theorem, originally proved by Ray Solomonoff, states that a Universal Turing machine provides an optimal
Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or other data structures). Algorithmic information theory is a subfield of Information theory and Computer science that concerns itself with the relationship between computation A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently The field was developed by Andrey Kolmogorov, Ray Solomonoff and Gregory Chaitin starting in the late 1960s. Andrey Nikolaevich Kolmogorov (Андрей Николаевич Колмогоров ( April 25, 1903 - October 20, 1987) was a Soviet Ray Solomonoff (born 1926 Cleveland Ohio son of Russianimmigrants invented Algorithmic Probability in 1960 Gregory John Chaitin (born 1947 is an Argentine - American Mathematician and Computer scientist There are several variants of Kolmogorov complexity or algorithmic information. The most widely used one is based on self-delimiting programs and is mainly due to Leonid Levin (1974). Leonid Anatolievich Levin (לאוניד אנטולייביץ לוין Леонид Анатольевич Левин born November
Naming this concept "Kolmogorov complexity" is an example of the Matthew effect. The " Matthew effect " denotes the phenomenon that "the rich get richer and the poor get poorer" and can be observed in various different contexts where "rich"
In the following, we will fix one definition and simply write K(s) for the complexity of the string s.
It is not hard to see that the minimal description of a string cannot be too much larger than the string itself: the program GenerateFixedString above that outputs s is a fixed amount larger than s.
Theorem. There is a constant c such that
The first result is that there is no way to effectively compute K.
Theorem. K is not a computable function. Computable functions are the basic objects of study in computability theory.
In other words, there is no program which takes a string s as input and produces the integer K(s) as output. We show this by contradiction by making a program that creates a string that should only be able to be created by a longer program. Suppose there is a program
function KolmogorovComplexity(string s)
that takes as input a string s and returns K(s). Now consider the program
function GenerateComplexString(int n) for i = 1 to infinity: for each string s of length exactly i if KolmogorovComplexity(s) >= n return s quit
This program calls KolmogorovComplexity as a subroutine. This program tries every string, starting with the shortest, until it finds a string with complexity at least n, then returns that string. Therefore, given any positive integer n, it produces a string with Kolmogorov complexity at least as great as n. The program itself has a fixed length U. The input to the program GenerateComplexString is an integer n; here, the size of n is measured by the number of bits required to represent n which is log2(n). Now consider the following program:
function GenerateParadoxicalString() return GenerateComplexString(n0)
This program calls GenerateComplexString as a subroutine and also has a free parameter n0. This program outputs a string s whose complexity is at least n0. By an auspicious choice of the parameter n0 we will arrive at a contradiction. To choose this value, note s is described by the program GenerateParadoxicalString whose length is at most
where C is the "overhead" added by the program GenerateParadoxicalString. Since n grows faster than log2(n), there exists a value n0 such that
But this contradicts the definition of having a complexity at least n0. That is, by the definition of K(s), the string s returned by GenerateParadoxicalString is only supposed to be able to be generated by a program of length n0 or longer, but GenerateParadoxicalString is shorter than n0. Thus the program named "KolmogorovComplexity" cannot actually computably find the complexity of arbitrary strings.
This is proof by contradiction where the contradiction is similar to the Berry paradox: "Let n be the smallest positive integer that cannot be defined in fewer than twenty English words. The Berry paradox is a Self-referential Paradox arising from the expression "the smallest possible Integer not definable by a given number of " It is also possible to show the uncomputability of K by reduction from the uncomputability of the halting problem H, since K and H are turing-equivalent. In computability theory, the halting problem is a Decision problem which can be stated as follows given a description of a program and a finite input 
The chain rule for Kolmogorov complexity states that
It states that the shortest program that reproduces X and Y is no more than a logarithmic term larger than a program to reproduce X and a program to reproduce Y given X. The chain rule for Kolmogorov complexity is an analogue of the chain rule for Information entropy, which states H(XY = H(X + H(Y|X In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments Using this statement one can define an analogue of mutual information for Kolmogorov complexity. In Probability theory and Information theory, the mutual information (sometimes known by the archaic term transinformation) of two Random
It is however straightforward to compute upper bounds for K(s): simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the resulting string's length.
A string s is compressible by a number c if it has a description whose length does not exceed |s| − c. This is equivalent to saying K(s) ≤ |s| − c. Otherwise s is incompressible by c. A string incompressible by 1 is said to be simply incompressible; by the pigeonhole principle, incompressible strings must exist, since there are 2n bit strings of length n but only 2n−2 shorter strings, that is strings of length n − 1 or less. The pigeonhole principle, also known as Dirichlet's box (or drawer) principle, states that given two Natural numbers n and
For the same reason, "most" strings are complex in the sense that they cannot be significantly compressed: K(s) is not much smaller than |s|, the length of s in bits. To make this precise, fix a value of n. There are 2n bitstrings of length n. The uniform probability distribution on the space of these bitstrings assigns to each string of length exactly n equal weight 2−n. WikipediaWikiProject Probability#Standards for a discussion of standards used for probability distribution articles such as this one ---> In Probability Probability is the likelihood or chance that something is the case or will happen
Theorem. With the uniform probability distribution on the space of bitstrings of length n, the probability that a string is incompressible by c is at least 1 − 2−c+1 + 2−n.
To prove the theorem, note that the number of descriptions of length not exceeding n − c is given by the geometric series:
There remain at least
many bitstrings of length n that are incompressible by c. In Mathematics, a geometric series is a series with a constant ratio between successive terms. To determine the probability divide by 2n.
This theorem is the justification for various challenges in comp.compression FAQ. Despite this result, it is sometimes claimed by certain individuals (considered cranks) that they have produced algorithms which uniformly compress data without loss. "Crank" is a Pejorative term for a person who either holds some belief which the vast majority of his contemporaries would consider false is eccentric (especially See lossless data compression. Lossless data compression is a class of Data compression Algorithms that allows the exact original data to be reconstructed from the compressed data
We know that most strings are complex in the sense that they cannot be described in any significantly "compressed" way. However, it turns out that the fact that a specific string is complex cannot be formally proved, if the string's length is above a certain threshold. The precise formalization is as follows. First fix a particular axiomatic system S for the natural numbers. In Mathematics, an axiomatic system is any set of Axioms from which some or all axioms can be used in conjunction to logically derive Theorems In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an The axiomatic system has to be powerful enough so that to certain assertions A about complexity of strings one can associate a formula FA in S. This association must have the following property: if FA is provable from the axioms of S, then the corresponding assertion A is true. This "formalization" can be achieved either by an artificial encoding such as a Gödel numbering or by a formalization which more clearly respects the intended interpretation of S. In Mathematical logic, a Gödel numbering is a function that assigns to each symbol and Well-formed formula of some Formal language a unique
Theorem. There exists a constant L (which only depends on the particular axiomatic system and the choice of description language) such that there does not exist a string s for which the statement
(as formalized in S) can be proven within the axiomatic system S.
Note that by the abundance of nearly incompressible strings, the vast majority of those statements must be true.
The proof of this result is modeled on a self-referential construction used in Berry's paradox. The Berry paradox is a Self-referential Paradox arising from the expression "the smallest possible Integer not definable by a given number of The proof is by contradiction. If the theorem were false, then
We can find an effective enumeration of all the formal proofs in S by some procedure
function NthProof(int n)
which takes as input n and outputs some proof. This function enumerates all proofs. Some of these are proofs for formulas we do not care about here (examples of proofs which will be listed by the procedure NthProof are the various known proofs of the law of quadratic reciprocity, those of Fermat's little theorem or the proof of Fermat's last theorem all translated into the formal language of S). The law of quadratic reciprocity is a theorem from Modular arithmetic, a branch of Number theory, which shows a remarkable relationship between the solvability Fermat's little theorem (not to be confused with Fermat's last theorem) states that if p is a Prime number, then for any Integer a Fermat's Last Theorem is the name of the statement in Number theory that It is impossible to separate any power higher than the second into two like Some of these are complexity formulas of the form K(s) ≥ n where s and n constants in the language of S. There is a program
function NthProofProvesComplexityFormula(int n)
which determines whether the nth proof actually proves a complexity formula K(s) ≥ L. The strings s and the integer L in turn are computable by programs:
function StringNthProof(int n)
function ComplexityLowerBoundNthProof(int n)
Consider the following program
function GenerateProvablyComplexString(int n) for i = 1 to infinity: if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) >= n return StringNthProof(i) quit
Given an n, this program tries every proof until it finds a string and a proof in the formal system S of the formula K(s) ≥ n. In formal logic, a formal system (also called a logical system, a logistic system, or simply a logic Formal systems in mathematics consist The program terminates by our Assumption (X). Now this program has a length U. There is an integer n0 such that U + log2(n0) + C < n0, where C is the overhead cost of
function GenerateProvablyParadoxicalString() return GenerateProvablyComplexString(n0) quit
The program GenerateProvablyParadoxicalString outputs a string s for which K(s) ≥ n0 can be formally proved in S. In particular K(s) ≥ n0 is true. However, s is also described by a program of length U+log2(n0)+C so its complexity is less than n0. This contradiction proves Assumption (X) cannot hold.
Similar ideas are used to prove the properties of Chaitin's constant. In the Computer science subfield of Algorithmic information theory a Chaitin Constant or halting probability is a Real number that
The minimum message length principle of statistical and inductive inference and machine learning was developed by C.S. Wallace and D. Minimum message length (MML is a formal Information theory restatement of Occam's Razor: even when models are not equal in goodness of fit accuracy to the observed Professor Christopher Stewart Wallace ( 26 October, 1933 — 7 August, 2004) was an Australian Computer scientist (and M. Boulton in 1968. MML is Bayesian (it incorporates prior beliefs) and information-theoretic. Bayesian probability interprets the concept of Probability as 'a measure of a state of knowledge'. It has the desirable properties of statistical invariance (the inference transforms with a re-parametrisation, such as from polar coordinates to Cartesian coordinates), statistical consistency (even for very hard problems, MML will converge to any underlying model) and efficiency (the MML model will converge to any true underlying model about as quickly as is possible). C.S. Wallace and D. L. Dowe showed a formal connection between MML and algorithmic information theory (or Kolmogorov complexity) in 1999.
Kolmogorov randomness (also called algorithmic randomness) defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string. In Computer programming and some branches of Mathematics, a string is an ordered Sequence of Symbols. A bit is a binary digit, taking a value of either 0 or 1 Binary digits are a basic unit of Information storage and communication Randomness is a lack of order Purpose, cause, or predictability Computer programs (also software programs, or just programs) are instructions for a Computer. This definition of randomness is critically dependent on the definition of Kolmogorov complexity. To make this definition complete, a computer has to be specified, usually a Turing machine. Turing machines are basic abstract symbol-manipulating devices which despite their simplicity can be adapted to simulate the logic of any Computer Algorithm According to the above definition of randomness, a random string is also an "incompressible" string, in the sense that it is impossible to give a representation of the string using a program whose length is shorter than the length of the string itself. However, according to this definition, most strings shorter than a certain length end up to be (Chaitin-Kolmogorovically) random because the best one can do with very small strings is to write a program that simply prints these strings.