Contents: 1) Direct information sizes; 2) Dual complexity measures; 3) Origin and advantages of the axiomatic approach to algorithmic informationThe 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 Algorithmic information measures information that is necessary to construct (build) a constructive object by means of some system of algorithm 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).
All kinds of *Direct static information size*depends only on an algorithm/program that is measured. Direct static information size usually reflects information in the algorithm/program representation. The length of a text (of an algorithm) measures information in bits. If we say that a memory has the capacity 1 gigabytes, it means that it is possible to store 8´10^{9}bits of information in this memory.*Direct functional**information size*depends both on an algorithm/program that is measured and on the input. Examples of a direct functional information size are such popular measures as time of a computation or space used in a computation.*Direct Processual**information size*depends on an algorithm/program, its realization, and on the input. Examples of a direct processual information size are time that it takes to process given input or the number of data transactions between memories of different type used in this process.
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 Let i Î I } be a class of algorithms, A be an algorithm that works with elements from I as inputs and a: I ® Nbe 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 (A, a)-information size a_{A}^{o} 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 asa When there is no such When the class
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
- BLUM, M. (1967) On the Size of Machines, Information and Control, v. 11, pp. 257–265
- BLUM M. (1967a) A Machine-independent Theory of Complexity of Recursive Functions, Journal of the ACM, v. 14, No.2, pp. 322–336
- 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. (2005)
*Super-recursive algorithms*, Monographs in computer science, Springer. - BURGIN, Mark (2010).
*Theory of Information: Fundamentality, Diversity and Unification*. Singapore: World Scientific Publishing
| 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 entriesWhenever 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) >