Whereas the first string is output by the (much shorter) pseudo-code: For example, the second string above is output by the pseudo-code: In this article, an informal approach is discussed.Īny string s has at least one description. For theoretical analysis, this approach is more suited for constructing detailed formal proofs and is generally preferred in the research literature. If M is a Turing Machine which, on input w, outputs string x, then the concatenated string w is a description of x. ![]() We could, alternatively, choose an encoding for Turing machines, where an encoding is a function which associates to each Turing Machine M a bitstring. The length of the description is just the length of P as a character string, multiplied by the number of bits in a character (e.g., 7 for ASCII). If P is a program which outputs a string x, then P is a description of x. Such a description language can be based on any computer programming language, such as Lisp, Pascal, or Java. We must first specify a description language for strings. The Kolmogorov complexity can be defined for any mathematical object, but for simplicity the scope of this article is restricted to strings. Strings like the abab example above, whose Kolmogorov complexity is small relative to the string's size, are not considered to be complex. 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. More formally, the complexity of a string is the length of the shortest possible description of the string in some fixed universal description language (the sensitivity of complexity relative to the choice of description language is discussed below). Hence the operation of writing the first string can be said to have "less complexity" than writing the second. The second one has no obvious simple description (using the same character set) other than writing down the string itself, i.e., "write 4c1j5b2p0cv4w1x8rx2圓9umgw5q85s7" which has 38 characters. The first string has a short English-language description, namely "write ab 16 times", which consists of 17 characters. ![]() In particular, no program P computing a lower bound for each text's Kolmogorov complexity can return a value essentially larger than P's own length (see section § Chaitin's incompleteness theorem) hence no single program can compute the exact Kolmogorov complexity for infinitely many texts.Ĭonsider the following two strings of 32 lowercase letters and digits:Ībababababababababababababababab, and 4c1j5b2p0cv4w1x8rx2圓9umgw5q85s7 The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem. ![]() It is named after Andrey Kolmogorov, who first published on the subject in 1963 and is a generalization of classical information theory. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. PNG's general-purpose image compression only reduces it to 1.6 MB, smaller than the raw data but much larger than the Kolmogorov complexity. Thus, the Kolmogorov complexity of this image is much less than 23 MB in any pragmatic model of computation. Simply storing the 24-bit color of each pixel in this image would require 23 million bytes, but a small computer program can reproduce these 23 MB using the definition of the Mandelbrot set and the corner coordinates of the image. ![]() Measure of algorithmic complexity This image illustrates part of the Mandelbrot set fractal.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |