Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS

Тел.: +7 (495) 625-9241


K-complexity in Context of Modern Information Technologies


S.P. Levashkin, V.V. Alexandrov

In 1965 the titular paper «Three approaches to the definition of the concept «quantity of information» by A.N. Kolmogorov has appeared in «The problems of information transmission», which opened a new direction as a result of many years of his research of information theory. Thus algorithmic theory of information and Kolmogorov's complexity had appeared. The problem of evaluation of object's complexity belongs to fundamental and ancient scientific problems and is most difficult to formalize. This problem has philosophic, metaphysic and natural-science aspects, and the range of its application varies from cosmic bodies to common numbers. The first problem this the new theory had addressed was to define quantative measure of information i.e. numeric estimation of message «informativity». The notion of entropy allowed to solve great variety of important problems related to transmission and storage of discrete data. But all attempts to extend this notion to continuous signals failed. A.N. Kolmogorov discovered new trend in information theory, he created algorithmic theory of information based on the notion of Kolmogorov's complexity. Due to rapid growth of information technologies observed last 10 years the question of Kolmogorov's research place has emerged one way or the other related to this technologies. Of course, K-complexity and algorithmic theory of information are still waiting for new impulses for it's development, firstly the practical. It is turned out that K-complexity can not be implemented algorithmically. Another words, for any binary sequence X the constructive way to obtain the complexity K(X) does not exist. The development of algorithmic information theory has gone to «theoretical» way, which resulted in obtaining various estimations for K(X) preferably for «common» situations most of which are fairly artificial. This led to the kind of sport competition between mathematicians. At the same time it has become almost impossible for engineers and informatics to overcome complex mathematical constructions. Which in turn resulted in interest loss for Kolmogorov's theory among the practicians. The rich Kolmogorov's legacy is urgently demands careful study and practical development in application to modern information technologies. We are in no doubt that this legacy is also rich in content as the new technologies and doubtfully will assist it's further improvement and development.
June 24, 2020
May 29, 2020

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio