 FACTOID # 4: Just 1% of the houses in Nevada were built before 1939.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Algorithmic information theory

Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information. According to Gregory Chaitin, it is "the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously."  A bundle of optical fiber. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a computer. ... The ASCII codes for the word Wikipedia represented in binary, the numeral system most commonly used for encoding computer information. ... Gregory John Chaitin (born 1947) is an Argentine-American mathematician and computer scientist. ...

## Contents

Algorithmic information theory principally studies Kolmogorov complexity and other complexity measures on strings (or other data structures). Because most mathematical objects can be described in terms of strings, or as the limit of a sequence of strings, it can be used to study a wide variety of mathematical objects, including integers and real numbers. 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. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... A binary tree, a simple type of branching linked data structure. ... The limit of a sequence is one of the oldest concepts in mathematical analysis. ... In mathematics, a series is often represented as the sum of a sequence of terms. ... The integers are commonly denoted by the above symbol. ... In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2. ...

The term "information" may be a bit misleading, as it is used in a way which is synonymous with "incompressibility" - a string has high information content, from the point of view of algorithmic information theory, if the information it contains cannot be expressed more compactly. One reason this may be misleading is that, from this point of view, a 3000 page encyclopedia actually contains less information than 3000 pages of completely random letters, despite the fact that the encyclopedia is much more useful. This is because to reconstruct the entire sequence of random letters, one must know, more or less, what every single letter is. On the other hand, if every vowel were removed from the encyclopedia, someone with reasonable knowledge of the English language could reconstruct it, just as one could likely reconstruct the sentence "Ths sntnc hs lw nfrmtn cntnt" from the context and consonants present. For this reason, high-information strings and sequences are sometimes called "random"; people also sometimes attempt to distinguish between "information" and "useful information" and attempt to provide rigorous definitions for the latter, with the idea that the random letters may have more information than the encyclopedia, but the encyclopedia has more "useful" information.

Unlike classical information theory, algorithmic information theory gives formal, rigorous definitions of a random string and a random infinite sequence that do not depend on physical or philosophical intuitions about nondeterminism or likelihood. 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. ... Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm. ... Look up Intuition in Wiktionary, the free dictionary. ... This article is about the general notion of determinism in philosophy. ... In statistics, a likelihood function is a conditional probability function considered a function of its second argument with its first argument held fixed, thus: and also any other function proportional to such a function. ...

Some of the results of algorithmic information theory, such as Chaitin's incompleteness theorem, appear to challenge common mathematical and philosophical intuitions. Most notable among these is the construction of Chaitin's constant Ω, a real number which expresses the probability that a random computer program will eventually halt. Ω has numerous remarkable mathematical properties, including the fact that it is definable but not computable. Thus, although Ω is easily defined, in any theory you can only compute finitely many digits of Ω, so it is in some sense unknowable, providing an absolute limit on knowledge that is reminiscent of Gödel's Incompleteness Theorem. Although the digits of Ω cannot be found, many general properties of Ω are known; for example, it is known to be normal and transcendental - in fact, these properties are shared by every infinite algorithmically random sequence. 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. ... In the computer science subfield of algorithmic information theory the Chaitin constant or halting probability is a construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or programming language will halt. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ... A real number a is first-order definable in the language of set theory, without parameters, if there is a formula Ï† in the language of set theory, with one free variable, such that a is the unique real number such that Ï†(a) holds (in the von Neumann universe V). ... In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ... In mathematical logic, GÃ¶dels incompleteness theorems are two celebrated theorems proven by Kurt GÃ¶del in 1931. ... In mathematics, a normal number is, roughly speaking, a real number whose digits show a random distribution with all digits being equally likely. ... In mathematics, a transcendental number is any complex number that is not algebraic, that is, not the solution of a non-zero polynomial equation with integer (or, equivalently, rational) coefficients. ...

## History

The field was developed by Andrey Kolmogorov, Ray Solomonoff and Gregory Chaitin, starting in the late 1960s. 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). Per Martin-Löf also contributed significantly to the information theory of infinite sequences. Andrey Nikolaevich Kolmogorov (Russian: ÐÐ½Ð´Ñ€ÐµÌÐ¹ ÐÐ¸ÐºÐ¾Ð»Ð°ÌÐµÐ²Ð¸Ñ‡ ÐšÐ¾Ð»Ð¼Ð¾Ð³Ð¾ÌÑ€Ð¾Ð²) (April 25, 1903 - October 20, 1987) was a Soviet mathematician who made major advances in different academic fields (among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity). ... Ray Solomonoff (born 1926) invented the concept of algorithmic probability around 1960. ... Gregory John Chaitin (born 1947) is an Argentine-American mathematician and computer scientist. ... The 1960s decade refers to the years from January 1, 1960 to December 31, 1969, inclusive. ... Leonid Levin (born November 2, 1948, USSR) is a computer scientist. ... Per Martin-LÃ¶f 2004 Per Martin-LÃ¶f is a Swedish logician, philosopher, and mathematician born in 1942. ...

