Algorithmic information theory was established by Ray Solomonoff, who invented algorithmic probability to solve Bayes' rule problems in statistics. Ray presented his findings at a 1960 Caltech conference and in "A Preliminary Report on a General Theory of Inductive Inference." 

Recent studies have merged computer science and information theory into algorithmic information theory. This domain is alternatively referred to as its primary outcome, Kolmogorov complexity. 

How much do we learn about a phenomenon through observation, and how do we quantify that learning? 

The premise of both 'classical' (Shannon) and algorithmic information theory is that this quantity can be quantified by the smallest number of bits required to express the observation. Kolmogorov's algorithmic theory is nonprobabilistic; any computer program that computes (prints) the observation string and then terminates is valid, while Shannon's theory considers optimal description methods for a probability distribution. The length of the shortest computer program that outputs the string and then exits provides a measure of the amount of information contained in the string (in bits).

Kolmogorov complexity

Kolmogorov complexity, also called algorithmic information, comes in several forms. The most common one is based on self-delimiting programs and is primarily the work of Leonid Levin. Per-Martin-Lof also made essential contributions to the theory of information for infinite sequences. Mark Burgin proposed an axiomatic approach to algorithmic information theory based on the Blum axioms in a paper that Andrey Kolmogorov was submitting for publication. 

In algorithmic information theory, the axiomatic method includes other ways of looking at things. It is possible to think of different ways to measure algorithmic information as exceptional cases of ways to measure algorithmic information described by axioms. Instead of proving similar theorems, like the basic invariance theorem, for each measure, these results can be quickly drawn from a single theorem already proven in the axiomatic setting. In math, this is a general benefit of the formal method. In the book, the axiomatic approach to algorithmic information theory was improved and used to measure software metrics.

Mathematical aspects

The concept of Kolmogorov complexity provides a novel approach to comprehending the mathematical aspects of information, enabling the description of the underlying structures present in the universe. The information elucidates the cultural frameworks encompassing scientific, legal, and market establishments, artistic and musical domains, knowledge systems, and belief systems. 

Information is utilized to characterize the structures and processes of biological phenomena and events occurring within the physical environment. The application of knowledge is most prominently observed within the engineering fields of computer science and telecommunications.

Conclusion

AIT mostly looks at ways to measure the amount of information that can't be removed from strings or other data structures. Since most mathematical objects can be described as strings or as the end of a series of strings, it can be used to study a wide range of mathematical objects, including integers. One of the main reasons for AIT is the study of how mathematical things carry information, such as in the field of metamathematics, as shown by the incompleteness results listed below. 

The other main reasons were getting past classical information theory's limitations for single and fixed objects, formalizing randomness, and finding a meaningful probabilistic inference without knowing the probability distribution (independent and identically distributed, Markovian, or stationary). In this way, it is clear that AIT is based on the relationships between three main mathematical ideas: algorithmic complexity, algorithmic randomness, and algorithmic chance.

Image source: Unsplash