pith. sign in

arxiv: 1907.05056 · v1 · pith:JXIEEFSLnew · submitted 2019-07-11 · 💻 cs.GL · cs.IT· math.IT

Kolmogorov complexity in the USSR (1975--1982): isolation and its end

V.V. V'yugin This is my paper

Pith reviewed 2026-05-24 23:01 UTC · model grok-4.3

classification 💻 cs.GL cs.ITmath.IT
keywords algorithmic information theoryKolmogorov complexityhistory of computingSoviet scienceLevinKolmogorov seminarresearch isolation
0
0 comments X

The pith

Research on algorithmic information theory in the USSR declined after the early 1970s until a Kolmogorov seminar talk restarted activity among younger researchers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a first-hand account of reduced activity in algorithmic information theory inside the Soviet Union between 1975 and 1982. It describes how early enthusiasm from the 1960s and beginning of the 1970s gave way to a sharp drop in the number of people working in the area after L.A. Levin produced foundational papers and then left the country. The narrative identifies A.N. Kolmogorov's talk at a Moscow State University seminar as the event that ended this period of isolation and prompted several younger researchers to produce new results.

Core claim

After a period of strong interest in the 1960s and early 1970s the number of researchers active in algorithmic information theory inside the USSR fell significantly; Levin's departure left a gap that was later closed when Kolmogorov's seminar presentation at Moscow State University drew in new participants who then obtained original results.

What carries the argument

The sequence of decline after Levin's emigration followed by revival triggered by Kolmogorov's seminar at the Logic and Algorithms Division.

If this is right

  • Levin's papers remained influential even while local participation dropped.
  • A single seminar organized by a senior figure could directly recruit and motivate a new cohort of researchers.
  • Emigration of leading contributors produced a measurable gap in national output that lasted several years.
  • Renewed interest appeared first among younger researchers once the seminar provided an entry point.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Individual departures and targeted seminars can produce sharper swings in local research output than broad institutional policies alone would predict.
  • Similar boom-bust-revival patterns may appear in other theoretical fields under conditions of restricted travel and communication.
  • Cross-checking this timeline against publication databases or additional participant interviews would test the claimed scale of the decline.
  • The account implies that preserving oral histories of small research communities can reveal mechanisms of continuity that formal publication counts miss.

Load-bearing premise

The author's personal memory accurately records the overall level of research activity, the reasons for its decline, and the causal effect of Levin's departure together with Kolmogorov's seminar in restarting the work.

What would settle it

Publication records, seminar notes, or other contemporary accounts showing continued high activity or different timing for any revival between 1975 and 1982.

read the original abstract

These reminiscences are about the "dark ages" of algorithmic information theory in the USSR. After a great interest in this topic in 1960s and the beginning of 1970s the number of people working in this area in the USSR decreased significantly. At that time L.A. Levin published a bunch of papers that were seminal for the modern algorithmic information theory. Then he left the USSR, and the new wave of interest was triggered by the talk of A.N. Kolmogorov at a Moscow State (Lomonosov) University Mathematical Department (Logic and Algorithms Division) seminar organized by him; several younger researchers obtained some new results in algorithmic information theory.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript is a personal reminiscence describing the 'dark ages' of algorithmic information theory research in the USSR from 1975 to 1982. It claims that interest declined significantly after the 1960s and early 1970s, that L.A. Levin produced seminal papers before leaving the country, and that a new wave of activity was triggered by A.N. Kolmogorov's talk at a Moscow State University seminar, after which younger researchers obtained new results.

Significance. If the recollections prove accurate, the paper supplies a primary-source account of institutional and personal factors affecting a specialized research area in a closed society, which could aid historians of computer science in understanding periods of isolation and revival. Such insider narratives are rare and can complement archival studies when properly contextualized.

