Book review

[This volume edited by A.N. Shiryaev.]

This is an annotated translation from the work in Russian of the same name published in Moscow in 1987. The name of A.N. Kolmogorov (1903-1987), one of the most prominent mathematicians of the century, needs no presentation to the scientific audience. The impact of his work on the contemporary mathematics is extremely wide. In particular, this holds for his studies in Information Theory and the Theory of Algorithms.

The volume includes 13 papers of Kolmogorov (some of them are written jointly with other mathematicians, such as I.M. Gelfand, A.M. Yaglom, V.A. Uspensky, V.M. Tikhomirov, Ya.M. Barzdin). Most of the papers concern information theory. Kolmogorov's work in the theory of algorithms is presented mainly by the papers "On the notion of algorithm" and "To the definition of algorithm", but several other papers are also related to this theory, since they study an algorithmic approach to information theory. Extensive comments to the papers are added by Kolmogorov himself and by R.L. Dobrushin, A.Kh. Shen, V.M. Tikhomirov, A.Sh. Shen, Ya.M. Barzdin, Ya.G. Sinai, V.A. Uspensky and A.L. Semyonov. Two appendices present Kolmogorov's papers which remained in manuscript form before. The scientific biography of Kolmogorov is considered in detail in the enclosed survey by N.N. Bogolyubov, B.V. Gnedenko and S.L. Sobolev. Other enclosed materials also add essential strokes to this biography.

As Kolmogorov notes, a considerable part of the works in information theory can be reviewed in connection with the following three approaches to the introduction of the main notions of the theory: (i) purely combinatorial approach, (ii) probabilistic approach, (iii) algorithmic approach. Kolmogorov's original contributions in all these directions are presented in the volume, as well as original applications of information theory to the theory of dynamical systems. These works gave rise to numerous studies by other researchers (let us mention as an example only the numerous further studies on e-entropy and e-capacity of classes of functions). A considerable amount of information about such continuations and extensions of Kolmogorov's work can be found in the comments to the papers.

The volume presents Kolmogorov's main contribution to the theory of algorithms which is the introduction of a general notion of algorithm (studied jointly with V.A. Uspensky). This notion, proposed shortly after 1950, covers a great number of kinds of algorithms having a local character. It is reasonable to conjecture that the general intuitive notion of an algorithm with a local character is correctly captured in this way. As well known, mathematical definitions of a certain general notion of algorithm have been given not later than 1936, and these definitions are widely used now, but they pretend to encompass all possible algorithms only extensionally. The level of generality of Kolmogorov's definition could be better evaluated only when the computer science began to develop rapidly (about 10-15 years after 1950).

The volume will be of great use for many researchers and students of mathematics, mechanics and computer science, as well as for historians of mathematics. It must be strongly recommended also for each scientific library covering some of these fields.