Inalgorithmic information theory (a subfield ofcomputer science andmathematics), theKolmogorov complexity of an object, such as a piece of text, is the length of a shortestcomputer program (in a predeterminedprogramming language) that produces the object as output. It is a measure of thecomputational resources needed to specify the object, and is also known asalgorithmic complexity,Solomonoff–Kolmogorov–Chaitin complexity,program-size complexity,descriptive complexity, oralgorithmic entropy. It is named afterAndrey Kolmogorov, who first published on the subject in 1963^[1][2] and is a generalization of classical information theory.

The notion of Kolmogorov complexity can be used to state andprove impossibility results akin toCantor's diagonal argument,Gödel's incompleteness theorem, andTuring's halting problem.In particular, no programP computing alower bound for each text's Kolmogorov complexity can return a value essentially larger thanP's own length (see section§ Chaitin's incompleteness theorem); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts.

Consider the following twostrings of 32 lowercase letters and digits:

abababababababababababababababab, and

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

The first string has a short English-language description, namely "write ab 16 times", which consists of17 characters. The second one has no obvious simple description (using the same character set) other than writing down the string itself, i.e., "write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7" which has38 characters. Hence the operation of writing the first string can be said to have "less complexity" than writing the second.

More formally, thecomplexity of a string is the length of the shortest possible description of the string in some fixeduniversal description language (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 more than a few bytes larger than the length of the string itself. Strings like theabab example above, whose Kolmogorov complexity is small relative to the string's size, are not considered to be complex.

The Kolmogorov complexity can be defined for any mathematical object, but for simplicity the scope of this article is restricted to strings. We must first specify a description language for strings. Such a description language can be based on any computer programming language, such asLisp,Pascal, orJava. IfP is a program which outputs a stringx, thenP is a description ofx. The length of the description is just the length ofP as a character string, multiplied by the number of bits in a character (e.g., 7 forASCII).

We could, alternatively, choose an encoding forTuring machines, where anencoding is a function which associates to each Turing MachineM a bitstring <M>. IfM is a Turing Machine which, on inputw, outputs stringx, then the concatenated string <M>w is a description ofx. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature. In this article, an informal approach is discussed.

Any strings has at least one description. For example, the second string above is output by thepseudo-code:

function GenerateString2()return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

whereas the first string is output by the (much shorter) pseudo-code:

function GenerateString1()return "ab" × 16

If a descriptiond(s) of a strings is of minimal length (i.e., using the fewest bits), it is called aminimal description ofs, and the length ofd(s) (i.e. the number of bits in the minimal description) is theKolmogorov complexity ofs, writtenK(s). Symbolically,

K(s) = |d(s)|.

The length of the shortest description will depend on the choice of description language; but the effect of changing languages is bounded (a result called theinvariance theorem, seebelow).

There are two definitions of Kolmogorov complexity:plain andprefix-free. The plain complexity is the minimal description length of any program, and denoted${\displaystyle C(x)}$ while the prefix-free complexity is the minimal description length of any program encoded in aprefix-free code, and denoted${\displaystyle K(x)}$. The plain complexity is more intuitive, but the prefix-free complexity is easier to study.

By default, all equations hold only up to an additive constant. For example,${\displaystyle f(x)=g(x)}$ really means that${\displaystyle f(x)=g(x)+O(1)}$, that is,${\displaystyle \mathrm{\exists }c,\mathrm{\forall }x,|f(x)-g(x)|\le c}$.

Let${\displaystyle U:2^{\ast }\to 2^{\ast }}$ be a computable function mapping finite binary strings to binary strings. It is a universal function if, and only if, for any computable${\displaystyle f:2^{\ast }\to 2^{\ast }}$, we can encode the function in a "program"${\displaystyle s_f}$, such that${\displaystyle \mathrm{\forall }x\in 2^{\ast },U(s_{f}x)=f(x)}$. We can think of${\displaystyle U}$ as a program interpreter, which takes in an initial segment describing the program, followed by data that the program should process.

One problem with plain complexity is that, because intuitively speaking, there is no general way to tell where to divide an output string just by looking at the concatenated string. We can divide it by specifying the length of${\displaystyle x}$ or${\displaystyle y}$, but that would take${\displaystyle O(min(\ln x,\ln y))}$ extra symbols. Indeed, for any${\displaystyle c>0}$ there exists${\displaystyle x,y}$ such that${\displaystyle C(xy)\ge C(x)+C(y)+c}$.^[3]

Typically, inequalities with plain complexity have a term like${\displaystyle O(min(\ln x,\ln y))}$ on one side, whereas the same inequalities with prefix-free complexity have only${\displaystyle O(1)}$.

The main problem with plain complexity is that there is something extra sneaked into a program. A program not only represents for something with its code, but also represents its own length. In particular, a program${\displaystyle x}$ may represent a binary number up to${\displaystyle {\log }_2|x|}$, simply by its own length. Stated in another way, it is as if we are using a termination symbol to denote where a word ends, and so we are not using 2 symbols, but 3. To fix this defect, we introduce the prefix-free Kolmogorov complexity.^[4]

A prefix-free code is a subset of${\displaystyle 2^{\ast }}$ such that given any two different words${\displaystyle x,y}$ in the set, neither is a prefix of the other. The benefit of a prefix-free code is that we can build a machine that reads words from the code forward in one direction, and as soon as it reads the last symbol of the word, itknows that the word is finished, and does not need to backtrack or a termination symbol.

Define aprefix-free Turing machine to be a Turing machine that comes with a prefix-free code, such that the Turing machine can read any string from the code in one direction, and stop reading as soon as it reads the last symbol. Afterwards, it may compute on a work tape and write to a write tape, but it cannot move its read-head anymore.

This gives us the following formal way to describeK.^[5]

• Fix a prefix-free universal Turing machine, with three tapes: a read tape infinite in one direction, a work tape infinite in two directions, and a write tape infinite in one direction.
• The machine can read from the read tape in one direction only (no backtracking), and write to the write tape in one direction only. It can read and write the work tape in both directions.
• The work tape and write tape start with all zeros. The read tape starts with an input prefix code, followed by all zeros.
• Let${\displaystyle S}$ be the prefix-free code on${\displaystyle 2^{\ast }}$, used by the universal Turing machine.

Note that some universal Turing machines may not be programmable with prefix codes. We must pick only a prefix-free universal Turing machine.

The prefix-free complexity of a string${\displaystyle x}$ is the shortest prefix code that makes the machine output${\displaystyle x}$:$${\displaystyle K(x):=min\{|c|:c\in S,U(c)=x\}}$$

There are some description languages which are optimal, in the following sense: given any description of an object in a description language, said description may be used in the optimal description language with a constant overhead. The constant depends only on the languages involved, not on the description of the object, nor the object being described.

Here is an example of an optimal description language. A description will have two parts:

• The first part describes another description language.
• The second part is a description of the object in that language.

In more technical terms, the first part of a description is a computer program (specifically: a compiler for the object's language, written in the description language), with the second part being the input to that computer program which produces the object as output.

The invariance theorem follows: Given any description languageL, the optimal description language is at least as efficient asL, with some constant overhead.

Proof: Any descriptionD inL can be converted into a description in the optimal language by first describingL as a computer programP (part 1), and then using the original descriptionD as input to that program (part 2). Thetotal length of this new descriptionD′ is (approximately):

|D′ | = |P| + |D|

The length ofP is a constant that doesn't depend onD. So, there is at most a constant overhead, regardless of the object described. Therefore, the optimal language is universalup to this additive constant.

Theorem: IfK₁ andK₂ are the complexity functions relative toTuring complete description languagesL₁ andL₂, then there is a constantc – which depends only on the languagesL₁ andL₂ chosen – such that

∀s. −c ≤K₁(s) −K₂(s) ≤c.

Proof: By symmetry, it suffices to prove that there is some constantc such that for all stringss

K₁(s) ≤K₂(s) +c.

Now, suppose there is a program in the languageL₁ which acts as aninterpreter forL₂:

function InterpretLanguage(stringp)

wherep is a program inL₂. The interpreter is characterized by the following property:

RunningInterpretLanguage on inputp returns the result of runningp.

Thus, ifP is a program inL₂ which is a minimal description ofs, thenInterpretLanguage(P) returns the strings. The length of this description ofs is the sum of

1. The length of the programInterpretLanguage, which we can take to be the constantc.
2. The length ofP which by definition isK₂(s).

This proves the desired upper bound.

Algorithmic information theory is the area of computer science that studies Kolmogorov complexity and other complexity measures on strings (or otherdata structures).

The concept and theory of Kolmogorov Complexity is based on a crucial theorem first discovered byRay Solomonoff, who published it in 1960, describing it in "A Preliminary Report on a General Theory of Inductive Inference"^[6] as part of his invention ofalgorithmic probability. He gave a more complete description in his 1964 publications, "A Formal Theory of Inductive Inference," Part 1 and Part 2 inInformation and Control.^[7][8]

Andrey Kolmogorov laterindependently published this theorem inProblems Inform. Transmission in 1965.^[9]Gregory Chaitin also presents this theorem in theJournal of the ACM – Chaitin's paper was submitted October 1966 and revised in December 1968, and cites both Solomonoff's and Kolmogorov's papers.^[10]

The theorem says that, among algorithms that decode strings from their descriptions (codes), there exists an optimal one. This algorithm, for all strings, allows codes as short as allowed by any other algorithm up to an additive constant that depends on the algorithms, but not on the strings themselves. Solomonoff used this algorithm and the code lengths it allows to define a "universal probability" of a string on which inductive inference of the subsequent digits of the string can be based. Kolmogorov used this theorem to define several functions of strings, including complexity, randomness, and information.

When Kolmogorov became aware of Solomonoff's work, he acknowledged Solomonoff's priority.^[11] For several years, Solomonoff's work was better known in the Soviet Union than in the West. The general consensus in the scientific community, however, was to associate this type of complexity with Kolmogorov, who was concerned with randomness of a sequence, while Algorithmic Probability became associated with Solomonoff, who focused on prediction using his invention of the universal prior probability distribution. The broader area encompassing descriptional complexity and probability is often called Kolmogorov complexity. The computer scientistMing Li considers this an example of theMatthew effect: "...to everyone who has, more will be given..."^[12]

There are several other variants of Kolmogorov complexity or algorithmic information. The most widely used one is based onself-delimiting programs, and is mainly due toLeonid Levin (1974).

An axiomatic approach to Kolmogorov complexity based onBlum axioms (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov.^[13]

We write${\displaystyle K(x,y)}$ to be${\displaystyle K((x,y))}$, where${\displaystyle (x,y)}$ means some fixed way to code for a tuple of strings x and y.

We omit additive factors of${\displaystyle O(1)}$. This section is based on.^[5]

Theorem.${\displaystyle K(x)\le C(x)+2{\log }_{2}C(x)}$

Proof. Take any program for the universal Turing machine used to define plain complexity, and convert it to a prefix-free program by first coding the length of the program in binary, then convert the length to prefix-free coding. For example, suppose the program has length 9, then we can convert it as follows:$${\displaystyle 9\mapsto 1001\mapsto 11-00-00-11-01}$$where we double each digit, then add a termination code. The prefix-free universal Turing machine can then read in any program for the other machine as follows:$${\displaystyle [\text{code for simulating the other machine}][\text{coded length of the program}][\text{the program}]}$$The first part programs the machine to simulate the other machine, and is a constant overhead${\displaystyle O(1)}$. The second part has length${\displaystyle \le 2{\log }_{2}C(x)+3}$. The third part has length${\displaystyle C(x)}$.

Theorem: There exists${\displaystyle c}$ such that${\displaystyle \mathrm{\forall }x,C(x)\le |x|+c}$. More succinctly,${\displaystyle C(x)\le |x|}$. Similarly,${\displaystyle K(x)\le |x|+2{\log }_2|x|}$, and${\displaystyle K(x||x|)\le |x|}$.^{[clarification needed]}

Proof. For the plain complexity, just write a program that simply copies the input to the output. For the prefix-free complexity, we need to first describe the length of the string, before writing out the string itself.

Theorem. (extra information bounds, subadditivity)

• ${\displaystyle K(x|y)\le K(x)\le K(x,y)\le max(K(x|y)+K(y),K(y|x)+K(x))\le K(x)+K(y)}$
• ${\displaystyle K(xy)\le K(x,y)}$

Note that there is no way to compare${\displaystyle K(xy)}$ and${\displaystyle K(x|y)}$ or${\displaystyle K(x)}$ or${\displaystyle K(y|x)}$ or${\displaystyle K(y)}$. There are strings such that the whole string${\displaystyle xy}$ is easy to describe, but its substrings are very hard to describe.

Theorem. (symmetry of information)${\displaystyle K(x,y)=K(x|y,K(y))+K(y)=K(y,x)}$.

Proof. One side is simple. For the other side with${\displaystyle K(x,y)\ge K(x|y,K(y))+K(y)}$, we need to use a counting argument (page 38^[14]).

Theorem. (information non-increase) For any computable function${\displaystyle f}$, we have${\displaystyle K(f(x))\le K(x)+K(f)}$.

Proof. Program the Turing machine to read two subsequent programs, one describing the function and one describing the string. Then run both programs on the work tape to produce${\displaystyle f(x)}$, and write it out.

At first glance it might seem trivial to write a program which can computeK(s) for anys, such as the following:

function KolmogorovComplexity(string s)for i = 1to infinity:for each string pof length exactly iif isValidProgram(p)and evaluate(p) == sreturn i

This program iterates through all possible programs (by iterating through all possible strings and only considering those which are valid programs), starting with the shortest. Each program is executed to find the result produced by that program, comparing it to the inputs. If the result matches then the length of the program is returned.

However this will not work because some of the programsp tested will not terminate, e.g. if they contain infinite loops. There is no way to avoid all of these programs by testing them in some way before executing them due to the non-computability of thehalting problem.

What is more, no program at all can compute the functionK, be it ever so sophisticated. This is proven in the following.

Theorem: There exist strings of arbitrarily large Kolmogorov complexity. Formally: for each natural numbern, there is a strings withK(s) ≥n.^{[note 1]}

Proof: Otherwise all of the infinitely many possible finite strings could be generated by the finitely many^{[note 2]} programs with a complexity belown bits.

Theorem:K is not acomputable function. In other words, there is no program which takes any strings as input and produces the integerK(s) as output.

The followingproof by contradiction uses a simplePascal-like language to denote programs; for sake of proof simplicity assume its description (i.e. aninterpreter) to have a length of1400000 bits.Assume for contradiction there is a program

function KolmogorovComplexity(string s)

which takes as input a strings and returnsK(s). All programs are of finite length so, for sake of proof simplicity, assume it to be7000000000 bits.Now, consider the following program of length1288 bits:

function GenerateComplexString()for i = 1to infinity:for each string sof length exactly iif KolmogorovComplexity(s) ≥ 8000000000return s

UsingKolmogorovComplexity as a subroutine, the program tries every string, starting with the shortest, until it returns a string with Kolmogorov complexity at least8000000000 bits,^{[note 3]} i.e. a string that cannot be produced by any program shorter than8000000000 bits. However, the overall length of the above program that produceds is only7001401288 bits,^{[note 4]} which is a contradiction. (If the code ofKolmogorovComplexity is shorter, the contradiction remains. If it is longer, the constant used inGenerateComplexString can always be changed appropriately.)^{[note 5]}

The above proof uses a contradiction similar to that of theBerry paradox: "₁The₂smallest₃positive₄integer₅that₆cannot₇be₈defined₉in₁₀fewer₁₁than₁₂twenty₁₃English₁₄words". It is also possible to show the non-computability ofK by reduction from the non-computability of the halting problemH, sinceK andH areTuring-equivalent.^[15]

There is a corollary, humorously called the "full employment theorem" in the programming language community, stating that there is no perfect size-optimizing compiler.

The chain rule^[16] for Kolmogorov complexity states that there exists a constantc such that for allX andY:

K(X,Y) =K(X) +K(Y|X) + c*max(1,log(K(X,Y))).

It states that the shortest program that reproducesX andY isno more than a logarithmic term larger than a program to reproduceX and a program to reproduceY givenX. Using this statement, one can definean analogue of mutual information for Kolmogorov complexity.

It is straightforward to compute upper bounds forK(s) – simplycompress the strings with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string – concretely, the size of aself-extracting archive in the given language.

A strings is compressible by a numberc if it has a description whose length does not exceed |s| −c bits. This is equivalent to saying thatK(s) ≤ |s| −c. Otherwise,s is incompressible byc. A string incompressible by 1 is said to be simplyincompressible – by thepigeonhole principle, which applies because every compressed string maps to only one uncompressed string,incompressible strings must exist, since there are 2ⁿ bit strings of lengthn, but only 2ⁿ − 1 shorter strings, that is, strings of length less thann, (i.e. with length 0, 1, ...,n − 1).^{[note 6]}

For the same reason, most strings are complex in the sense that they cannot be significantly compressed – theirK(s) is not much smaller than |s|, the length ofs in bits. To make this precise, fix a value ofn. There are 2ⁿ bitstrings of lengthn. Theuniformprobability distribution on the space of these bitstrings assigns exactly equal weight 2⁻ⁿ to each string of lengthn.

Theorem: With the uniform probability distribution on the space of bitstrings of lengthn, the probability that a string is incompressible byc is at least1 − 2^−c+1 + 2⁻ⁿ.

To prove the theorem, note that the number of descriptions of length not exceedingn −c is given by the geometric series:

1 + 2 + 2² + ... + 2^{n −c} = 2^n−c+1 − 1.

There remain at least

2ⁿ − 2^n−c+1 + 1

bitstrings of lengthn that are incompressible byc. To determine the probability, divide by 2ⁿ.

By the above theorem (§ Compression), 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 proven, if the complexity of the string is above a certain threshold. The precise formalization is as follows. First, fix a particularaxiomatic systemS for thenatural numbers. The axiomatic system has to be powerful enough so that, to certain assertionsA about complexity of strings, one can associate a formulaF_A inS. This association must have the following property:

IfF_A is provable from the axioms ofS, then the corresponding assertionA must be true. This "formalization" can be achieved based on aGödel numbering.

Theorem: There exists a constantL (which only depends onS and on the choice of description language) such that there does not exist a strings for which the statement

K(s) ≥L       (as formalized inS)

can be proven withinS.^[17][18]

Proof Idea: The proof of this result is modeled on a self-referential construction used inBerry's paradox. We firstly obtain a program which enumerates the proofs withinS and we specify a procedureP which takes as an input an integerL and prints the stringsx which are within proofs withinS of the statementK(x) ≥L. By then settingL to greater than the length of this procedureP, we have that the required length of a program to printx as stated inK(x) ≥L as being at leastL is then less than the amountL since the stringx was printed by the procedureP. This is a contradiction. So it is not possible for the proof systemS to proveK(x) ≥L forL arbitrarily large, in particular, forL larger than the length of the procedureP, (which is finite).

Proof:

We can find an effective enumeration of all the formal proofs inS by some procedure

function NthProof(intn)

which takes as inputn and outputs some proof. This function enumerates all proofs. Some of these are proofs for formulas we do not care about here, since every possible proof in the language ofS is produced for somen. Some of these are complexity formulas of the formK(s) ≥ n wheres andn are constants in the language ofS. There is a procedure

function NthProofProvesComplexityFormula(intn)

which determines whether thenth proof actually proves a complexity formulaK(s) ≥ L. The stringss, and the integerL in turn, are computable by procedure:

function StringNthProof(intn)

function ComplexityLowerBoundNthProof(intn)

Consider the following procedure:

function GenerateProvablyComplexString(intn)for i = 1 to infinity:if NthProofProvesComplexityFormula(i)and ComplexityLowerBoundNthProof(i) ≥nreturn StringNthProof(i)

Given ann, this procedure tries every proof until it finds a string and a proof in the formal systemS of the formulaK(s) ≥ L for someL ≥ n; if no such proof exists, it loops forever.

Finally, consider the program consisting of all these procedure definitions, and a main call:

GenerateProvablyComplexString(n0)

where the constantn₀ will be determined later on. The overall program length can be expressed asU+log₂(n₀), whereU is some constant and log₂(n₀) represents the length of the integer valuen₀, under the reasonable assumption that it is encoded in binary digits. We will choosen₀ to be greater than the program length, that is, such thatn₀ >U+log₂(n₀). This is clearly true forn₀ sufficiently large, because the left hand side grows linearly inn₀ whilst the right hand side grows logarithmically inn₀ up to the fixed constantU.

Then no proof of the form "K(s)≥L" withL≥n₀ can be obtained inS, as can be seen by anindirect argument:IfComplexityLowerBoundNthProof(i) could return a value ≥n₀, then the loop insideGenerateProvablyComplexString would eventually terminate, and that procedure would return a strings such that

This is a contradiction,Q.E.D.

As a consequence, the above program, with the chosen value ofn₀, must loop forever.

Similar ideas are used to prove the properties ofChaitin's constant.

The minimum message length principle of statistical and inductive inference and machine learning was developed byC.S. Wallace and D.M. Boulton in 1968. MML isBayesian (i.e. it incorporates prior beliefs) and information-theoretic. It has the desirable properties of statistical invariance (i.e. the inference transforms with a re-parametrisation, such as from polar coordinates to Cartesian coordinates), statistical consistency (i.e. even for very hard problems, MML will converge to any underlying model) and efficiency (i.e. the MML model will converge to any true underlying model about as quickly as is possible). C.S. Wallace and D.L. Dowe (1999) showed a formal connection between MML and algorithmic information theory (or Kolmogorov complexity).^[19]

Kolmogorov randomness defines a string (usually ofbits) as beingrandom if and only if everycomputer program that can produce that string is at least as long as the string itself. To make this precise, a universal computer (oruniversal Turing machine) must be specified, so that "program" means a program for this universal machine. A random string in this sense is "incompressible" in that it is impossible to "compress" the string into a program that is shorter than the string itself. For every universal computer, there is at least one algorithmically random string of each length.^[20] Whether a particular string is random, however, depends on the specific universal computer that is chosen. This is because a universal computer can have a particular string hard-coded in itself, and a program running on this universal computer can then simply refer to this hard-coded string using a short sequence of bits (i.e. much shorter than the string itself).

This definition can be extended to define a notion of randomness forinfinite sequences from a finite alphabet. Thesealgorithmically random sequences can be defined in three equivalent ways. One way uses an effective analogue ofmeasure theory; another uses effectivemartingales. The third way defines an infinite sequence to be random if the prefix-free Kolmogorov complexity of its initial segments grows quickly enough — there must be a constantc such that the complexity of an initial segment of lengthn is always at leastn−c. This definition, unlike the definition of randomness for a finite string, is not affected by which universal machine is used to define prefix-free Kolmogorov complexity.^[21]

For dynamical systems, entropy rate and algorithmic complexity of the trajectories are related by a theorem of Brudno, that the equality${\displaystyle K(x;T)=h(T)}$ holds for almost all${\displaystyle x}$.^[22]

It can be shown^[23] that for the output ofMarkov information sources, Kolmogorov complexity is related to theentropy of the information source. More precisely, the Kolmogorov complexity of the output of a Markov information source, normalized by the length of the output, converges almost surely (as the length of the output goes to infinity) to theentropy of the source.

Theorem. (Theorem 14.2.5^[24]) The conditional Kolmogorov complexity of a binary string${\displaystyle x_{1:n}}$ satisfies$${\displaystyle \frac{1}{n}K(x_{1:n}|n)\le H_b\left(\frac{1}{n}\sum _i{x}_i\right)+\frac{\log n}{2n}+O(1/n)}$$where${\displaystyle H_b}$ is thebinary entropy function (not to be confused with the entropy rate).

The Kolmogorov complexity function is equivalent to deciding the halting problem.

If we have a halting oracle, then the Kolmogorov complexity of a string can be computed by simply trying every halting program, in lexicographic order, until one of them outputs the string.

The other direction is much more involved.^[25][26] It shows that given a Kolmogorov complexity function, we can construct a function${\displaystyle p}$, such that${\displaystyle p(n)\ge BB(n)}$ for all large${\displaystyle n}$, where${\displaystyle BB}$ is theBusy Beaver shift function (also denoted as${\displaystyle S(n)}$). By modifying the function at lower values of${\displaystyle n}$ we get an upper bound on${\displaystyle BB}$, which solves the halting problem.

Consider this program$p_K$, which takes input as$n$, and uses$K$.

• List all strings of length$\le 2n+1$.
• For each such string$x$, enumerate all (prefix-free) programs of length${\displaystyle K(x)}$ until one of them does output$x$. Record its runtime$n_x$.
• Output the largest$n_x$.

We prove by contradiction that$p_K(n)\ge BB(n)$ for all large$n$.

Let$p_n$ be a Busy Beaver of length${\displaystyle n}$. Consider this (prefix-free) program, which takes no input:

• Run the program$p_n$, and record its runtime length$BB(n)$.
• Generate all programs with length$\le 2n$. Run every one of them for up to$BB(n)$ steps. Note the outputs of those that have halted.
• Output the string with the lowest lexicographic order that has not been output by any of those.

Let the string output by the program be$x$.

The program has length$\le n+2{\log }_{2}n+O(1)$, where${\displaystyle n}$ comes from the length of the Busy Beaver$p_n$,${\displaystyle 2{\log }_{2}n}$ comes from using the (prefix-free)Elias delta code for the number${\displaystyle n}$, and${\displaystyle O(1)}$ comes from the rest of the program. Therefore,$${\displaystyle K(x)\le n+2{\log }_{2}n+O(1)\le 2n}$$for all big$n$. Further, since there are only so many possible programs with length$\le 2n$, we have$l(x)\le 2n+1$ bypigeonhole principle.By assumption,, so every string of length$\le 2n+1$ has a minimal program with runtime. Thus, the string$x$ has a minimal program with runtime. Further, that program has length$K(x)\le 2n$. This contradicts how$x$ was constructed.

Fix a universal Turing machine${\displaystyle U}$, the same one used to define the (prefix-free) Kolmogorov complexity. Define the (prefix-free) universal probability of a string${\displaystyle x}$ to be$${\displaystyle P(x)=\sum _{U(p)=x}{2}^{-l(p)}}$$In other words, it is the probability that, given a uniformly random binary stream as input, the universal Turing machine would halt after reading a certain prefix of the stream, and output${\displaystyle x}$.

Note.${\displaystyle U(p)=x}$ does not mean that the input stream is${\displaystyle p000\cdots }$, but that the universal Turing machine would halt at some point after reading the initial segment${\displaystyle p}$, without reading any further input, and that, when it halts, its has written${\displaystyle x}$ to the output tape.

Theorem. (Theorem 14.11.1^[24])${\displaystyle \log \frac{1}{P(x)}=K(x)+O(1)}$

Kolmogorov complexity has been used in the context of biology to argue that the symmetries and modular arrangements observed in multiple species emerge from the tendency of evolution to prefer minimal Kolmogorov complexity.^[27] Considering the genome as a program that must solve a task or implement a series of functions, shorter programs would be preferred on the basis that they are easier to find by the mechanisms of evolution.^[28] An example of this approach is the eight-fold symmetry of the compass circuit that is found across insect species, which correspond to the circuit that is both functional and requires the minimum Kolmogorov complexity to be generated from self-replicating units.^[29]

This sectionneeds expansion. You can help byadding to it.(July 2014)

The conditional Kolmogorov complexity of two strings${\displaystyle K(x|y)}$ is, roughly speaking, defined as the Kolmogorov complexity ofx giveny as an auxiliary input to the procedure.^[30][31] So while the (unconditional) Kolmogorov complexity${\displaystyle K(x)}$ of a sequence${\displaystyle x}$ is the length of the shortest binary program that outputs${\displaystyle x}$ on a universal computer and can be thought of as the minimal amount of information necessary to produce${\displaystyle x}$, the conditional Kolmogorov complexity${\displaystyle K(x|y)}$ is defined as the length of the shortest binary program that computes${\displaystyle x}$ when${\displaystyle y}$ is given as input, using a universal computer.^[32]

There is also a length-conditional complexity${\displaystyle K(x|L(x))}$, which is the complexity ofx given the length ofx as known/input.^[33][34]

Time-bounded Kolmogorov complexity is a modified version of Kolmogorov complexity where the space of programs to be searched for a solution is confined to only programs that can run within some pre-defined number of steps.^[35] It is hypothesised that the possibility of the existence of an efficient algorithm for determining approximate time-bounded Kolmogorov complexity is related to the question of whether trueone-way functions exist.^[36][37]

• Berry paradox
• Code golf
• Data compression
• Descriptive complexity theory
• Grammar induction
• Inductive reasoning
• Kolmogorov structure function
• Levenshtein distance
• Manifold hypothesis
• Solomonoff's theory of inductive inference
• Sample entropy
• Rayo's number

• Blum, M. (1967)."On the size of machines".Information and Control.11 (3): 257.doi:10.1016/S0019-9958(67)90546-3.
• Brudno, A. (1983). "Entropy and the complexity of the trajectories of a dynamical system".Transactions of the Moscow Mathematical Society.2:127–151.
• Cover, Thomas M.; Thomas, Joy A. (2006).Elements of information theory (2nd ed.). Wiley-Interscience.ISBN 0-471-24195-4.
• Lajos, Rónyai; Gábor, Ivanyos; Réka, Szabó (1999).Algoritmusok. TypoTeX.ISBN 963-279-014-6.
• Li, Ming; Vitányi, Paul (1997).An Introduction to Kolmogorov Complexity and Its Applications. Springer.ISBN 978-0-387-33998-6.
• Yu, Manin (1977).A Course in Mathematical Logic. Springer-Verlag.ISBN 978-0-7204-2844-5.
• Sipser, Michael (1997).Introduction to the Theory of Computation. PWS.ISBN 0-534-95097-3.
• Downey, Rodney G.; Hirschfeldt, Denis R. (2010)."Algorithmic Randomness and Complexity".Theory and Applications of Computability.doi:10.1007/978-0-387-68441-3.ISBN 978-0-387-95567-4.ISSN 2190-619X.

• The Legacy of Andrei Nikolaevich Kolmogorov
• Chaitin's online publications
• Solomonoff's IDSIA page
• Generalizations of algorithmic information byJ. Schmidhuber
• "Review of Li Vitányi 1997".
• Tromp, John."John's Lambda Calculus and Combinatory Logic Playground". Tromp's lambda calculus computer model offers a concrete definition of K()]
• Universal AI based on Kolmogorov ComplexityISBN 3-540-22139-5 byM. Hutter:ISBN 3-540-22139-5
• David Dowe'sMinimum Message Length (MML) andOccam's razor pages.
• Grunwald, P.; Pitt, M.A. (2005). Myung, I. J. (ed.).Advances in Minimum Description Length: Theory and Applications. MIT Press.ISBN 0-262-07262-9.

• Algorithmic information theory
• Information theory
• Computability theory
• Descriptive complexity
• Measures of complexity
• Computational complexity theory
• Data compression

• Articles with short description
• Short description matches Wikidata
• Wikipedia articles needing clarification from January 2024
• Articles to be expanded from July 2014
• All articles to be expanded