major comments (2)
  1. [Abstract] Abstract and main narrative: the central claim that 'the number of people working in this area in the USSR decreased significantly' is load-bearing for the theme of isolation but is advanced without any quantitative indicators, publication counts, lists of active researchers, or external references; this leaves the scale and timing of the decline unverified.
  2. [Main text] Main text: the assertion that the 'new wave of interest was triggered by' Kolmogorov's seminar talk is presented as causal without discussion of the talk's content, contemporaneous publications, or alternative explanations, making the restart mechanism difficult to assess independently.
minor comments (2)
  1. The manuscript contains no references, bibliography, or citations to related historical literature, which would assist readers in cross-checking the timeline and events.
  2. The title bounds the period to 1975--1982, yet the text does not explicitly justify these endpoints or contrast them with activity before 1975 or after 1982.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report on our personal reminiscence. The manuscript is explicitly framed as an insider account rather than a quantitative historical analysis, and we address the two major comments below.

read point-by-point responses

  1. Referee: [Abstract] Abstract and main narrative: the central claim that 'the number of people working in this area in the USSR decreased significantly' is load-bearing for the theme of isolation but is advanced without any quantitative indicators, publication counts, lists of active researchers, or external references; this leaves the scale and timing of the decline unverified.

    Authors: The manuscript is presented as personal reminiscences, not as a systematic historical study. The statement reflects the author's direct observations of the research community during 1975-1982. We will revise the abstract and opening paragraphs to state explicitly that the assessment is qualitative and based on personal recollection, without implying exhaustive verification or quantitative data. revision: partial

  2. Referee: [Main text] Main text: the assertion that the 'new wave of interest was triggered by' Kolmogorov's seminar talk is presented as causal without discussion of the talk's content, contemporaneous publications, or alternative explanations, making the restart mechanism difficult to assess independently.

    Authors: The text conveys the author's recollection of the sequence of events, in which Kolmogorov's talk is remembered as the moment that renewed activity among younger researchers. As a personal narrative the manuscript does not attempt a full causal analysis. We will add a clarifying sentence noting that this is the author's perception of the triggering event and that the account is not intended to rule out other contemporaneous factors. revision: partial

Circularity Check

0 steps flagged

No circularity: historical narrative with no derivations or fitted claims

full rationale

The paper is a personal historical reminiscence with no equations, predictions, parameters, or first-principles derivations of any kind. The enumerated circularity patterns (self-definitional claims, fitted inputs renamed as predictions, load-bearing self-citations, uniqueness theorems, ansatz smuggling, or renaming of known results) have no applicability because there is no derivation chain to inspect. The text simply recounts events from the author's memory; it makes no mathematical or quantitative assertions that could reduce to their own inputs by construction. This is the expected non-finding for a non-technical historical account.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a historical narrative paper containing no technical derivations, fitted parameters, mathematical axioms, or postulated entities.

pith-pipeline@v0.9.0 · 5637 in / 1023 out tokens · 22657 ms · 2026-05-24T23:01:15.210680+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

71 extracted references · 71 canonical work pages · 1 internal anchor

  1. [1]

    О некоторых свойствах ∆ -случайных по Колмогорову конечных по- следовательностей

    Е.А.Асарин. О некоторых свойствах ∆ -случайных по Колмогорову конечных по- следовательностей. Теория вероятностей и её применения , 32(3), 1987, 556–558 . (E.A. Asarin. Some properties of Kolmogorov ∆-random finite sequences, Theory Probab. Appl., 32, 1987, 507–508)

    work page 1987

  2. [2]

    Колмогоровская сложность и алгорит- мическая случайность

    Н.К.Верещагин, В.А.Успенский, А.Шень. Колмогоровская сложность и алгорит- мическая случайность . /emdash.cyr М.: МЦНМО, 2013. 575с.(A. Shen, V.A. Uspensky, N. Vereshchagin, Kolmogorov complexity and algorithmic randomness . Mathematical Sur- veys and Monographs, volume 220. American Mathematical Society, Providence, RI, 2018.)

    work page 2013

  3. [3]

    Об инвариантных по Тьюрингу множествах, Доклады АН СССР , 229(4), 1976, 790–793.(V.V

    В.В.Вьюгин. Об инвариантных по Тьюрингу множествах, Доклады АН СССР , 229(4), 1976, 790–793.(V.V. V’jugin. On Turing invariant sets.Soviet Mathematics Dok- lady, 17, 1976, 1090–1094)

    work page 1976

  4. [4]

    Алгоритмическая энтропия (сложность) конечных объектов и её при- менения к определению случайности и количества информации

    В.В.Вьюгин. Алгоритмическая энтропия (сложность) конечных объектов и её при- менения к определению случайности и количества информации. /emdash.cyr В сборнике:Се- миотика и информатика, вып. 16. М.: ВИНИТИ, 1981, с.14–43.(V.V. Vyugin, Selecta Mathematica formerly Sovietica, 13(4), 1994, 357–389)

    work page 1981

  5. [5]

    Алгебра инвариантных свойств двоичных последовательностей

    В.В.Вьюгин. Алгебра инвариантных свойств двоичных последовательностей. Про- блемы передачи информации , 18(2), 1982, 83–100. (V.V. V’yugin. Algebra of Invariant Properties of Binary Sequences, Problems Inform. Transmission, 18(2), 1982, 147–161) 10

    work page 1982

  6. [7]

    О дефекте случайности конечного объекта относительно мер с задан- ными границами их сложности.Теория вероятностей и ее применения , 32(3), 1987, 558–563

    В.В.Вьюгин. О дефекте случайности конечного объекта относительно мер с задан- ными границами их сложности.Теория вероятностей и ее применения , 32(3), 1987, 558–563. (V.V. Vjugin. On Randomness Defect of a Finite Object Relative to Measures with Given Complexity Bounds, Theory Probab. Appl. , 32(3), 1987, 508–512)

    work page 1987

  7. [8]

    Сложность конечных объектов и обоснование понятий ин- формации и случайности с помощью теории алгоритмов.Успехи математических наук, 25(6), 1970, 85–127

    А.К.Звонкин, Л.А.Левин. Сложность конечных объектов и обоснование понятий ин- формации и случайности с помощью теории алгоритмов.Успехи математических наук, 25(6), 1970, 85–127. (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. Russian Math. Su...

    work page 1970

  8. [9]

    Три подхода к определению понятия /guillemotleft.cyrколичество информации/guillemotright.cyr

    А.Н.Колмогоров. Три подхода к определению понятия /guillemotleft.cyrколичество информации/guillemotright.cyr. Проблемы передачи информации, 1(1), 1965, 3–11.(A.N. Kolmogorov. Three approaches to the quantitative definition of information. Problems Inform. Transmission , 1(1), 1965, 1–7)

    work page 1965

  9. [10]

    К логическим основам теории информации и теории вероятностей

    А.Н.Колмогоров. К логическим основам теории информации и теории вероятностей. Проблемы передачи информации , 5(3), 1969, 3–7. (A.N. Kolmogorov. On the logical foundations of information theory and probability theory. Problems Inform. Transmission, 5(3), 1969, 1–4)

    work page 1969

  10. [11]

    Комбинаторные основания теории информации и исчисления веро- ятностей

    А.Н.Колмогоров. Комбинаторные основания теории информации и исчисления веро- ятностей. Успехи математических наук, 38(4), 1983, 27–36.(A.N. Kolmogorov. Com- binatorial foundations of information theory and the calculus of probabilities. Russian Math. Surveys , 38(4),1983, 29–40)

    work page 1983

  11. [12]

    О логических основаниях теории вероятностей

    А.Н.Колмогоров. О логических основаниях теории вероятностей. /emdash.cyr В кн.: А.Н.Колмогоров, Теория вероятностей и математическая статистика, М.:Наука, 1986, 467–471. (A.N.Kolmogorov. On logical foundations of probability. Lecture Notes in Mathematics, 1021, 1983, 1–5)

    work page 1986

  12. [14]

    О понятии случайной последовательности

    Л.А.Левин. О понятии случайной последовательности. Доклады АН СССР , 212(3), 1973, 548–550. (L.A. Levin. On the Notion of a Random Sequence. Sov. Math. Doklady , 14, 1973, 1413–1416)

    work page 1973

  13. [15]

    Законы сохранения (невозрастания) информации и вопросы обоснования теории информации.Проблемы передачи информации, 10(3), 1974, 30–35.(L.A

    Л.А.Левин. Законы сохранения (невозрастания) информации и вопросы обоснования теории информации.Проблемы передачи информации, 10(3), 1974, 30–35.(L.A. Levin. Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Proba- bility Theory. Problems Inform. Transmission, 10(3), 1974, 206–210)

    work page 1974

  14. [17]

    О принципе сохранения информации в интуиционистской математике

    Л.А.Левин. О принципе сохранения информации в интуиционистской математике. Доклады АН СССР , 227(6), 1976, 1293–1296.(L.A. Levin. On the principle of conserva- tion of information in intuitionistic mathematics.Soviet Math. Doklady, 17, 1976, 601–605) 11

    work page 1976

  15. [18]

    Доклады АН СССР, 227(4), 1976, 804–807.(L.A

    Л.А.Левин.Оразличныхмерахсложностиконечныхобъектов(аксиоматическоеопи- сание). Доклады АН СССР, 227(4), 1976, 804–807.(L.A. Levin. Various measures of com- plexity for finite objects (axiomatic description). Soviet Math. Doklady , 17, 1976, 522–526)

    work page 1976

  16. [19]

    Равномерные тесты случайности

    Л.А.Левин. Равномерные тесты случайности. Доклады АН СССР , 227(1), 1976, 33–

    work page 1976

  17. [20]

    (L.A. Levin. Uniform tests for randomness. Soviet Math. Doklady , 17(1), 1976, 337– 340)

    work page 1976

  18. [21]

    Л.А.Левин.Оразличныхмерахсложностиконечныхобъектов(аксиоматическоеопи- сание), Доклады АН СССР, 227(4), 1976, 804–807.(L.A. Levin. Various measures of com- plexity for finite objects (axiomatic description). Soviet Math. Doklady , 17, 1976, 522–526)

    work page 1976

  19. [22]

    Об одном конкретном способе задания сложностных мер.Доклады АН СССР, 234(3), 1977, 536–539.(L.A

    Л.А.Левин. Об одном конкретном способе задания сложностных мер.Доклады АН СССР, 234(3), 1977, 536–539.(L.A. Levin, On a concrete method of assigning complexity measures, Soviet Math. Doklady , 18, 1977, 727–731.)

    work page 1977

  20. [23]

    де Леу, Э.Ф

    К. де Леу, Э.Ф. Мур, К. Шеннон, Н. Шапиро, Вычислимость на вероятностных маши- нах, Автоматы (сб. переводов), М., ИЛ, 1956.(K. de Leeuw, E.F. Moore, C.E. Shannon, N. Shapiro. Computability by Probabilistic Machines. – In: Automata studies , edited by C.E. Shannon and J. McCarthy, Annals of Mathematics Studies , 34, lithoprinted, Prince- ton University Pre...

    work page 1956

  21. [24]

    Может ли (индивидуальная) последова- тельность нулей и единиц быть случайной? Успехи математических наук , 45(1), 1990, 105–162

    В.А.Успенский, А.Л.,Семёнов, А.Х.Шень. Может ли (индивидуальная) последова- тельность нулей и единиц быть случайной? Успехи математических наук , 45(1), 1990, 105–162. (V.A. Uspensky, A.L. Semenov, and A.K. Shen. Can an individual se- quence of zeros and ones be random? Russian Math. Surveys , 45(1), 1990, 121–189)

    work page 1990

  22. [25]

    Понятие (α,β)-стохастичности по Колмогорову и его свойства.Доклады АН СССР , 271(6), 1983, 1337–1340

    А.Х.Шень. Понятие (α,β)-стохастичности по Колмогорову и его свойства.Доклады АН СССР , 271(6), 1983, 1337–1340. (A.K. Shen. The concept of Kolmogorov ( α,β)- stochasticity and its properties. Soviet Math. Doklady , 28, 1983, 295–299)

    work page 1983

  23. [27]

    G.J. Chaitin. On the length of programs for computing binary sequences, Journal of the Association for Computing Machinery , 13, 1966, 547–569

    work page 1966

  24. [28]

    G.J. Chaitin. On the length of programs for computing binary sequences: Statistical con- siderations, Journal of the Association for Computing Machinery , 16, 1969, 145–159

    work page 1969

  25. [29]

    G.J. Chaitin. A theory of program size formally identical to information theory, Journal of the Association for Computing Machinery , 22, 1975, 329–340

    work page 1975

  26. [30]

    G.J. Chaitin. Algorithmic information theory, IBM Journal of Research and Development , 21, 1977, 350–359

    work page 1977

  27. [31]

    Cover, P

    T.M. Cover, P. G´ acs, R.M. Gray. Kolmogorov’s contributions to information theory and algorithmic complexity. Annals of Probability , 17(1), 1989, 840–865

    work page 1989

  28. [32]

    L.A. Levin. Some theorems on the algorithmic approach to probability theory and informa- tion theory. (1971 Ph.D. thesis, advisor: A.N. Kolmogorov). Annals of Pure and Applied Logic, 162(3), 2010, 224–235

    work page 1971

  29. [33]

    Levin, V.V

    L.A. Levin, V.V. V’yugin. Invariant properties of informational bulks. MFCS 1977: Math- ematical Foundations of Computer Science . Lecture Notes on Computer Science , 53, Springer, 1977, 359–364. 12

    work page 1977

  30. [34]

    L.A. Levin. Randomness conservation inequalities; information and independence in math- ematical theories. Information and Control , 61(1), 1984, 15–37

    work page 1984

  31. [35]

    M. Li, P. Vit´ anyi. An Introduction to Kolmogorov Complexity and Its Applications , 3rd ed. New York: Springer–Verlag, 2008

    work page 2008

  32. [36]

    Martin-L¨ of

    P. Martin-L¨ of. The definition of random sequences. Information and Control , 9, 1966, 602–619

    work page 1966

  33. [39]

    Kolmogorov complexity in the USSR (1975--1982): isolation and its end

    V.V. V’yugin. Algorithmic complexity and stochastic properties of finite binary sequences. The Computer Journal , 1999, 42(4), 1999, 294–317. 13 Колмогоровская сложность в СССР в 1975–1982: в изоляции и выход из нее В.В. Вьюгин∗ Аннотация Эти воспоминания относятся к наиболее /guillemotleft.cyrтёмному/guillemotright.cyr периоду развития алгорит- мической т...

    work page internal anchor Pith review Pith/arXiv arXiv 1999

  34. [40]

    О некоторых свойствах ∆ -случайных по Колмогорову конечных по- следовательностей

    Е.А.Асарин. О некоторых свойствах ∆ -случайных по Колмогорову конечных по- следовательностей. Теория вероятностей и её применения , 32(3), 1987, 556–558. (E.A. Asarin. Some properties of Kolmogorov∆ -random finite sequences,Theory Probab. Appl., 32, 1987, 507–508) 10

    work page 1987

  35. [41]

    Колмогоровская сложность и алгорит- мическая случайность

    Н.К.Верещагин, В.А.Успенский, А.Шень. Колмогоровская сложность и алгорит- мическая случайность . /emdash.cyr М.: МЦНМО, 2013. 575с. (A. Shen, V.A. Uspensky, N. Vereshchagin, Kolmogorov complexity and algorithmic randomness . Mathematical Surveys and Monographs, volume 220. American Mathematical Society, Providence, RI, 2018.)

    work page 2013

  36. [42]

    Об инвариантных по Тьюрингу множествах, Доклады АН СССР , 229(4), 1976, 790–793

    В.В.Вьюгин. Об инвариантных по Тьюрингу множествах, Доклады АН СССР , 229(4), 1976, 790–793. (V.V. V’jugin. On Turing invariant sets. Soviet Mathematics Doklady, 17, 1976, 1090–1094)

    work page 1976

  37. [43]

    Алгоритмическая энтропия (сложность) конечных объектов и её при- менения к определению случайности и количества информации

    В.В.Вьюгин. Алгоритмическая энтропия (сложность) конечных объектов и её при- менения к определению случайности и количества информации. /emdash.cyr В сборнике:Се- миотика и информатика , вып. 16. М.: ВИНИТИ, 1981, с.14–43. (V.V. Vyugin,Selecta Mathematica formerly Sovietica, 13(4), 1994, 357–389)

    work page 1981

  38. [44]

    Алгебра инвариантных свойств двоичных последовательностей

    В.В.Вьюгин. Алгебра инвариантных свойств двоичных последовательностей. Про- блемы передачи информации , 18(2), 1982, 83–100. (V.V. V’yugin. Algebra of Invariant Properties of Binary Sequences,Problems Inform. Transmission, 18(2), 1982, 147–161)

    work page 1982

  39. [45]

    О нестохастических объектах, Проблемы передачи информации , 21(2), 1985, 3–9

    В.В.Вьюгин. О нестохастических объектах, Проблемы передачи информации , 21(2), 1985, 3–9. (V.V. V’yugin. On Nonstochastic Objects. Problems Inform. Transmission , 21(2), 1985, 77–83)

    work page 1985

  40. [46]

    О дефекте случайности конечного объекта относительно мер с задан- ными границами их сложности.Теория вероятностей и ее применения , 32(3), 1987, 558–563

    В.В.Вьюгин. О дефекте случайности конечного объекта относительно мер с задан- ными границами их сложности.Теория вероятностей и ее применения , 32(3), 1987, 558–563. (V.V. Vjugin. On Randomness Defect of a Finite Object Relative to Measures with Given Complexity Bounds,Theory Probab. Appl., 32(3), 1987, 508–512)

    work page 1987

  41. [47]

    Сложность конечных объектов и обоснование понятий ин- формации и случайности с помощью теории алгоритмов.Успехи математических наук, 25(6), 1970, 85–127

    А.К.Звонкин, Л.А.Левин. Сложность конечных объектов и обоснование понятий ин- формации и случайности с помощью теории алгоритмов.Успехи математических наук, 25(6), 1970, 85–127. (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.Russian Math. Sur...

    work page 1970

  42. [48]

    Три подхода к определению понятия /guillemotleft.cyrколичество информации/guillemotright.cyr

    А.Н.Колмогоров. Три подхода к определению понятия /guillemotleft.cyrколичество информации/guillemotright.cyr. Проблемы передачи информации, 1(1), 1965, 3–11. (A.N. Kolmogorov. Three approaches to the quantitative definition of information.Problems Inform. Transmission, 1(1), 1965, 1–7)

    work page 1965

  43. [49]

    К логическим основам теории информации и теории вероятностей

    А.Н.Колмогоров. К логическим основам теории информации и теории вероятностей. Проблемы передачи информации , 5(3), 1969, 3–7. (A.N. Kolmogorov. On the logical foundations of information theory and probability theory.Problems Inform. Transmission, 5(3), 1969, 1–4)

    work page 1969

  44. [50]

    Комбинаторные основания теории информации и исчисления ве- роятностей

    А.Н.Колмогоров. Комбинаторные основания теории информации и исчисления ве- роятностей. Успехи математических наук , 38(4), 1983, 27–36. (A.N. Kolmogorov. Combinatorial foundations of information theory and the calculus of probabilities.Russian Math. Surveys, 38(4),1983, 29–40)

    work page 1983

  45. [51]

    О логических основаниях теории вероятностей

    А.Н.Колмогоров. О логических основаниях теории вероятностей. /emdash.cyr В кн.: А.Н.Колмогоров, Теория вероятностей и математическая статистика, М.:Наука, 1986, 467–471. (A.N.Kolmogorov. On logical foundations of probability.Lecture Notes in Mathematics, 1021, 1983, 1–5) 11

    work page 1986

  46. [52]

    Универсальные задачи перебора, Проблемы передачи информации, 9(3), 1973, 115–116

    Л.А.Левин. Универсальные задачи перебора, Проблемы передачи информации, 9(3), 1973, 115–116. (L.A. Levin. Universal Sequential Search Problems, Problems Inform. Transmission, 9(3), 1973, 265–266. For a corrected translation see [36])

    work page 1973

  47. [53]

    О понятии случайной последовательности

    Л.А.Левин. О понятии случайной последовательности. Доклады АН СССР , 212(3), 1973, 548–550. (L.A. Levin. On the Notion of a Random Sequence.Sov. Math. Doklady , 14, 1973, 1413–1416)

    work page 1973

  48. [54]

    Законы сохранения (невозрастания) информации и вопросы обоснования теории информации.Проблемы передачи информации, 10(3), 1974, 30–35

    Л.А.Левин. Законы сохранения (невозрастания) информации и вопросы обоснования теории информации.Проблемы передачи информации, 10(3), 1974, 30–35. (L.A. Levin. Laws of Information Conservation (Nongrowth) and Aspects of the Foundation of Probability Theory.Problems Inform. Transmission, 10(3), 1974, 206–210)

    work page 1974

  49. [55]

    Сигнализирующие вычислимых функций

    Л.А.Левин. Сигнализирующие вычислимых функций. Сложность вычислений и алгоритмов, сборник переводов. Библиотека Кибернетического Сборника, М.:Мир, 1974, 174–185

    work page 1974

  50. [56]

    О принципе сохранения информации в интуиционистской математи- ке

    Л.А.Левин. О принципе сохранения информации в интуиционистской математи- ке. Доклады АН СССР , 227(6), 1976, 1293–1296. (L.A. Levin. On the principle of conservation of information in intuitionistic mathematics.Soviet Math. Doklady, 17, 1976, 601–605)

    work page 1976

  51. [57]

    Доклады АН СССР , 227(4), 1976, 804–807

    Л.А.Левин.Оразличныхмерахсложностиконечныхобъектов(аксиоматическоеопи- сание). Доклады АН СССР , 227(4), 1976, 804–807. (L.A. Levin. Various measures of complexity for finite objects (axiomatic description).Soviet Math. Doklady, 17, 1976, 522– 526)

    work page 1976

  52. [58]

    Равномерные тесты случайности

    Л.А.Левин. Равномерные тесты случайности. Доклады АН СССР , 227(1), 1976, 33– 35.(L.A.Levin.Uniformtestsforrandomness. Soviet Math. Doklady, 17(1),1976,337–340)

    work page 1976

  53. [59]

    Л.А.Левин.Оразличныхмерахсложностиконечныхобъектов(аксиоматическоеопи- сание), Доклады АН СССР , 227(4), 1976, 804–807. (L.A. Levin. Various measures of complexity for finite objects (axiomatic description).Soviet Math. Doklady, 17, 1976, 522– 526)

    work page 1976

  54. [60]

    Об одном конкретном способе задания сложностных мер.Доклады АН СССР, 234(3), 1977, 536–539

    Л.А.Левин. Об одном конкретном способе задания сложностных мер.Доклады АН СССР, 234(3), 1977, 536–539. (L.A. Levin, On a concrete method of assigning complexity measures, Soviet Math. Doklady , 18, 1977, 727–731.)

    work page 1977

  55. [61]

    де Леу, Э.Ф

    К. де Леу, Э.Ф. Мур, К. Шеннон, Н. Шапиро, Вычислимость на вероятностных маши- нах, Автоматы (сб. переводов), М., ИЛ, 1956 (K. de Leeuw, E.F. Moore, C.E. Shannon, N. Shapiro. Computability by Probabilistic Machines. – In: Automata studies , edited by C.E. Shannon and J. McCarthy, Annals of Mathematics Studies , 34, lithoprinted, Princeton University Press...

    work page 1956

  56. [62]

    Может ли (индивидуальная) последова- тельность нулей и единиц быть случайной? Успехи математических наук , 45(1), 1990, 105–162

    В.А.Успенский, А.Л.,Семёнов, А.Х.Шень. Может ли (индивидуальная) последова- тельность нулей и единиц быть случайной? Успехи математических наук , 45(1), 1990, 105–162. (V.A. Uspensky, A.L. Semenov, and A.K. Shen. Can an individual sequence of zeros and ones be random?Russian Math. Surveys , 45(1), 1990, 121–189)

    work page 1990

  57. [63]

    Понятие (α,β)-стохастичности по Колмогорову и его свойства.Доклады АН СССР , 271(6), 1983, 1337–1340

    А.Х.Шень. Понятие (α,β)-стохастичности по Колмогорову и его свойства.Доклады АН СССР , 271(6), 1983, 1337–1340. (A.K. Shen. The concept of Kolmogorov (α,β)- stochasticity and its properties.Soviet Math. Doklady , 28, 1983, 295–299) 12

    work page 1983

  58. [64]

    Bienvenu, A

    L. Bienvenu, A. Shen,Algorithmic information theory and martingales , https://arxiv. org/abs/0906.2614

    work page arXiv

  59. [65]

    G.J. Chaitin. On the length of programs for computing binary sequences,Journal of the Association for Computing Machinery , 13, 1966, 547–569

    work page 1966

  60. [66]

    G.J. Chaitin. On the length of programs for computing binary sequences: Statistical considerations, Journal of the Association for Computing Machinery , 16, 1969, 145–159

    work page 1969

  61. [67]

    G.J. Chaitin. A theory of program size formally identical to information theory,Journal of the Association for Computing Machinery , 22, 1975, 329–340

    work page 1975

  62. [68]

    G.J. Chaitin. Algorithmic information theory,IBM Journal of Research and Development , 21, 1977, 350–359

    work page 1977

  63. [69]

    Cover, P

    T.M. Cover, P. G´ acs, R.M. Gray. Kolmogorov’s contributions to information theory and algorithmic complexity.Annals of Probability, 17(1), 1989, 840–865

    work page 1989

  64. [70]

    L.A. Levin. Some theorems on the algorithmic approach to probability theory and information theory. (1971 Ph.D. thesis, advisor: A.N. Kolmogorov).Annals of Pure and Applied Logic, 162(3), 2010, 224–235

    work page 1971

  65. [71]

    Levin, V.V

    L.A. Levin, V.V. V’yugin. Invariant properties of informational bulks. MFCS 1977: Mathematical Foundations of Computer Science . Lecture Notes on Computer Science , 53, Springer, 1977, 359–364

    work page 1977

  66. [72]

    L.A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control , 61(1), 1984, 15–37

    work page 1984

  67. [73]

    M. Li, P. Vit´ anyi.An Introduction to Kolmogorov Complexity and Its Applications , 3rd ed. New York: Springer–Verlag, 2008

    work page 2008

  68. [74]

    Martin-L¨ of

    P. Martin-L¨ of. The definition of random sequences.Information and Control , 9, 1966, 602–619

    work page 1966

  69. [75]

    Trakhtenbrot

    Boris A. Trakhtenbrot. A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms. Annals of the History of Computing , 6(4), 1984, 384–400

    work page 1984

  70. [76]

    Vereshchagin, P

    N.K. Vereshchagin, P. Vitanyi. Kolmogorov’s Structure Functions and Model Selection. IEEE Transactions on Information Theory , 50(12), 2004, 3265–3289

    work page 2004

  71. [77]

    V.V. V’yugin. Algorithmic complexity and stochastic properties of finite binary sequences. The Computer Journal , 1999, 42(4), 1999, 294–317. 13

    work page 1999