Algorithmic Information

From glossariumBITri
Jump to: navigation, search

Burgin, Mark (2011), interactive-glossariumBITri, 1(1)

  • Mark BURGIN, Department of Mathematics, University of California Los Angeles
Usage domain: Computer science, coding science, Algorithmic information Theory, Complexity theory
Type: concept
Other languages: S: información algorítmica, F: information algorithmique, G: algorithmische Information

Algorithmic information reflects aspects and properties of information related to algorithms (s. also Algorithmic information Theory). 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:


  • 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, 13: 547-569.
  • KOLMOGOROFF, A. N. (1965). Three approaches to the quantitative definition of ‘information'. Problems of Information Transmission, 1(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, 7: 1-22 (I part), 224-254 (II part).