Algorithmic Information
| Collection | GlossariumBITri |
|---|---|
| Author | Mark Burgin |
| Editor | Mark Burgin |
| Year | 2016 |
| Volume | 2 |
| Number | 1 |
| ID | 1 |
| Object type | Concept Theory |
| Domain | ICT Transdisciplinary |
| es | información algorítmica |
| fr | information algorithmique |
| de | algorithmische Information |
Algorithmic information reflects aspects and properties of information related to algorithms (s. also Algorithmic Information Theory and Axiomatics for Algorithmic Information). Many information processes, such as network messaging or computer information processing, have algorithmic nature as they are performed according to various algorithms.
Two kinds of algorithmic information are considered: (1) algorithmic information necessary to build a constructive object by a given system of algorithms and (2) algorithmic information in an object, e.g., message, which allows making simpler construction of another object. The most popular measure of algorithmic information of the first type is absolute Kolmogorov or algorithmic complexity. The most popular measure of algorithmic information of the second type is relative Kolmogorov or algorithmic complexity (Kolmogorov complexity).
According to the classes of algorithms used for information acquisition, processing and utilization, three types of algorithmic information have been separated and studied:
- subrecursive algorithmic information,
- recursive algorithmic information (Kolmogorov complexity), and
- super-recursive algorithmic information (Super-recursive Kolmogorov complexity).
References
- BURGIN, M. (2010). Theory of Information: Fundamentality, Diversity and Unification. Singapore: World Scientific Publishing.
- CHAITIN, G. J. (1966). “On the length of programs for computing finite binary sequences”. Journal of the Association for Computing Machinery, Vol. 13, 547-569.
- KOLMOGOROFF, A. N. (1965). Three approaches to the quantitative definition of ‘information'. Problems of Information Transmission, Vol. 1, Num. 1, 3-11.
- SOLOMONOFF, R. J. (1960). A Preliminary Report on a General Theory of Inductive Inference. Report V-131, Zator Co., Cambridge, Ma. Feb 4, 1960.
- SOLOMONOFF, R. J. (1964). A formal theory of inductive inference. Inf. Control, Vol. 7, 1-22 (I part), 224-254 (II part).