Algorithmic Information Theory
| Collection | GlossariumBITri |
|---|---|
| Author | José María Díaz-Nafría Mark Burgin |
| Editor | Mark Burgin |
| Year | 2016 |
| Volume | 2 |
| Number | 1 |
| ID | 2 |
| Object type | Theory |
| Domain | Coding Theory Complexity Theory Computer Science Information Theory |
| es | Teoría Algorítmica de la Información |
| fr | Théorie Algorithmique de la Information |
| de | Algorithmische Informationstheorie |
Algorithmic information theory is based on the concept of Kolmogorov or algorithmic complexity of objects, which provides means to measure the intrinsic information related to objects via their algorithmic description length (s. also algorithmic information). As it is generally assumed, this measure was introduced and studied by three authors: Ray Solomonoff (1964), Andrey Kolmogorov (1965) and Gregory Chaitin (1966). Algorithmic approach explicates an important property of information, connecting information to means used for accessing and utilizing information. Information is considered not as some inherent property of different objects but is related to algorithms that use, extract or produce this information. In this context, a system (person) with more powerful algorithms for information extraction and management can get more information from the same carrier and use this information in a better way than a system that has weaker algorithms and more limited abilities. This correlates with the conventional understanding of information. For instance, system (person) that (who) has a code C can read codified in C texts, while those who do not have this code cannot read such texts. As a result, efficiency or complexity of algorithms becomes a measure of information in contrast to the traditional approach when information is treated as uncertainty or diversity. Efficiency is a clue problem and a pivotal characteristic of any activity. Consequently, measures of efficiency and complexity provide means for measuring information as a dynamic essence.
Algorithmic information theory has been applied to a wide range of areas, including theory of computation, combinatorics, medicine, biology, neurophisiology, physics, economics, hardware and software engineering, probability theory, statistics, inductive reasoning, and machine learning.
Symbolic objects and systems
Objects considered in algorithmic information theory are strings of symbols because the most habitual representation of information uses symbols and it is possible to represent other structures codifying them by strings of symbols. It is natural to interpret such strings as words or texts in some language. It means that information is presented and processed in the symbolic form and all systems are represented by their symbolic (semiotic) models (symbol). Exact models have mathematical structure. The main question is how much information we need to reconstruct (compute) a given string (word). Thus, the traditional approach in algorithmic information theory treats only symbolic information. This question relates information to complexity because measure of necessary information appears here as a measure of complexity of the string reconstruction.
Reconstructive sense of algorithmic information
Reconstruction/computation of a string of symbols is an action that is realized as a process. Its complexity depends on means that are used for reconstruction. To make this idea precise a concept of an algorithm is used. Namely, strings are reconstructed (built) by algorithms. Algorithms are working in the domain of strings and this domain usually consists of all finite strings in some alphabet. In this context, an algorithm (it is also possible to say, automaton or computer) takes one string of symbols z and eventually produces another string x, as represented in the following figure.
The input string is a carrier of information about the output string, i.e., string that we are going to reconstruct/compute. It is possible to consider the input string z as the program that has been given to the algorithm/machine for computing x. This program provides information about x for an algorithm (computing device). In such a way, researchers come to information size (complexity) of a string of symbols, which is the theory's fundamental concept. Note that very often, information content of a string is called Kolmogorov complexity. Namely, the information content C(x) of a string x is the minimum quantity of information needed to reconstruct this string. In the conventional approach, such quantity of input information is measured by the size of information carrier and as carriers are strings of symbols the volume of a string z is the length l(z) of this string. Thus, the length of the shortest program for calculating the output string x gives the measure of information needed to reconstruct/compute this string.
Versions of algorithmic information measures
Although this is the most popular information measure in algorithmic information theory, other versions of algorithmic measures of information have been introduced. The most known of then are: uniform complexity KR(x), prefix complexity or prefix-free complexity K(x), monotone complexity Km(x), conditional Kolmogorov complexity CD(x), time-bounded Kolmogorov complexity Ct(x), space-bounded Kolmogorov complexity Cs(x), and resource-bounded Kolmogorov complexity Ct,s(x). In addition, algorithmic information theory has been extended to infinite processes, infinite words (Chaitin, 1976; 1977), super-recursive algorithms (Burgin, 1995; 2005; Schmidhuber, 2002) and quantum computations (Svozil, 1996; Vitanyi, 1999; 2001). Each new development of algorithmic information theory has been connected to considering different classes of algorithms as means for information acquisition, processing and utilization. At first, only subrecursive classes (i.e., subclasses of the class of all Turing machines, such as the class of all delimiting Turing machines) were used for this purpose. Later more powerful, super-recursive algorithms, such as inductive Turing machines were applied to the study of algorithmic information (s. also algorithmic information).
Existence of a variety of approaches and algorithmic measures of information caused a necessity for a unifying approach. This approach called axiomatic information theory was introduced and developed by Burgin (1982; 1990; 2005; 2010).
Algorithmic vs. common sense information: object vs. carrier of information
An essential problem with algorithmic complexity as a measure of information is related to its information theoretical interpretation. It is generally assumed that the algorithmic complexity of a binary string x measures the amount of information in the string x. Thus, according to the algorithmic information theory, random sequences have maximum complexity as by definition, a random sequence can have no generating algorithm shorter than simply listing the sequence. It means that information content of random sequences is maximal.
Physicists were the first who attracted attention to this peculiarity. For instance, Richard Feynman (1999) wrote:
“How can a random string contain any information, let alone the maximum amount? Surely we must be using the wrong definition of 'information'?...”
To eliminate these contradictions and discrepancies that are prevalent in algorithmic information theory and to solve the problem of correct understanding the meaning of the function C(x), it is more adequate to consider C(x) and all its versions as measures of information about x or the information size of x with the special goal to build or reconstruct x. It means that in reality, x is not the carrier of information measured by C(x), but the object of this information. Thus, it becomes not surprising that people, or a machine, need more information about a random sequence of letters to reconstruct it than about a masterpiece, such as a poem by Dante or a novel by Cervantes.
Timely and semiotic aspects of algorithmic information with respect to other information meanings
In order to reconcile the common sense of information with the one provided by the algorithmic information theory, the timely distinction introduced by Weizsäcker (1984) between potential and actual information is also fruitful (Lyre, 2002). In our case, while the aforementioned carrier (z in the figure above) represents potential information (i.e. the possibility to reconstruct x), the object of information x represents actual information when the algorithmic system has effectively reconstructed it. By abstracting the algorithmic resources and therefore addressing to an alleged optimal means, the specificity of z with respect to a given algorithmic system is lost and only the objective of reconstruction, x, prevails. To this respect algorithmic information can be seen as actual information. On the contrary, the information concept provided by the Mathematical Theory of Communication (MTC), information entropy, exclusively refers to the degree of uncertainty at the recipient before being informed, thus abstracting the specific outcome. This shows that information entropy has a fundamental potential character complementary to algorithmic information.
The semiotic distinction between syntactic and semantic aspects offers as well some insights to distinguish algorithmic information from other senses of information. As argued by Lyre (2002) algorithmic information – unlike Shannon’s information – reflects, at the same time, semantic and syntactic aspects: “The algorithmic information content measures actual information under both syntactic and sematic aspects” (Lyre 2002, p. 38). In our context, x can be regarded as the semantic value of the algorithmic information or process (note x may be a set of operations with a particular effect on the environment, for instance, a manufacturing process, therefore it reflects not only semantics but also pragmatics), whereas z represents its syntactical value. In the invariant form of algorithmic information, z corresponds to the minimal syntactics to address the object semantics represented by x. On the contrary, is well known that MTC programmatically restrict information to its syntactic dimension.
These same distinctions are to some extent also used in the common senses of information. When we consider that we need information, this is regarded in its potential value. While when we say that we have the information someone need, this is regarded in its actual value, though what we factually have is some z that might eventually be shared and we suppose the third party has the algorithmic means (as we do) to reconstruct some x, which for some reason might be cherished. Then having z is practically equivalent to having x. Although it would not be formulated as such, it is commonly clear that z has a syntactical value, whereas x has a semantic one.
References
- BURGIN, M. (1982). “Generalized Kolmogorov complexity and duality in theory of computations”. Soviet Math. Dokl., v.25, No. 3, pp. 19–23
- BURGIN, M. (1990). “Generalized Kolmogorov Complexity and other Dual Complexity Measures”. Cybernetics, No. 4, pp. 21–29
- BURGIN, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005
- BURGIN, Mark (2010). Theory of Information: Fundamentality, Diversity and Unification. Singapore: World Scientific Publishing
- CHAITIN, Gregory J. (1969). “On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers”. Journal of the ACM 16: 407.
- CHAITIN, G.J. Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987
- KOLMOGOROV, A.N. (1965). “Three Approaches to the Quantitative Definition of Information”. Problems Inform. Transmission, Vol.1, Num.1, pp. 1–7.
- LYRE, H. (2002). Inforsmationstheorie. Munich: Wilhelm Fink Verlag
- SOLOMONOFF, Ray (March 1964). “A Formal Theory of Inductive Inference Part I”. Information and Control, Vol. 7, Num. 7, pp. 1–22.
- SOLOMONOFF, Ray (June 1964). “A Formal Theory of Inductive Inference Part II”. Information and Control, Vol. 7, Num. 2, pp. 224–254.
- WEIZSÄCKER, C.F. (1985). Aufbau der Physik. Munich: Hanser.