RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УМН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


УМН, 1970, том 25, выпуск 6(156), страницы 85–127 (Mi umn5428)  

Эта публикация цитируется в 169 научных статьях (всего в 169 статьях)

Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов

А. К. Звонкин, Л. А. Левин


Аннотация: В 1964 г. А. Н. Колмогоров ввел понятие сложности конечного объекта (например, слова в некотором алфавите). Сложность он определял как минимальное число двоичных знаков, содержащих всю информацию о задаваемом объекте, достаточную для его восстановления (декодирования). Это определение существенно зависит от метода декодирования, однако с помощью общей теории алгоритмов А. Н. Колмогорову удалось дать инвариантное (универсальное) определение сложности. Близкие понятия рассматривались Р. Дж. Соломоновым (США) и А. А. Марковым. На базе понятия сложности А. Н. Колмогоров дал определение количества информации в конечных объектах и понятия случайной последовательности (уточненное потом в работах П. Мартин-Лёфа). Впоследствии этот круг вопросов быстро развивался. В частности, интересное развитие получили идеи А. А. Маркова о применении понятия сложности для изучения количественных вопросов теории алгоритмов. Настоящая статья представляет собой обзор основных результатов, связанных со всем изложенным.

Полный текст: PDF файл (4898 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Russian Mathematical Surveys, 1970, 25:6, 83–124

Реферативные базы данных:

УДК: 519.24+517.11+519.9
MSC: 68Q30, 94B35
Поступила в редакцию: 07.08.1970

Образец цитирования: А. К. Звонкин, Л. А. Левин, “Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов”, УМН, 25:6(156) (1970), 85–127; Russian Math. Surveys, 25:6 (1970), 83–124

Цитирование в формате AMSBIB
\RBibitem{ZvoLev70}
\by А.~К.~Звонкин, Л.~А.~Левин
\paper Сложность конечных объектов и~обоснование понятий информации и~случайности с~помощью теории алгоритмов
\jour УМН
\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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/umn5428
  • http://mi.mathnet.ru/rus/umn/v25/i6/p85

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    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. А. А. Брудно, “О сложности траектории динамической системы”, УМН, 33:1(199) (1978), 207–208  mathnet  mathscinet  zmath; A. A. Brudno, “The complexity of the trajectories of a dynamical system”, Russian Math. Surveys, 33:1 (1978), 197–198  crossref
    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. А. Н. Колмогоров, “Комбинаторные основания теории информации и исчисления вероятностей”, УМН, 38:4(232) (1983), 27–36  mathnet  mathscinet  zmath  adsnasa; A. N. Kolmogorov, “Combinatorial foundations of information theory and the calculus of probabilities”, Russian Math. Surveys, 38:4 (1983), 29–40  crossref  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. Е. А. Асарин, “О сложности равномерных приближений непрерывных функций”, УМН, 39:3(237) (1984), 157–169  mathnet  mathscinet  zmath  adsnasa; E. A. Asarin, “On convergence of uniform approximations of continuous functions”, Russian Math. Surveys, 39:3 (1984), 179–193  crossref  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. П. Витаньи, М. Ли, “Колмогоровская сложность: двадцать лет спустя”, УМН, 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. В. А. Успенский, А. Л. Семёнов, А. Х. Шень, “Может ли (индивидуальная) последовательность нулей и единиц быть случайной?”, УМН, 45:1(271) (1990), 105–162  mathnet  mathscinet  zmath  adsnasa; 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  crossref  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. А. Е. Ромащенко, “Пары слов с нематериализуемой взаимной информацией”, Пробл. передачи информ., 36:1 (2000), 3–20  mathnet  mathscinet  zmath; A. E. Romashchenko, “Pairs of Words with Nonmaterializable Mutual Information”, Problems Inform. Transmission, 36:1 (2000), 1–18
    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. В. В. Вьюгин, “Проблемы устойчивости универсальных схем сжатия информации”, Пробл. передачи информ., 39:1 (2003), 36–52  mathnet  mathscinet  zmath; V. V. V'yugin, “Problems of Robustness for Universal Coding Schemes”, Problems Inform. Transmission, 39:1 (2003), 32–46  crossref
    75. Л. А. Левин, “Односторонние функции”, Пробл. передачи информ., 39:1 (2003), 103–117  mathnet  mathscinet  zmath; L. A. Levin, “One-Way Functions”, Problems Inform. Transmission, 39:1 (2003), 92–103  crossref
    76. А. Е. Ромащенко, “Критерий выделяемости взаимной информации для тройки слов”, Пробл. передачи информ., 39:1 (2003), 166–175  mathnet  mathscinet  zmath; A. E. Romashchenko, “A Criterion of Extractability of the Mutual Information for a Triple of Strings”, Problems Inform. Transmission, 39:1 (2003), 148–157  crossref
    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. А. Ю. Хренников, Ш. Яамада, “О концепции случайной последовательности относительно $p$-адических вероятностей”, Теория вероятн. и ее примен., 49:1 (2004), 54–69  mathnet  crossref  mathscinet  zmath; 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  crossref  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. Б. Я. Рябко, В. А. Монарев, “Экспериментальное исследование методов прогнозирования, базирующихся на алгоритмах сжатия данных”, Пробл. передачи информ., 41:1 (2005), 74–78  mathnet  zmath; B. Ya. Ryabko, V. A. Monarev, “Experimental Investigation of Forecasting Methods Based on Data Compression Algorithms”, Problems Inform. Transmission, 41:1 (2005), 65–69  crossref  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. S. Vakulenko, D. Grigoriev, “Instability, complexity, and evolution”, Теория представлений, динамические системы, комбинаторные методы. XVI, Зап. научн. сем. ПОМИ, 360, ПОМИ, СПб., 2008, 31–69  mathnet  elib; J. Math. Sci. (N. Y.), 158:6 (2009), 787–808  crossref
    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. А. Ю. Колесов, Н. Х. Розов, “К вопросу об определении хаоса”, УМН, 64:4(388) (2009), 125–172  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. Yu. Kolesov, N. Kh. Rozov, “On the definition of ‘chaos’”, Russian Math. Surveys, 64:4 (2009), 701–744  crossref  isi  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. Ан. А. Мучник, А. Е. Ромащенко, “Устойчивость колмогоровских свойств при релятивизации”, Пробл. передачи информ., 46:1 (2010), 42–67  mathnet  mathscinet; An. A. Muchnik, A. E. Romashchenko, “Stability of properties of Kolmogorov complexity under relativization”, Problems Inform. Transmission, 46:1 (2010), 38–61  crossref  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. В. В. Вьюгин, “Об универсальных алгоритмах адаптивного прогнозирования”, Пробл. передачи информ., 47:2 (2011), 90–116  mathnet  mathscinet; V. V. V'yugin, “On universal algorithms for adaptive forecasting”, Problems Inform. Transmission, 47:2 (2011), 166–189  crossref  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. Н. К. Верещагин, Ан. А. Мучник, “О совместной условной сложности (энтропии)”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 103–118  mathnet  mathscinet  elib; Nikolay K. Vereshchagin, Andrej A. Muchnik, “On joint conditional complexity (entropy)”, Proc. Steklov Inst. Math., 274 (2011), 90–104  crossref  isi  elib
    143. Л. Биенвеню, П. Гач, М. Хойруп, К. Рохас, А. Шень, “Алгоритмические тесты и случайность относительно классов мер”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 41–102  mathnet  mathscinet  elib; 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  crossref  isi  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. Гидлевский А.В., “Парадоксы энтропии (спекулятивный характер современной научной методологии)”, Вестник омского университета, 2011, № 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. Ю. И. Манин, “Закон Ципфа и вероятностные распределения Левина”, Функц. анализ и его прил., 48:2 (2014), 51–66  mathnet  crossref  mathscinet  zmath  elib; Yu. I. Manin, “Zipf's Law and L. Levin Probability Distributions”, Funct. Anal. Appl., 48:2 (2014), 116–127  crossref  isi
    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. G. Shabat, “Calculating and drawing Belyi pairs”, Комбинаторика и теория графов. V, Зап. научн. сем. ПОМИ, 446, ПОМИ, СПб., 2016, 182–220  mathnet  mathscinet; J. Math. Sci. (N. Y.), 226:5 (2017), 667–693  crossref
  • Успехи математических наук Russian Mathematical Surveys
    Просмотров:
    Эта страница:2034
    Полный текст:578
    Литература:67
    Первая стр.:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019