Chaitin's account of the history of AIT.

Crediting Kolmogorov (over Chaitin especially) with developing AIT is an example of the Matthew effect. The Matthew effect may refer to related ideas depending on context: // Biblical Matthew effect alludes to a line spoken by the Master in Jesuss parable of the talents in the Christian Bible: For unto every one that hath shall be given, and he shall have abundance: but from him...

## Precise Definitions

Main article: Kolmogorov Complexity

A binary string is said to be random if the Kolmogorov complexity of the string is at least the length of the string. A simple counting argument shows that some strings of any given length are random, and almost all strings are very close to being random. Since Kolmogorov complexity depends on a fixed choice of universal Turing machine (informally, a fixed "description language" in which the "descriptions" are given), the collection of random strings does depend on the choice of fixed universal machine. Nevertheless, the collection of random strings, as a whole, has similar properties regardless of the fixed machine, so one can (and often does) talk about the properties of random strings as a group without having to first specify a universal machine. 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. ... 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. ...

Main article: Algorithmically random sequence

An infinite binary sequence is said to be random if, for some constant c, the Kolmogorov complexity of every initial segment (with length n) of the sequence is at least n-c. Importantly, the complexity used here is prefix-free complexity; if plain complexity were used, there would be no random sequences. However, with this definition, it can be shown that almost every sequence (from the point of view of the standard measure - "fair coin" or Lebesgue measure - on the space of infinite binary sequences) is random. Also, since it can be shown that the Kolmogorov complexity relative to two different universal machines differs by at most a constant, the collection of random infinite sequences does not depend on the choice of universal machine (in contrast to finite strings). This definition of randomness is usually called Martin-Löf randomness, after Per Martin-Löf, to distinguish it from other similar notions of randomness. It is also sometimes called 1-randomness to distinguish it from other stronger notions of randomness (2-randomness, 3-randomness, etc.). Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm. ... 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. ... In mathematics, a measure is a function that assigns a number, e. ... Per Martin-LÃ¶f 2004 Per Martin-LÃ¶f is a Swedish logician, philosopher, and mathematician born in 1942. ...

(Related definitions can be made for alphabets other than the set {0,1}.)

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. ... Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm. ... Around 1960, Ray Solomonoff invented the concept of algorithmic probability. ... In the computer science subfield of algorithmic information theory the Chaitin constant or halting probability is a construction by Gregory Chaitin which describes the probability that a randomly generated program for a given model of computation or programming language will halt. ... Chaitin-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 algorithmic information theory, if {Dn}n &#8712; N and {En}n &#8712; N are distribution ensembles (on &#937;) then we say they are computationally indistinguishable if for any probabilistic, polynomial time algorithm A and any polynomal function f there is some m such that for all n > m: where... Let be a countable index set. ... It has been suggested that Meta-epistemology be merged into this article or section. ... In algorithmic information theory, the invariance theorem, originally proved by Ray Solomonoff, states that a universal Turing machine provides an optimal means of description, up to a constant. ... The minimum description length principle is a formalization of Occams Razor in which the best hypothesis for a given set of data is the one that leads to the largest compression of the data. ... Minimum message length (MML) is a formal information theory restatement of Occams Razor: even when models are not equal in goodness of fit accuracy to the observed data, the one generating the shortest overall message is more likely to be correct (where the message consists of a statement of... Let be a uniform ensemble and be an ensemble. ... Let G be a deterministic polynomial time function from N<? to N<? with stretch function l:N ? N, so that if x has length n then G(x) has length l(n). ... Uniform ensemble is a distribution ensemble, uniformly distributed over strings of length . ... Results from FactBites:

 Complexity & Information Theory (1531 words) The central idea of algorithmic information theory is to quantify the information content of an object or bit string in terms of its shortest description. We define the algorithmic information content I(x) of an object (or bit string) x as the length of the shortest self delimiting program(s) for a Universal Turing Machine U which generates a description of that object for a given level of precision. The string's algorithmic information content, or aglorithmic complexity, is bounded from above by the length of the binary sequence specifying 'forty', together with the code which tells the computer to print a digit a certain number of times.
More results at FactBites »

Share your thoughts, questions and commentary here
Press Releases | Feeds | Contact