Contents: 1) Direct information sizes; 2) Dual complexity measures; 3) Origin and advantages of the axiomatic approach to algorithmic information The existence of a variety of algorithmic measures of information brought forth a necessity for a unifying approach (®Algorithmic information theory, and Algorithmic information). This approach has been called axiomatic information theory. Algorithmic information measures information that is necessary to construct (build) a constructive object by means of some system of algorithm A. That is why algorithmic information is dual to a static complexity measure (static direct information size) a of a constructive object x and is called by the name (A, a)- information size of x. Dual information size is constructed from direct information size by the minimization operation. For instance, a natural direct information size for algorithms/programs is the length of their description (symbolic representation), and the same is true for data. It is possible to measure length in such natural units of information as bits and bytes. When taking the dual to this measure in the class of recursive algorithms, we obtain Kolmogorov complexity or recursive information size (®Kolmogorov complexity). The axiomatic description of dual information size uses axiomatic descriptions of direct complexity measures suggested by Blum (1967; 1967a) and further developed by Burgin (1982; 2005; 2010). 1. Direct information sizes All kinds of direct information sizes are divided into three classes:
2. Dual complexity measures Information size, or algorithmic complexity, can be defined for different classes of algorithms, resulting in different measures. However, all these measures are constructed by a similar technique. As a result, it is possible to axiomatize this approach. The result of this axiomatization is called dual complexity measures (Burgin, 2005). As before, we are going to call these measures by the name dual information size as they reflect information necessary to compute (construct) a given object. These measures give much more opportunities to estimate information size of words and infinite strings than conventional types of information size (Kolmogorov complexity). Let A = { Ai ; i Î I } be a class of algorithms, A be an algorithm that works with elements from I as inputs and a: I ® N be a direct static information size of algorithms from a class A that satisfies axioms from (Blum, 1967) or (Burgin, 2005, Ch.5). Elements of I are usually treated as programs for the algorithm A. The dual to a complexity measure or (A, a)-information size aAo of an object (word) x with respect to the algorithm A is the function from the codomain (the set of all outputs) Y of A that is defined as aAo(x) = min { a(p); p Î I and A(p) = x}. When there is no such p that A(p) = x, the value of aAo at x is undefined. When the class A has universal algorithms, the invariance theorem is proved stating that aUo(x) where U is a universal algorithm in the class A is an optimal – in some sense – measure in the class of all measures aAo(x) with A from the class A (Burgin, 2010). This allows one to take aUo(x) as an axiomatic complexity measure (axiomatic information size) in the class A. 3. Origin and advantages of the axiomatic approach to algorithmic information An axiomatic approach to algorithmic information theory was introduced by Burgin in a paper presented for publication by Kolmogorov (Burgin 1982) and further developed in the paper (Burgin, 1990) and in books (Burgin 2005; 2010). The axiomatic approach encompasses other approaches in the algorithmic information theory. It is possible to treat different measures of algorithmic information as particular cases of axiomatically defined measures of algorithmic information. Instead of proving similar theorems, such as the basic invariance theorem, for each particular measure, it is possible to easily deduce all such results from one corresponding theorem proved in the axiomatic setting. This is a general advantage of the axiomatic approach in mathematics. References
| Entries
New entry. For doing a new entry: (1) the user must be identified as an authorized user(to this end, the "sign in" link at the page bottom left can be followed). (2) After being identified, press the "edit page" button at he upper right corner. (3) Being in edition mode, substitute -under this blue paragraph- "name" by the authors' names, "date" by the date in which the text is entered; and the following line by the proposed text. At the bottom of the entry, the references -used in the proposed text- must be given using the normalized format. (4) To finish, press the "save" button at the upper right corner. The entry will be reviewed by the editor and -at least- another peer, and subsequently articulated in the article if elected. Name (dd/mm/yyyy)
[To be substituted by the author with the proposed text] Incorporated entries Whenever an entry is integrated in the article (left column) the corresponding entry is reflected in this section. Mark Burgin (17/2/2011) [After being reviewed, the entry was moved to the article column, 16/12/2011] |
Glossary (en) >