RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription
License agreement
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


Uspekhi Mat. Nauk, 1970, Volume 25, Issue 6(156), Pages 85–127 (Mi umn5428)  

This article is cited in 169 scientific papers (total in 169 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


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.

Full text: PDF file (4898 kB)
References: PDF file   HTML file

English version:
Russian Mathematical Surveys, 1970, 25:6, 83–124

Bibliographic databases:

UDC: 519.24+517.11+519.9
MSC: 68Q30, 94B35
Received: 07.08.1970

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/umn5428}
\mathscinet{http://www.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:
  • http://mi.mathnet.ru/eng/umn5428
  • http://mi.mathnet.ru/eng/umn/v25/i6/p85

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. R.P.. Daley, “Noncomplex sequences: characterizations and examples”, J. symb. log, 41:03 (1976), 626  crossref
    2. Robert Daley, “On the inference of optimal descriptions”, Theoretical Computer Science, 4:3 (1977), 301  crossref
    3. A. A. Brudno, “The complexity of the trajectories of a dynamical system”, Russian Math. Surveys, 33:1 (1978), 197–198  mathnet  crossref  mathscinet  zmath
    4. J.M. Maciejowski, “Model discrimination using an algorithmic information criterion”, Automatica, 15:5 (1979), 579  crossref
    5. Peter Gács, “Exact Expressions for Some Randomness Tests”, Z Math Logik Grundlagen Math, 26:25-27 (1980), 385  crossref  mathscinet  zmath  isi
    6. J. P. Crutchfield, N. H. Packard, “Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise”, Int J Theor Phys, 21:6-7 (1982), 433  crossref  mathscinet  zmath  isi
    7. Charles H. Bennett, “The thermodynamics of computation—a review”, Int J Theor Phys, 21:12 (1982), 905  crossref  isi
    8. A. Muir, M. W. Warner, “The dynamics of symmetric nets”, Bull Math Biol, 45:5 (1983), 781  crossref  mathscinet  zmath  isi
    9. A. N. Kolmogorov, “Combinatorial foundations of information theory and the calculus of probabilities”, Russian Math. Surveys, 38:4 (1983), 29–40  mathnet  crossref  mathscinet  zmath  adsnasa  isi
    10. M. Milgram, H. Atlan, “Probabilistic automata as a model for epigenesis of cellular networks”, Journal of Theoretical Biology, 103:4 (1983), 523  crossref
    11. Péter Gács, “On the relation between descriptional complexity and algorithmic probability”, Theoretical Computer Science, 22:1-2 (1983), 71  crossref
    12. Stuart A. Kurtz, “On the random oracle hypothesis”, Information and Control, 57:1 (1983), 40  crossref
    13. M. A. Jiménez-Montaño, “On the syntactic structure of protein sequences and the concept of grammar complexity”, Bull Math Biol, 46:4 (1984), 641  crossref  mathscinet  zmath  isi
    14. E. A. Asarin, “On convergence of uniform approximations of continuous functions”, Russian Math. Surveys, 39:3 (1984), 179–193  mathnet  crossref  mathscinet  zmath  adsnasa  isi
    15. Edward P. Stabler, “Berwick and Weinberg on linguistics and computational psychology”, Cognition, 17:2 (1984), 155  crossref
    16. Leonid A. Levin, “Randomness conservation inequalities; information and independence in mathematical theories”, Information and Control, 61:1 (1984), 15  crossref
    17. Ker-I Ko, “On the notion of infinite pseudorandom sequences”, Theoretical Computer Science, 48 (1986), 9  crossref
    18. H Atlan, “Self creation of meaning”, Phys Scr, 36:3 (1987), 563  crossref  adsnasa  isi
    19. A. N. Kolmogorov, V. A. Uspenskii, “Algorithms and Randomness”, Theory Probab Appl, 32:3 (1987), 389  mathnet  crossref  mathscinet  zmath  isi
    20. Kristian Lindgren, “Microscopic and macroscopic entropy”, Phys Rev A, 38:9 (1988), 4794  crossref  isi
    21. P. Vitani, M. Li, “Kolmogorovskaya slozhnost: dvadtsat let spustya”, UMN, 43:6(264) (1988), 129–166  mathnet  mathscinet  zmath
    22. J. Higgins, “Embedding recursive functions in universal algorithms”, International Journal of Computer Mathematics, 24:3-4 (1988), 273  crossref
    23. Karl Svozil, “Comment on ‘`Comment on `Quantum cosmology and the initial state of the universe’ "”, Phys Rev D, 41:4 (1990), 1353  crossref  isi
    24. V. A. Uspenskii, A. L. Semenov, A. Kh. Shen', “Can an individual sequence of zeros and ones be random?”, Russian Math. Surveys, 45:1 (1990), 121–189  mathnet  crossref  mathscinet  zmath  adsnasa  isi
    25. Karl Svozil, “Constructive chaos by cellular automata and possible sources of an arrow of time”, Physica D: Nonlinear Phenomena, 45:1-3 (1990), 420  crossref
    26. Ramamohan Paturi, Joel I. Seiferas, Janos Simon, Richard E. Newman-Wolfe, “Milking the Aanderaa argument”, Information and Computation, 88:1 (1990), 88  crossref
    27. P R Baldwin, J Phys A Math Gen, 24:16 (1991), L941  crossref  mathscinet  zmath  adsnasa  isi
    28. Moshe Koppel, Henri Atlan, “An almost machine-independent theory of program-length complexity, sophistication, and induction”, Information Sciences, 56:1-3 (1991), 23  crossref
    29. Yuri Gurevich, “Average case completeness”, Journal of Computer and System Sciences, 42:3 (1991), 346  crossref
    30. P.E. Rapp, M.A. Jiménez-Montano, R.J. Langs, L. Thomson, A.I. Mees, “Toward a quantitative characterization of patient-therapist communication”, Mathematical Biosciences, 105:2 (1991), 207  crossref
    31. Y Yomdin, “Complexity of functions: Some questions, conjectures, and results”, Journal of Complexity, 7:1 (1991), 70  crossref
    32. Luigi Burigana, “Organization by rules in finite sequences”, Journal of Mathematical Psychology, 35:3 (1991), 345  crossref
    33. Dung T. Huyn, “Effective entropies and data compression”, Information and Computation, 90:1 (1991), 67  crossref
    34. Ming Li, Paul Vitányi, SIAM J. Comput, 20:5 (1991), 911  crossref
    35. Ming Li, Paul M.B. Vitányi, “Inductive reasoning and kolmogorov complexity”, Journal of Computer and System Sciences, 44:2 (1992), 343  crossref
    36. Ming Li, Paul M.B. Vitányi, “Average case complexity under the universal distribution equals worst-case complexity”, Information Processing Letters, 42:3 (1992), 145  crossref
    37. A. Nabutovsky, R. Ben-Av, “Noncomputability arising in dynamical triangulation model of four-dimensional Quantum Gravity”, Comm Math Phys, 157:1 (1993), 93  crossref  mathscinet  zmath  adsnasa  isi
    38. Peter Bro Miltersen, “The Complexity of Malign Measures”, SIAM J Comput, 22:1 (1993), 147  crossref  mathscinet  zmath  adsnasa  isi
    39. Homer S. White, “Algorithmic complexity of points in dynamical systems”, Ergod Th Dynam Sys, 13:4 (1993)  crossref  mathscinet  zmath
    40. Pierre Gaspard, Xiao-Jing Wang, “Noise, chaos, and (ε, τ)-entropy per unit time”, Physics Reports, 235:6 (1993), 291  crossref
    41. Manuel Martinez-Morales, B.S. Duran, “A test for randomness based on a complexity measure”, Communications in Statistics - Theory and Methods, 22:3 (1993), 879  crossref
    42. Luc Longpré, Sarah Mocas, “Symmetry of information and one-way functions”, Information Processing Letters, 46:2 (1993), 95  crossref
    43. B. Schapiro, “An approach to the physics of complexity”, Chaos, Solitons & Fractals, 4:1 (1994), 115  crossref
    44. David W. Juedes, James I. Lathrop, Jack H. Lutz, “Computational depth and reducibility”, Theoretical Computer Science, 132:1-2 (1994), 37  crossref
    45. Charles H. Bennett, “Universal computation and physical dynamics”, Physica D: Nonlinear Phenomena, 86:1-2 (1995), 268  crossref
    46. J.C. Kieffer, En-hui Yang, “Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity”, IEEE Trans Inform Theory, 42:1 (1996), 29  crossref  mathscinet  zmath  isi
    47. A. Nabutovsky, “Geometry of the space of triangulations of a compact manifold”, Comm Math Phys, 181:2 (1996), 303  crossref  mathscinet  zmath  adsnasa  isi
    48. V. A. Uspensky, A. Shen, “Relations between varieties of kolmogorov complexities”, Math Systems Theory, 29:3 (1996), 271  crossref  mathscinet  zmath  isi  elib
    49. En-hui Yang, Zhen Zhang, T. Berger, “Fixed-slope universal lossy data compression”, IEEE Trans Inform Theory, 43:5 (1997), 1465  crossref  mathscinet  isi
    50. Jürgen Schmidhuber, “Discovering Neural Nets with Low Kolmogorov Complexity and High Generalization Capability”, Neural Networks, 10:5 (1997), 857  crossref  elib
    51. C.H. Bennett, P. Gacs, Ming Li, M.B. Vitanyi, W.H. Zurek, “Information distance”, IEEE Trans Inform Theory, 44:4 (1998), 1407  crossref  mathscinet  zmath  isi
    52. An.A. Muchnik, “On common information”, Theoretical Computer Science, 207:2 (1998), 319  crossref
    53. V.V. V'yugin, “Ergodic theorems for individual random sequences”, Theoretical Computer Science, 207:2 (1998), 343  crossref
    54. V.V. V'yugin, “Non-stochastic infinite and finite sequences”, Theoretical Computer Science, 207:2 (1998), 363  crossref
    55. Andrei A. Muchnik, Alexei L. Semenov, Vladimir A. Uspensky, “Mathematical metaphysics of randomness”, Theoretical Computer Science, 207:2 (1998), 263  crossref
    56. J Lathrop, “Recursive Computational Depth”, Information and Computation, 153:2 (1999), 139  crossref
    57. P.M.B. Vitanyi, Ming Li, “Minimum description length induction, Bayesianism, and Kolmogorov complexity”, IEEE Trans Inform Theory, 46:2 (2000), 446  crossref  mathscinet  zmath  isi
    58. A. E. Romashchenko, “Pairs of Words with Nonmaterializable Mutual Information”, Problems Inform. Transmission, 36:1 (2000), 1–18  mathnet  mathscinet  zmath
    59. C. Adami, N.J. Cerf, “Physical complexity of symbolic sequences”, Physica D: Nonlinear Phenomena, 137:1-2 (2000), 62  crossref
    60. Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai Vereshchagin, “Inequalities for Shannon Entropy and Kolmogorov Complexity”, Journal of Computer and System Sciences, 60:2 (2000), 442  crossref
    61. Marcus Hutter, “New Error Bounds for Solomonoff Prediction”, Journal of Computer and System Sciences, 62:4 (2001), 653  crossref
    62. V.V V'yugin, “Most Sequences Are Stochastic”, Information and Computation, 169:2 (2001), 252  crossref
    63. A. Yu. Khrennikov, “Interpretations of Probability and Their p-Adic Extensions”, Theory Probab Appl, 46:2 (2002), 256  mathnet  crossref  mathscinet  isi
    64. V.V. V'yugin, “Suboptimal Measures of Predictive Complexity for Absolute Loss Function”, Information and Computation, 175:2 (2002), 146  crossref
    65. Michael V Vyugin, Vladimir V V'yugin, “On Complexity of Easy Predictable Sequences”, Information and Computation, 178:1 (2002), 241  crossref
    66. Yuri Kalnishkan, “General linear relations between different types of predictive complexity”, Theoretical Computer Science, 271:1-2 (2002), 181  crossref
    67. Bruno Durand, Alexander Shen, Nikolai Vereshchagin, “Descriptive complexity of computable sequences”, Theoretical Computer Science, 271:1-2 (2002), 47  crossref
    68. Nikolai K. Vereshchagin, “Kolmogorov complexity conditional to large integers”, Theoretical Computer Science, 271:1-2 (2002), 59  crossref
    69. Bruno Durand, Sylvain Porrot, “Comparison between the complexity of a function and the complexity of its graph”, Theoretical Computer Science, 271:1-2 (2002), 37  crossref
    70. MARCUS HUTTER, “THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS”, Int. J. Found. Comput. Sci, 13:03 (2002), 431  crossref
    71. Ludwig Staiger, “The Kolmogorov complexity of real numbers”, Theoretical Computer Science, 284:2 (2002), 455  crossref
    72. Marcus Hutter, “Optimality of Universal Bayesian Sequence Prediction for General Loss and Alphabet”, J Machine Learning Res, 4:6 (2003), 971  crossref  mathscinet  isi
    73. D.M. Sow, A. Eleftheriadis, “Complexity distortion theory”, IEEE Trans Inform Theory, 49:3 (2003), 604  crossref  mathscinet  zmath  isi  elib
    74. V. V. V'yugin, “Problems of Robustness for Universal Coding Schemes”, Problems Inform. Transmission, 39:1 (2003), 32–46  mathnet  crossref  mathscinet  zmath
    75. L. A. Levin, “One-Way Functions”, Problems Inform. Transmission, 39:1 (2003), 92–103  mathnet  crossref  mathscinet  zmath
    76. A. E. Romashchenko, “A Criterion of Extractability of the Mutual Information for a Triple of Strings”, Problems Inform. Transmission, 39:1 (2003), 148–157  mathnet  crossref  mathscinet  zmath
    77. Peter Hertling, Klaus Weihrauch, “Random elements in effective topological spaces with measure”, Information and Computation, 181:1 (2003), 32  crossref
    78. Jack H. Lutz, “The dimensions of individual strings and sequences”, Information and Computation, 187:1 (2003), 49  crossref
    79. Hayato Takahashi, Kazuyuki Aihara, “Algorithmic analysis of irrational rotations in a single neuron model”, Journal of Complexity, 19:2 (2003), 132  crossref
    80. John M. Hitchcock, “Gales suffice for constructive dimension”, Information Processing Letters, 86:1 (2003), 9  crossref
    81. H. Takahashi, “Redundancy of Universal Coding, Kolmogorov Complexity, and Hausdorff Dimension”, IEEE Trans Inform Theory, 50:11 (2004), 2727  crossref  mathscinet  isi  elib
    82. A. Yu. Khrennikov, Sh. Yamada, “On the concept of random sequence with respect to $p$-adic valued probabilities”, Theory Probab. Appl., 49:1 (2005), 65–76  mathnet  crossref  crossref  mathscinet  zmath  isi
    83. Rod G. Downey, Denis R. Hirschfeldt, Geoff LaForte, “Randomness and reducibility”, Journal of Computer and System Sciences, 68:1 (2004), 96  crossref
    84. Mark Burgin, “Algorithmic complexity of recursive and inductive algorithms”, Theoretical Computer Science, 317:1-3 (2004), 31  crossref
    85. Jan Poland, “A coding theorem for Enumerable Output Machines”, Information Processing Letters, 91:4 (2004), 157  crossref
    86. Liang Yu, Decheng Ding, Rodney Downey, “The Kolmogorov complexity of random reals”, Annals of Pure and Applied Logic, 129:1-3 (2004), 163  crossref
    87. Lowe B., Piwinger B., Rasch T., “Classical and New Paradigms of Computation and their Complexity Hierarchies - Papers of the Conference “Foundations of the Formal Sciences III{””, Classical and New Paradigms of Computation and their Complexity Hierarchies, Trends in Logic Studia Logica Library, 23, eds. Lowe B., Piwinger B., Rasch T., Springer, 2004, VII+  isi
    88. J. Poland, M. Hutter, “Asymptotics of Discrete MDL for Online Prediction”, IEEE Trans Inform Theory, 51:11 (2005), 3780  crossref  mathscinet  isi
    89. Jack H. Lutz, “Effective fractal dimensions”, MLQ - Math Log Quart, 51:1 (2005), 62  crossref  mathscinet  zmath  isi
    90. B. Ya. Ryabko, V. A. Monarev, “Experimental Investigation of Forecasting Methods Based on Data Compression Algorithms”, Problems Inform. Transmission, 41:1 (2005), 65–69  mathnet  crossref  zmath  elib
    91. Michael V. Vyugin, Vladimir V. V’yugin, “Predictive complexity and information”, Journal of Computer and System Sciences, 70:4 (2005), 539  crossref
    92. Yuri Kalnishkan, Vladimir Vovk, Michael V. Vyugin, “How many strings are easy to predict?”, Information and Computation, 201:1 (2005), 55  crossref
    93. Troy Lee, Andrei Romashchenko, “Resource bounded symmetry of information revisited”, Theoretical Computer Science, 345:2-3 (2005), 386  crossref
    94. Peter Gács, “Uniform test of algorithmic randomness over a general space”, Theoretical Computer Science, 341:1-3 (2005), 91  crossref
    95. Ludwig Staiger, “Constructive dimension equals Kolmogorov complexity”, Information Processing Letters, 93:3 (2005), 149  crossref
    96. Fabio Benatti, Tyll Krüger, Markus Müller, Rainer Siegmund-Schultze, Arleta Szkoła, “Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno’s Theorem”, Comm Math Phys, 265:2 (2006), 437  crossref  mathscinet  zmath  isi
    97. Kohtaro Tadaki, “An extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system”, MLQ - Math Log Quart, 52:5 (2006), 419  crossref  mathscinet  zmath  isi
    98. Sean Devine, “The application of algorithmic information theory to noisy patterned strings”, Complexity, 12:2 (2006), 52  crossref  mathscinet  isi
    99. Jan Poland, Marcus Hutter, “MDL convergence speed for Bernoulli sequences”, Stat Comput, 16:2 (2006), 161  crossref  mathscinet  isi
    100. Marcus Hutter, “Sequential predictions based on algorithmic complexity”, Journal of Computer and System Sciences, 72:1 (2006), 95  crossref
    101. Marcus Hutter, “On generalized computable universal priors and their convergence”, Theoretical Computer Science, 364:1 (2006), 27  crossref
    102. Andrej Muchnik, Alexei Semenov, “Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets”, Annals of Pure and Applied Logic, 141:3 (2006), 437  crossref
    103. Rod Downey, D.R.. Hirschfeldt, André Nies, S.A.. Terwijn, “Calibrating Randomness”, Bull. symb. log, 12:03 (2006), 411  crossref
    104. Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, “Enumerations of the Kolmogorov function”, J. symb. log, 71:02 (2006), 501  crossref
    105. David Doty, “Dimension Extractors and Optimal Decompression”, Theory Comput Systems, 2007  crossref  mathscinet  isi
    106. John M. Hitchcock, María López-Valdés, Elvira Mayordomo, “Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets”, Theory Comput Systems, 2007  crossref  isi
    107. Khushboo Shah, Edmond Jonckheere, Stephan Bohacek, “Dynamic Modeling of Internet Traffic for Intrusion Detection”, EURASIP J Adv Signal Process, 2007 (2007), 1  crossref  isi
    108. Sheng-Tzong Cheng, Ming-Hung Tao, “Quantum cooperative search algorithm for 3-SAT”, Journal of Computer and System Sciences, 73:1 (2007), 123  crossref
    109. Nick Chater, Paul Vitányi, “‘Ideal learning’ of natural language: Positive results about learning from positive evidence”, Journal of Mathematical Psychology, 51:3 (2007), 135  crossref
    110. Alexey Chernov, Marcus Hutter, Jürgen Schmidhuber, “Algorithmic complexity bounds on future prediction errors”, Information and Computation, 205:2 (2007), 242  crossref
    111. Marcus Hutter, Andrej Muchnik, “On semimeasures predicting Martin-Löf random sequences”, Theoretical Computer Science, 382:3 (2007), 247  crossref
    112. Marcus Hutter, “On universal prediction and Bayesian confirmation”, Theoretical Computer Science, 384:1 (2007), 33  crossref
    113. Ludwig Staiger, “The Kolmogorov complexity of infinite words”, Theoretical Computer Science, 383:2-3 (2007), 187  crossref
    114. Michael G. Sadovsky, Julia A. Putintseva, Alexander S. Shchepanovsky, “Genes, information and sense: complexity and knowledge retrieval”, Theory Biosci, 127:2 (2008), 69  crossref  mathscinet  isi  elib
    115. J. Math. Sci. (N. Y.), 158:6 (2009), 787–808  mathnet  crossref  elib
    116. Daniil Ryabko, Marcus Hutter, “Predicting non-stationary processes”, Applied Mathematics Letters, 21:5 (2008), 477  crossref
    117. Hayato Takahashi, “On a definition of random sequences with respect to conditional probability”, Information and Computation, 206:12 (2008), 1375  crossref
    118. Jöran Mielke, “Refined Bounds on Kolmogorov Complexity for ω-Languages”, Electronic Notes in Theoretical Computer Science, 221 (2008), 181  crossref
    119. Ludwig Staiger, “On Oscillation-free ε-random Sequences”, Electronic Notes in Theoretical Computer Science, 221 (2008), 287  crossref
    120. CRISTIAN S. CALUDE, LUDWIG STAIGER, “On universal computably enumerable prefix codes”, Math Struct Comp Sci, 19:1 (2009), 45  crossref  mathscinet  zmath  isi
    121. Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, “Limit Complexities Revisited”, Theory Comput Systems, 2009  crossref
    122. A. Yu. Kolesov, N. Kh. Rozov, “On the definition of ‘chaos’”, Russian Math. Surveys, 64:4 (2009), 701–744  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    123. Laurent Bienvenu, “Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity”, Theory Comput Systems, 2009  crossref  isi
    124. Mathieu Hoyrup, Cristóbal Rojas, “Computability of probability measures and Martin-Löf randomness over metric spaces”, Information and Computation, 207:7 (2009), 830  crossref
    125. Vladimir V. V’yugin, “On calibration error of randomized forecasting algorithms”, Theoretical Computer Science, 410:19 (2009), 1781  crossref
    126. M.M. Hassan Mahmud, “On universal transfer learning”, Theoretical Computer Science, 410:19 (2009), 1826  crossref
    127. Fabio Benatti, “Quantum Algorithmic Complexities and Entropy”, Open Syst. Inf. Dyn, 16:01 (2009), 1  crossref
    128. D.L.. Abel, “The Capabilities of Chaos and Complexity”, IJMS, 10:1 (2009), 247  crossref
    129. An. A. Muchnik, A. E. Romashchenko, “Stability of properties of Kolmogorov complexity under relativization”, Problems Inform. Transmission, 46:1 (2010), 38–61  mathnet  crossref  mathscinet  isi  elib
    130. Matilde Marcolli, Yuri I. Manin, “Error-Correcting Codes and Phase Transitions”, Math comput sci, 2010  crossref
    131. Peter Gács, Mathieu Hoyrup, Cristóbal Rojas, “Randomness on Computable Probability Spaces—A Dynamical Point of View”, Theory Comput Systems, 2010  crossref
    132. Jürgen Schmidhuber, “The new AI is general and mathematically rigorous”, Front Electr Electron Eng China, 2010  crossref
    133. Vladimir V’yugin, “On Empirical Meaning of Randomness with Respect to Parametric Families of Probability Distributions”, Theory Comput Systems, 2010  crossref
    134. Cristian S. Calude, Marius Zimand, “Algorithmically independent sequences”, Information and Computation, 208:3 (2010), 292  crossref
    135. Markus Müller, “Stationary algorithmic probability”, Theoretical Computer Science, 411:1 (2010), 113  crossref
    136. K. Vela Velupillai, “NON-LINEAR DYNAMICS, COMPLEXITY AND RANDOMNESS: ALGORITHMIC FOUNDATIONS”, Journal of Economic Surveys, 2011, no  crossref
    137. V. V. V'yugin, “On universal algorithms for adaptive forecasting”, Problems Inform. Transmission, 47:2 (2011), 166–189  mathnet  crossref  mathscinet  isi
    138. Gerard Briscoe, Philippe De Wilde, “Physical complexity of variable length symbolic sequences”, Physica A: Statistical Mechanics and its Applications, 2011  crossref
    139. Paul E Rapp, Christopher J Cellucci, Adele MK Gilpin, Miguel A Jiménez-Montaño, Kathryn E Korslund, “Communication patterns in a psychotherapy following traumatic brain injury: A quantitative case study based on symbolic dynamics”, BMC Psychiatry, 11:1 (2011), 119  crossref
    140. Kohtaro Tadaki, “A Chaitin
      $$\Upomega$$
      number based on compressible strings”, Nat Comput, 2011  crossref
    141. Joseph S. Miller, Liang Yu, “Oscillation in the initial segment complexity of random reals”, Advances in Mathematics, 226:6 (2011), 4816  crossref
    142. Nikolay K. Vereshchagin, Andrej A. Muchnik, “On joint conditional complexity (entropy)”, Proc. Steklov Inst. Math., 274 (2011), 90–104  mathnet  crossref  mathscinet  isi  elib  elib
    143. Laurent Bienvenu, Peter Gács, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen, “Algorithmic tests and randomness with respect to a class of measures”, Proc. Steklov Inst. Math., 274 (2011), 34–89  mathnet  crossref  mathscinet  isi  elib  elib
    144. James P. Crutchfield, “Between order and chaos”, Nat Phys, 8:1 (2011), 17  crossref
    145. M. Zimand, “Generating Kolmogorov random strings from sources with limited independence”, Journal of Logic and Computation, 2011  crossref
    146. Sebastiaan A. Terwijn, Leen Torenvliet, Paul M.B. Vitányi, “Nonapproximability of the normalized information distance”, Journal of Computer and System Sciences, 77:4 (2011), 738  crossref
    147. Uspensky V.A., V'yugin V.V., “Development of the algorithmic information theory in Russia”, Journal of Communications Technology and Electronics, 56:6 (2011), 739–747  crossref  isi
    148. Gidlevskii A.V., “Paradoksy entropii (spekulyativnyi kharakter sovremennoi nauchnoi metodologii)”, Vestnik omskogo universiteta, 2011, no. 4, 199–201  elib
    149. Verónica Becher, Pablo Ariel Heiber, “A linearly computable measure of string complexity”, Theoretical Computer Science, 2012  crossref
    150. Boris Ryabko, Zhanna Reznikova, Alexey Druzyaka, Sofia Panteleeva, “Using Ideas of Kolmogorov Complexity for Studying Biological Texts”, Theory Comput Syst, 2012  crossref
    151. Adam R. Day, “Process and truth-table characterisations of randomness”, Theoretical Computer Science, 2012  crossref
    152. Luís Antunes, Armando Matos, Alexandre Pinto, André Souto, Andreia Teixeira, “One-Way Functions Using Algorithmic and Classical Information Theories”, Theory Comput Syst, 2012  crossref
    153. EIJI KONISHI, “MODELING QUANTUM MECHANICAL OBSERVERS VIA NEURAL-GLIAL NETWORKS”, Int. J. Mod. Phys. B, 26:09 (2012), 1250060  crossref
    154. Frank Stephan, Jason Teutsch, “An incomplete set of shortest descriptions”, J. symb. log, 77:01 (2012), 291  crossref
    155. José Hernández-Orallo, David L. Dowe, “On Potential Cognitive Abilities in the Machine Kingdom”, Minds & Machines, 2013  crossref
    156. Sergio Romano, Mariano Sigman, Santiago Figueira, “$LT^2C^2$ : A language of thought with Turing-computable Kolmogorov complexity”, Pap. Phys, 5 (2013)  crossref
    157. Dusko Pavlovic, “Monoidal computer I: Basic computability by string diagrams”, Information and Computation, 2013  crossref
    158. EIJI KONISHI, “TIME AND A TEMPORALLY STATISTICAL QUANTUM GEOMETRODYNAMICS”, Int. J. Mod. Phys. A, 2013, 1330015  crossref
    159. P.M..B. Vitányi, “Conditional Kolmogorov complexity and universal probability”, Theoretical Computer Science, 2013  crossref
    160. Nicolas Gauvrit, Hector Zenil, Jean-Paul Delahaye, Fernando Soler-Toscano, “Algorithmic complexity for short binary strings applied to psychology: a primer”, Behav Res, 2013  crossref
    161. Frank Stephan, Jason Teutsch, “Things that can be made into themselves”, Information and Computation, 2014  crossref
    162. Kenshi Miyabe, “Algorithmic randomness over general spaces”, Math. Log. Quart, 60:3 (2014), 184  crossref
    163. Jason Teutsch, “Short lists for shortest descriptions in short time”, comput. complex, 2014  crossref
    164. Yu. I. Manin, “Zipf's Law and L. Levin Probability Distributions”, Funct. Anal. Appl., 48:2 (2014), 116–127  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    165. Tor Lattimore, Marcus Hutter, “On Martin-Löf (non-)convergence of Solomonoff's universal mixture”, Theoretical Computer Science, 2014  crossref
    166. Manin Y.I., “Complexity Vs Energy: Theory of Computation and Theoretical Physics”, 3Quantum: Algebra Geometry Information, Journal of Physics Conference Series, 532, IOP Publishing Ltd, 2014, 012018  crossref  isi
    167. Manin Yu., Marcolli M., “Kolmogorov Complexity and the Asymptotic Bound For Error-Correcting Codes”, J. Differ. Geom., 97:1 (2014), 91–108  isi
    168. Mikhail Andreev, Akim Kumok, “The Sum 2 KM(x)−K(x) Over All Prefixes x of Some Binary Sequence Can be Infinite”, Theory Comput Syst, 2015  crossref
    169. J. Math. Sci. (N. Y.), 226:5 (2017), 667–693  mathnet  crossref  mathscinet
  • Успехи математических наук Russian Mathematical Surveys
    Number of views:
    This page:2044
    Full text:578
    References:67
    First page:2

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019