Russian Mathematical Surveys
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Uspekhi Mat. Nauk:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Russian Mathematical Surveys, 1970, Volume 25, Issue 6, Pages 83–124
DOI: https://doi.org/10.1070/RM1970v025n06ABEH001269
(Mi rm5428)
 

This article is cited in 409 scientific papers (total in 409 papers)

The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms

A. K. Zvonkin, L. A. Levin
References:
Abstract: In 1964 Kolmogorov introduced the concept of the complexity of a finite object (for instance, the words in a certain alphabet). He defined complexity as the minimum number of binary signs containing all the information about a given object that are sufficient for its recovery (decoding). This definition depends essentially on the method of decoding. However, by means of the general theory of algorithms, Kolmogorov was able to give an invariant (universal) definition of complexity. Related concepts were investigated by Solomonoff (U.S.A.) and Markov. Using the concept of complexity, Kolmogorov gave definitions of the quantity of information in finite objects and of the concept of a random sequence (which was then defined more precisely by Martin-Löf). Afterwards, this circle of questions developed rapidly. In particular, an interesting development took place of the ideas of Markov on the application of the concept of complexity to the study of quantitative questions in the theory of algorithms. The present article is a survey of the fundamental results connected with the brief remarks above.
Received: 07.08.1970
Russian version:
Uspekhi Matematicheskikh Nauk, 1970, Volume 25, Issue 6(156), Pages 85–127
Bibliographic databases:
Document Type: Article
UDC: 519.24+517.11+519.9
MSC: 68Q30, 94B35
Language: English
Original paper language: Russian
Citation: A. K. Zvonkin, L. A. Levin, “The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms”, Uspekhi Mat. Nauk, 25:6(156) (1970), 85–127; Russian Math. Surveys, 25:6 (1970), 83–124
Citation in format AMSBIB
\Bibitem{ZvoLev70}
\by A.~K.~Zvonkin, L.~A.~Levin
\paper The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms
\jour Uspekhi Mat. Nauk
\yr 1970
\vol 25
\issue 6(156)
\pages 85--127
\mathnet{http://mi.mathnet.ru/rm5428}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=307889}
\zmath{https://zbmath.org/?q=an:0222.02027}
\transl
\jour Russian Math. Surveys
\yr 1970
\vol 25
\issue 6
\pages 83--124
\crossref{https://doi.org/10.1070/RM1970v025n06ABEH001269}
Linking options:
  • https://www.mathnet.ru/eng/rm5428
  • https://doi.org/10.1070/RM1970v025n06ABEH001269
  • https://www.mathnet.ru/eng/rm/v25/i6/p85
  • This publication is cited in the following 409 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Успехи математических наук Russian Mathematical Surveys
    Statistics & downloads:
    Abstract page:2572
    Russian version PDF:989
    English version PDF:51
    References:118
    First page:2
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024