## Алгоритмическая теория информации

Странным образом Успенский, будучи учеником Колмогорова и работая рядом с ним на мехмате МГУ, был в 1960-е годы в стороне от исследований Колмогорова, связанных с определением понятия сложности конечного объекта. По его словам, он впервые вплотную занялся этой областью, готовя доклад (с А. Л. Семёновым) на конференции в Ургенче [24, 26]. В этом докладе была предложен подход к классификации различных видов сложности (или, как предпочитал говорить Успенский, «энтропии») для конечных объектов, определённых к тому времени (простая, префиксная, условная, монотонная энтропии, а также энтропия разрешения). Изначально (см. [107]) этот подход был предложен в терминах $f_0$-пространств и операций над ними, что можно рассматривать как развитие подхода Успенского к определению вычислимых отображений как частного случая непрерывных. Однако для целей классификации различных видов колмогоровской сложности можно было обойтись и без $f_0$-пространств, и Успенский с Семёновым в [24, 26] предложили более простой вариант определения (в терминах отношения согласованности на описаниях и объектах), достаточный для целей классификации. Впоследствии это упрощённое описание было изложено в [38, 40]; подробное изложение с топологической точки зрения (но без $f_0$-пространств) можно найти в [59].

Алгоритмической теории информации (точнее, различным определениям понятия случайности) посвящён также обзор [35] и монография [59]. Популярная лекция (для студентов-младшекурсников), посвящённая различным определениям случайности, была прочитана Успенским на летней школе «Современная математика» в Дубне в 2005 году, и материалы этой лекции были изданы [50] и вошли в качестве приложения в монографию [59].

До сих пор остаётся открытым вопрос, поставленный Успенским, Семёновым и Мучником в [43] о том, совпадают ли понятия случайности по Мартин-Лёфу и «непредсказуемости» (отсутствия выигрышной вычислимой стратегии в немонотонных играх, см. подробнее в [50, 59]).

## Популяризация

Есть разные представления о том, что такое «популяризация науки» (по-французски это называют vulgarisation, что для русского уха звучит обидно, хотя и не совсем незаслуженно). Можно рассказывать байки о трудной судьбе или особенностях личной жизни выдающихся учёных. Можно пересказывать недавно прочитанное в другой популярной книге, добавляя «оживляж». Видимо, это полезное дело — но Успенский всю жизнь занимался другим, пытаясь честно объяснить «суть дела». При этом сложность темы, естественно, зависела от того, на кого рассчитано объяснение, но всегда это было настоящее объяснение того, что объяснить можно, с отчётливым указанием, что именно оставлено без доказательства или уточнения. При этом он не боялся объяснить очевидное, помня, что известное известно немногим («Что мы знаем о лисе? Ничего, и то не все» — писал сосед Колмогорова по даче, знаменитый детский писатель Борис Заходер.)

Ещё будучи студентом, Успенский (вместе со старшим соавтором, Евгением Борисовичем Дынкиным) написал книгу «Математические беседы» [5] по материалам математических кружков, где он сначала был участником, а потом руководителем. В ней несколько тем (раскраска графов, начала теории чисел и теории вероятностей) представлены в виде последовательности задач, как это и делалось на кружке, и приведены решения этих задач. И до этого издавались книжки с задачами математических кружков, но тут идея была в том, что эти задачи в целом образуют изложение некоторой
математической теории. Книга Дынкина и Успенского была библиографической редкостью, пока не была переиздана уже сравнительно недавно, в 2004 году (и не появилась в интернете).

Успенский читал лекции для школьников (в частности, для участников математических олимпиад) и написал несколько популярных брошюр в серии «Популярные лекции по математике», никак не связанных с его собственными научными интересами (математической логикой и теорией алгоритмов): про применение механики в математике [17] и про треугольник Паскаля [20]. Впрочем, последняя брошюра затрагивает и логический вопрос: что означает решить комбинаторную задачу и почему нужно фиксировать список разрешённых операций (скажем, включив в него факториалы, но исключив обозначения для биномиальных коэффициентов).

Две другие брошюры в этой серии («Машина Поста» [23] и «Теорема Гёделя о неполноте» [25]) уже посвящены темам из математической логики и теории алгоритмов. Первая из них совсем элементарна и основана на занятиях с младшеклассниками, вторая, наоборот, написана на основе статьи в «Успехах математических наук» [22] и предполагает некоторую математическую культуру, но вполне может быть прочитана и понята продвинутыми старшеклассниками. Популярному изложению ещё одной темы, так называемого «нестандартного анализа», в котором методы математической логики используются для математически корректного рассмотрения бесконечно малых и бесконечно больших величин, посвящена брошюра [27]; её расширенный вариант был опубликован затем издательством «Наука» [31].

Как герой «Игры в бисер» Гессе, становясь старше, Успенский объяснял всё более и более базовые вещи, занявшись проповедью математики среди «гуманитарев». Впрочем, началось это уже давно, в 1960-е годы, когда он разрабатывал и осуществлял курс математики для отделения теоретической и прикладной лингвистики филологического факультета МГУ, но в последние два десятилетия своей жизни он обращался к гораздо более широкой аудитории. Несколько его лекций на летних школах по математике и лингвистике в Дубне, к счастью, сохранились как видеозаписи (прежде всего благодаря Виталию Арнольду), и по ним (см. ссылки в http://www.mathnet.ru/php/person.phtml?option lang=rus&personid=20219) можно составить представление об Успенском как лекторе—хотя, конечно, в полной мере оценить его можно было только на университетских лекциях, особенно спецкурсах. При этом проповедь Успенского была именно проповедью математики, а не «о математике». Он рассказывал простые вещи, но всерьёз, с определениями, примерами и доказательствами. Одна из его последних книжек [56] так и называется: «Простейшие примеры математических доказательств». Другая книжка [44] называется «Что такое аксиоматический метод?» — и там тоже подробно разобрано множество примеров (в частности, из школьной геометрии, точнее, из той части школьной геометрии, которая в школах пропускается). Например, объясняется, как вывести из аксиом, что для всякой прямой найдётся точка, на ней не лежащая. Материалы из этих двух книг вошли в сборник «Апология математики» [54] (вместе с другими статьями, уже более общего характера). И удивительным образом проповедь Успенского имела успех (по крайней мере в том же смысле, что у Антония Падуанского): Успенскому была присуждена премия «Просветитель» (учреждённая Дмитрием Борисовичем Зиминым и фондом «Династия») за 2010 год в области естественных и точных наук.

Помимо собственных книг, большой заслугой Успенского (то, что называют по-английски community service) является организация издания многих классических книг по математической логике и теории алгоритмов на русском языке: он переводил (по инициативе Колмогорова) книгу Р. Петер о рекурсивных функциях [64], редактиров
вал перевод классических монографий Клини [65] и Роджерса [70], книги Дэвиса о нестандартном анализе [71] (видимо, первого изложения идей нестандартного анализа, появившегося по-русски), фундаментального учебника Чёрча по логике [67], первого тома «Начал математики» Бурбаки [68], а также книги Эшби о кибернетике [66].
# Список литературы

Сайты с работами В. А. Успенского:

[1] Страница В. А. Успенского на сайте mathnet.ru: http://www.mathnet.ru/rus/person20219

[2] Страница В. А. Успенского на сайте кафедры математической логики и теории алгоритмов мехмата МГУ: http://1pcs.math.msu.su/~uspensky/

## Работы В. А. Успенского

[3] Геометрический вывод основных свойств гармонических функций. Успехи математических наук, 1949, том IV, выпуск 2(30), с. 201–205, http://1pcs.math.msu.su/~uspensky/bib/Uspensky_1949_UMN_Geometr_vyvod.pdf, http://mi.mathnet.ru/umn8612

[4] Общее определение алгоритмической вычислимости и алгоритмической сводимости. Дипломная работа. Научный руководитель — академик А. Н. Колмогоров. Московский государственный университет им. М. В. Ломоносова, механико-математический факультет. Машинопись. 90 с. http://1pcs.math.msu.su/~uspensky/bib/Uspensky_1952_Diploma.pdf

[5] Е. Б. Дынкин, В. А. Успенский, Математические беседы. Задачи о многоцветной раскраске. Задачи из теории чисел. Случайные блуждания. (Библиотека математического кружка, вып. 6). Москва–Петербург: Государственное издательство технико-теоретической литературы, 1952. http://ilib.mccme.ru/djvu/bib-mat-kr/besedy.htm, http://www.math.ru/lib/book/djvu/bib-mat-kr/besedy.djvu. 2-e издание: Наука, 2004. Английский перевод был выпущен в виде трёх брошюр издательством D.C. Heath, Boston в 1963 году, и позже в виде единой книги: Е.В. Dynkin, V.A. Uspenskii, Mathematical Conversations: Multicolor Problems, Problems in the Theory of Numbers, and Random Walks, Dover books in mathematics, Dover Publications, 2006, ISBN 0-486-45351-0.

[6] О понятии алгоритмической сводимости. Резюме доклада в Московском математическом обществе 17 марта 1953 года, Успехи математических наук, т. VIII, вып. 4(56), 1953, июль–август, с. 176, см. http://mi.mathnet.ru/umn8234

[7] Теорема Гёделя и теория алгоритмов. Резюме доклада в Московском математическом обществе 24 марта 1953 года, Успехи математических наук, т. VIII, вып. 4(56), 1953, июль–август, с. 176–178, см. http://mi.mathnet.ru/umn8234

[8] Теорема Гёделя и теория алгоритмов, Доклады Академии наук СССР, т. 91, номер 64 с. 737–740 (1953), https://istina.msu.ru/publications/article/92662634/ (есть полный текст). Английский перевод: Gödel’s theorem and the theory of algorithms, American Mathematical Society Translations, Series 2, Advances in the Mathematical Sciences, vol. 23 (1963), 103–107, DOI10.1090/trans2/023/06

[9] О вычислимых операциях, Доклады Академии наук СССР, том 103, номер 5 (1955), с. 773–776, https://istina.msu.ru/publications/article/92662640/ (есть полный текст)
[10] Системы перечислимых множеств и их нумерации, Доклады Академии наук СССР, том 105, номер 6 (1955), с. 1155–1158, https://istina.msu.ru/publications/article/92662649/ (есть полный текст)

[11] О вычислимых операциях, диссертация на соискание учёной степени кандидата физико-математических наук, Московский государственный университет имени М. В. Ломоносова, механико-математический факультет, октябрь 1955 г.

[12] Вычислимые операции и понятие программы. Резюме доклада в Московском математическом обществе 28 февраля 1956 года, Успехи математических наук, т. ХІ, вып. 4(70), 1956, июль-август, с. 172–176, http://mi.mathnet.ru/umn7861

[13] Третий всесоюзный математический съезд. Обзорный доклад «Об алгоритмической сводимости» 26 июня 1955 года. Доклад «Понятие программы и вычислимые операторы» 2 июля 1955 года. Сообщение «Вычислимые операции, вычислимые операторы и конструктивно-непрерывные функции» 3 июля 1955 года. Краткое содержание выступлений опубликовано: Труды третьего всесоюзного Математического съезда. М.: издательство АН СССР, 1956. Т. 2, с. 66–69 (обзорный доклад), т. 1, с. 186 (доклад), т. 1, с. 185 (сообщение).

[14] К теореме о равномерной непрерывности. Успехи математических наук, т. XII, вып. 1(73), 1957, январь–февраль, с. 100–142, http://mi.mathnet.ru/umn7524

[15] Несколько замечаний о перечислимых множествах. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, Bd. 3, S. 157–170 (1957), https://istina.msu.ru/publications/article/92666188/ (есть полный текст) Английский перевод: Some remarks on recursively enumerable sets, American Mathematical Society Translations, Series 2, Advances in the Mathematical Sciences, vol. 23 (1963), 89–101, DOI10.1090/trans2/023/05

[16] А. Н. Колмогоров, В. А. Успенский. К определению алгоритма. Успехи математических наук, т. XIII, вып. 4(82), 1958, июль–август, с. 3–28, http://mi.mathnet.ru/umn7453. Английский перевод (Elliott Mendelson): Kolmogorov A.N., Uspenskij V.A., On the definition of an algorithm, American Mathematical Society Translations, Series 2, Advances in the Mathematical Sciences, vol. 29 (1963), 217–245, DOI10.1090/trans2/029/07

[17] Некоторые приложения механики к математике (Популярные лекции по математике, выпуск 27). М.: Государственное издательство физико-математической литературы, 1958. 48 с., http://www.math.ru/lib/book/djvu/plm/plm27.djvu

[18] К вопросу о соотношении между различными системами конструктивных действительных чисел, Известия высших учебных заведений, математика, 1960, номер 2(15), с. 199–208, http://mi.mathnet.ru/ivm2028

[19] Лекции о вычислимых функциях. Москва, государственное издательство физико-математической литературы, 1960. 492 с. Французский перевод: Ouspenski V.A., Leçons sur les fonctions calculables. Paris, Hermann, 1966. 412 p.

[20] Треугольник Паскаля (Популярные лекции по математике, выпуск 43.) М.:Наука, главная редакция физико-математической литературы, 1966. 35 с. Второе издание (дополненное), 1979. 48с. http://www.math.ru/lib/book/plm/v43.djvu
[21] О сводимости вычислимых и потенциально вычислимых нумераций, *Математические заметки*, т. 6, номер 1 (1969), с. 3–9, http://mi.mathnet.ru/mz6891/ Английский перевод: V.A. Uspenskii, Reduction of computable and potentially computable numerations, *Mathematical Notes of the Academy of Sciences of the USSR*, 1969, vol. 6, no. 1, 461–464, DOI10.1007/BF01450246, https://istina.msu.ru/publications/article/92645436/ (есть полный текст)

[22] Теорема Гёделя о неполноте в элементарном изложении. *Успехи математических наук*, т. XXIX, вып. 1(175), с. 3–47 (1974, январь–февраль), http://mi.mathnet.ru/umn4322. Английский перевод (E. Lichfield): Uspenskii V.A., An elementary exposition of Gödel’s incompleteness theorem, *Russian Mathematical Surveys*, vol. 29 (1974), no. 1, 63–106, DOI10.1070/RM1974v029n01ABEH001280, https://istina.msu.ru/publications/article/92645484/ (есть полный текст)

[23] *Машина Поста*. (Популярные лекции по математике, выпуск 54). М.:Наука, главная редакция физико-математической литературы, 1979. 96 с., http://www.math.ru/lib/book/plm/v54.djvu

[24] Uspensky V.A., Semenov A.L., What are the gains of the theory of algorithms: Basic developments connected with the concept of algorithm and with its application in mathematics, *Algorithms in Modern Mathematics and Computer Science, Proceedings, Urgench, Uzbek SSR, September 16–22, 1979*. Edited by A.P. Ershov and D. Knuth, Lecture Notes in Computer Science, 122, Springer, 1981, p. 100–234.

[25] Теорема Гёделя о неполноте. (Популярные лекции по математике, выпуск 57) М.:Наука, главная редакция физико-математической литературы, 1982, http://www.math.ru/lib/book/plm/v57.djvu. Английский перевод опубликован в 1987 (Mir Publisher, перевёл N. Koblitz) и затем в *Theoretical Computer Science*, **130** (1994), 239–319.

[26] Успенский В.А., Семёнов А.Л., Теория алгоритмов: основные открытия и приложения. В сборнике *Алгоритмы в современной математике и её приложениях*. Материалы международного симпозиума, Ургенч, УзССР, 16–22 сентября 1979 г. А.П. Ершов, Д. Кнут, редакторы. Часть І, с. 99–342.

[27] Нестандартный, или неархимедов, анализ. М.:Знание, 1983. 61 с.

[28] Успенский В.А., Кановей В.Г., Проблемы Лузина о конституантах и их судьба. *Вестник Московского университета. Серия 1: Математика, механика*, 1983, номер 6, с. 73–87, https://istina.msu.ru/publications/article/93856782/. Английский перевод: Uspenskii V.A., Kanovei V.G., Luzin's problems on constituents and their fate, *Moscow University Mathematics Bulletin*, vol. 38, no. 6 (1983), 86–102. (Allerton Press, inc.)

[29] Вклад Н.Н. Лузина в дескриптивную теорию множеств и функций: понятия, проблемы, предсказания. *Успехи математических наук*, т. 40, вып. 3(243), с. 85–116, http://mi.mathnet.ru/umn2648. Английский перевод: Uspenskii V.A., Luzin's contribution to the descriptive theory of sets and functions: concepts, problems, predictions, *Russian Mathematical Surveys*, vol. 40, no. 3 (1985), 97–134, https://istina.msu.ru/publications/article/92645592/ (есть полный текст)

[30] А. Л. Семенов, В. А. Успенский, Математическая логика в вычислительных науках и вычислительной практике, *Вестник Академии наук СССР*, **56**(7), 93–103 (1986)
[31] Что такое нестандартный анализ? М.:Наука, главная редакция физико-математической литературы, 1987. 128 с.

[32] В. А. Успенский, А. Л. Семёнов, *Теория алгоритмов: основные открытия и приложения*, М.: Наука, главная редакция физико-математической литературы, 1987. (Серия «Библиотечка программиста», выпуск 49.) 288 с. Английский перевод: Vladimir Uspensky, Alexei Semenov, *Algorithms: Main Ideas and Applications*, Kluwer Academic Publishers, 1993, https://doi.org/10.1007/978-94-015-8232-2

[33] Колмогоров А. Н., Успенский В. А., Алгоритмы и случайность, *Теория вероятностей и её применения*, том XXXII, выпуск 3, 1987 год, июль, август, сентябрь, с. 425–455, http://mi.mathnet.ru/tvp1437. Английский перевод: Kolmogorov A.N., Uspenskii V.A., Algorithms and randomness, *Theory of Probability and Its Applications*, SIAM Publishers, vol. 32, no. 3, 389–412. http://dx.doi.org/10.1137/1132060, https://istina.msu.ru/publications/article/92647240/ (есть текст)

[34] Успенский В.А., Кановей В.Г., Вклад М.Я. Суслина в теоретико-множественную математику. *Вестник Московского университета. Серия 1: Математика, механика*, 1988, номер 5, с. 8–12, https://istina.msu.ru/publications/article/93856823/. Английский перевод: Uspenskii V.A., Kanovei V.G., M.Ya. Suslin’s contribution to set-theoretic mathematics, *Moscow University Mathematics Bulletin*, vol. 43, no. 5 (1988), 29–40. (Allerton Press, inc.)

[35] В. А. Успенский, А. Л. Семёнов, А. Х. Шень, Может ли (индивидуальная) последовательность нулей и единиц быть случайной? *Успехи математических наук*, т. 45, вып. 1(271), с. 105–162 (1990, январь–февраль), http://mi.mathnet.ru/umn4692

[36] Успенский В.А., Плиско В.Е., Диагностические пропозициональные формулы, *Вестник Московского университета. Серия 1: Математика, механика*, 1991, номер 3, с. 7–12, https://istina.msu.ru/publications/article/92717778/

[37] *Complexity and Entropy: An Introduction to the Theory of Kolmogorov Complexity*, в книге: *Kolmogorov Complexity and Computational Complexity*, Osamu Watanabe, editor. Springer, 1992, ISBN 3-540-55840-3, p. 85–102.

[38] Kolmogorov and mathematical logic, *The Journal of Symbolic Logic*, volume 57, number 2, June 1992, 385–412.

[39] Vladimir A. Uspensky and Valery Ye. Plisko, Review: Raymond M. Smullyan, Gödel's incompleteness theorems, *The Journal of Symbolic Logic*, volume 60, issue 4 (1995), 1320–1324, https://projecteuclid.org/euclid.jsl/1183744885

[40] V.A. Uspensky, A. Shen, Relation Between Varieties of Kolmogorov Complexities, *Mathematical Systems Theory*, **29**, 271–292 (1996), https://link.springer.com/article/10.1007/BF01201280, lpcs.math.msu.su/~uspensky/bib/Uspensky_1996_MST_Shen_Relations Between varieties

[41] Kolmogorov complexity: recent research in Moscow. In W.Penczek, A.Szalas (eds.), *Proceedings of the 21st International Symposium on Mathematical Foundations of Computer Science 1996* (MFCS96), Crakow, Poland, September
2-6, 1996 (Lecture Notes in Computer Science, v. 1113), 1996, p. 156-
166, https://link.springer.com/chapter/10.1007/3-540-61550-4_145,
http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1996_LNCS_Kolmogorov_Complexity_Rec

[42] Mathematical logic in the former Soviet Union: brief history and current trends, *Logic and Scientific Methods*, M.L. Dalla Chiare et al., editors, Kluver Academic Publishers, https://www.springer.com/us/book/9780792343837, 457–483.

[43] Andrei A. Muchnik, Alexei L. Semenov, Vladimir A. Uspensky, Mathematical metaphysics of randomness, *Theoretical Computer Science*, **207**, 263–317 (1998), https://www.sciencedirect.com/science/article/pii/S0304397598000693 (доступен полный текст), http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1998_TCS_Muchnik

[44] Что такое аксиоматический метод? Ижевск: издательский дом «Удмуртский университет», 2000. 100 с. ISBN 5-7029-0337-4.

[45] Why Kolmogorov complexity? In: E.Goles and C.Martinez (eds.), *Complex systems* (Series: Nonlinear Phenomena and Complex Systems, Vol. 6), Kluwer Academic Publishers, 2001, p. 201–260. ISBN 0-7923-6830-4, https://link.springer.com/chapter/10.1007/978-94-010-0920-1_5

[46] Труды по нематематике с приложением семиотических посланий А. Н. Колмогорова к автору и его друзьям. М.:ОГИ, 2002. 1409 с., ISBN 5-94282-086-4, http://www.math.ru/lib/book/pdf/shen/usp/usp-all.pdf

[47] B. Durand, V. Kanovei, V.A. Uspensky, N.K. Vereshchagin. Do stronger definitions of randomness exist? *Theoretical Computer Science*, v. 290, No. 3, p. 1987–1996 (2001), https://www.sciencedirect.com/science/article/pii/S0304397502000403 (доступен полный pdf-файл)

[48] Успенский В.А., Верещагин Н.К., Плиско В.Е., *Вводный курс математической логики*, М.: Физматлит, 2004.

[49] Кановей В.Г., Успенский В.А., Об эквивалентности двух форм континуум-гипотезы, *Вестник Московского университета. Серия 1: Математика, механика*, 2005, номер 3, с. 62–64, https://istina.msu.ru/publications/article/100287822/ (есть текст как фото)

[50] Четыре алгоритмических лица случайности, *Математическое просвещение*, серия 3, выпуск 10, М.:МЦНМО, 2006, с. 71–108, http://mi.mathnet.ru/mp188. Вошло в качестве приложения в книгу [59].

[51] Колмогоров, каким я его помню. *Колмогоров в воспоминаниях учеников*, редактор-составитель А. Н. Ширяев, текст подготовлен Н. Г. Химченко, М:МЦНМО, 2006, 272–371.

[52] Кановей В.Г., Успенский В.А., О единственности нестандартных расширений, *Вестник Московского университета. Серия 1: Математика, механика*, 2006, номер 5, с. 3–10, https://istina.msu.ru/publications/article/100285758/ (есть скан текста)
[53] В. Г. Кановей, Т. Линтон, В. А. Успенский, Игровой подход к мере Лебега, *Математический сборник*, т. 199, номер 11 (2008), 21–44, http://mi.mathnet.ru/msb3948
Английский перевод: V.G.Kanovei, Tom Linton and Vladimir A. Uspensky, Lebesgue measure and gambling, *Sbornik: Mathematics*, volume 199, no. 11, p. 1597, http://dx.doi.org/10.1070/SM2008v199n11ABEH003974

[54] *Апология математики*. Санкт-Петербург: Амфора, 2009. 554 с.

[55] К истории проблемы Гольдбаха, В кн.: *Историко-математические исследования. Вторая серия*. РАН, Институт естествознания и техники им. С. И. Вавилова. Вып. 13(48). М.: Янус-К, 2009, ISBN 978-5-8037-0449-2, с. 273–283.

[56] *Простейшие примеры математических доказательств* (Библиотека «Математическое просвещение», вып. 34). М.:МЦНМО, 2009. 56 с. ISBN 978-5-94057-492-7.
http://www.math.ru/lib/book/pdf/mp-seria/034_uspensky.pdf

[57] В. А. Успенский, В. В. Выюгин, Становление алгоритмической теории информации в России, *Информационные процессы*, том 10, номер 2, с. 145–158.

[58] Теорема Гёделя и четыре дороги, ведущие к ней, *Математическое просвещение*, серия 3, выпуск 15, М.:МЦНМО, 2011, с. 35–75, http://mi.mathnet.ru/mp309

[59] Н. К. Верещагин, В. А. Успенский, А. Шень, *Колмогоровская сложность и алгоритмическая случайность*, М.:МЦНМО, 2013. 575 с. (Английский перевод: A. Shen, V. Uspensky, N. Vereshchagin, *Kolmogorov complexity and algorithmic randomness*, American Mathematical Society, 2017.)

[60] [В. А. Успенский, М. С. Гельфанд] *Математика*—это гуманитарная наука (интервью с В. А. Успенским ведёт М. С. Гельфанд), в книге: *Математические прогулки. Сборник интервью*, М.:издательство Паулсен, 2017. ISBN 978-5-98797-057-7, с. 198–207.

[61] Vladimir Uspenskiy and Alexander Shen, *Algorithms and Geometric Constructions, Computability in Europe, 2018*, Lecture Notes in Computer Science, v. 10936, Springer, p. 410–420 (2018), см. также arXiv:1805:12579

[62] *Труды по нематематике. Второе издание, исправленное и дополненное. В пяти книгах. Книга пятая. Воспоминания и наблюдения.* М.:Объединённое гуманитарное издательство. Фонд «Математические этюды». 2018. 1118 с.

[63] Третий математический съезд. В кн.: [62, с. 897–905]. Примечания. Там же, с. 905–912.

Публикации, в подготовке которых участвовал В. А. Успенский

[64] Р. Петер, *Рекурсивные функции*, перевод с немецкого В. А. Успенского под редакцией и с предисловием А. Н. Колмогорова. М.:Издательство иностранной литературы, 1954. (Оригинал: *Rekursive Funktionen*, von Rósza Péter, Budapest, 1951.)

[65] Стефан К. Клини, *Введение в метаматематику*, перевод с английского А. С. Есенина-Вольпина под редакцией В. А. Успенского. М.:Издательство иностранной литературы, 1957. (Оригинал: Stephen Cole Kleene, *Introduction to metamathematics*, D. van Nostrand company, New York, Toronto, 1952.)
[66] У. Росс Эшби, *Введение в кибернетику*, перевод с английского Д. Г. Лахути под редакцией В. А. Успенского с предисловием А. Н. Колмогорова. М.: Издательство иностранной литературы, 1959. 428 с. (Оригинал: *An introduction to cybernetics*, by W. Ross Ashby, London, Chapman&Hall Ltd., 1956.)

[67] А. Чёрч, *Введение в математическую логику, I*, перевод с английского В. С. Чернявского под редакцией В. А. Успенского, М.: Издательство иностранной литературы, 1960. (Оригинал: *Introduction to mathematical logic* by Alonzo Church. Volume I. Princeton University Press, 1956.)

[68] Н. Бурбаки, *Начала математики. Первая часть. Основные структуры анализа. Книга первая. Теория множеств*. Перевод с французского Г. Н. Поварова и Ю. А. Шихановича под редакцией и с предисловием В. А. Успенского, М.: Мир, 1965. (Оригинал: *Éléments de mathématique par N. Bourbaki, XVII, XX, XXII, I. Première partie. Les structures fondamentales de l'analyse. Livre I. Théorie des ensembles. Hermann, 1956-1960.*)

[69] *Математика в современном мире*, сборник переводов из специального выпуска Mathematics in the modern world, Scientific American, 1964. Перевод с английского Н. Г. Рычковой. Под редакцией и с предисловием В. А. Успенского. М.: Мир, 1967.

[70] Х. Роджерс, *Теория рекурсивных функций и эффективная вычислимость*, перевод с английского В. А. Душского, М. И. Кановича, Е. Ю. Ногиной под редакцией В. А. Успенского. М.: Мир, 1972. (Оригинал: Hartley Rogers, Jr., *Theory of recursive functions and effective computability*, McGraw-Hill Book Company, 1967. Предварительная версия с тем же названием. Volume I. Mimeographed. Technology Store, Cambridge, Mass., 1957.)

[71] М. Дэвис, *Прикладной нестандартный анализ*, перевод с английского С. Ф. Сопрунова под редакцией и с предисловием В. А. Успенского, М.: Мир, 1980. (Оригинал: Martin Davis, *Applied nonstandard analysis*, Wiley&Sons, 1977.)

Другие цитируемые работы

[72] Th. Skolem, *Begründung der elementaren Arithmetik durch dir rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich* (Videnskapsselskapets Scrifter, I. Mat.-naturv. Klasse, 1923, No. 6), Kristiania, 1923. (Английский перевод: The foundations of elementary arithmetic established by means of the recursive mode of thought without the use of apparent variables ranging over infinite domains, в сборнике [102, p. 302–333].)

[73] David Hilbert, *Über das Unendliche, Mathematische Annalen*, Bd. 95, S. 161–190 (1926). (Английский перевод: On the Infinite, [102, p. 367–392].)

[74] Wilhelm Ackermann in Göttingen, Zum Hilbertschen Aufbau der reellen Zahlen, *Mathematische Annalen*, Bd. 99, 118–133 (1928). (Английский перевод: On Hilbert’s construction of the real numbers, [102, p. 493–507].)

[75] Kurt Gödel in Wien, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, *Monatshefte für Mathematik und Physik*, **38**, 173–198 (1931). (Английский перевод: On formally undecidable propositions of *Principia Mathematica* and related systems I, [102, p. 596–616] или [99, p. 4–38].)
[76] J. Herbrand à Paris, Sur la non-contradiction de l'Arithmétique, *Journal für die reine und angewandte Mathematik*, Bd. 166, S. 1-8 (1932), http://www.digizeitschriften.de/dms/img/?PID=PPN243919689_0166%7Clog4 (Английский перевод: On the consistency of arithmetic [102, p. 618-628].)

[77] Kurt Gödel, *On undecidable propositions of formal mathematical systems*, записки лекций в Institute for Advanced Study (Принстон), весна 1934 года. Воспроизведено в [99, p. 39-74].

[78] Rósza Péter, Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktionen, *Mathematische Annalen*, Bd. 110, n. 1, S. 612-632 (1935), https://doi.org/10.1007/BF01448046, https://link.springer.com/article/10.1007%2FBF01448046

[79] Alonzo Church, An unsolvable problem of elementary number theory, *American Journal of Mathematics*, vol. 58, no. 2 (April 1936), 345-363. Перепечатано в [99, p. 88-107].

[80] S.C. Kleene, General recursive functions of natural numbers, *Mathematische Annalen*, Bd. 112, S. 727-742 (1936), https://eudml.org/doc/159849. Перепечатано в [99, p. 236-253].

[81] Emil L. Post. Finite combinatory processes. Formulation I. *The Journal of Symbolic Logic*, vol. 1 (1936), p. 103–105.

[82] A.M. Turing, On computable numbers, with an application to the Entscheidungsproblem, *Proceedings of the London Mathematical Society*, ser. 2, vol. 42 (1936-7), p. 230-265; исправления в следующем томе того же журнала: vol. 43 (1937), p. 544-546. Перепечатано в [99, p. 116-154].

[83] S.C. Kleene, On notations for ordinal numbers, *Journal for Symbolic Logic*, 3, 150-155 (1938), https://www.jstor.org/stable/2267778

[84] A.M. Turing, Systems of logic based on ordinals, *Proc. London Math. Soc.* (2), vol. 45 (1939), pp. 161-228, https://doi.org/10.1112/plms/s2-45.1.161. (Перепечатано в [99, p. 154-222]. Есть текст одноимённой диссертации Тьюринга в Принстоне, http://www.dcc.fc.up.pt/~acm/turing-phd.pdf)

[85] S.C. Kleene, Recursive predicates and quantifiers, *Transactions of the American Mathematical Society*, 53, number 1, 41-73 (1943), https://doi.org/10.1090/S0002-9947-1943-0007371-8. Перепечатано в [99, p.254-287].

[86] Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, *Bulletin of the American Mathematical Society*, 5, 284-316 (1944). https://projecteuclid.org/download/pdf_1/euclid.bams/1183505800. Перепечатано в [99, p.304-337].

[87] S.C. Kleene, A symmetric form of Gödel's theorem (Presented to the American Mathematical Society, October 29, 1949. Communicated by Prof. L.E.J. Brouwer at the meeting of April 29, 1950). Koninklijke Nederlandse Akademie van Wetenschappen, Volume 53, deel 6 (1950), 800-802, http://www.dwc.knaw.nl/DL/publications/PU00018825.pdf
[88] H.G. Rice, Classes of recursively enumerable sets and their decision problems, *Transactions of the American Mathematical Society*, vol. 74 (1953), p. 358–366.

[89] Lászlo Kalmár in Szeged, Ungarn, Über ein Problem, betreffend die definition des Begriffes der allgemein-rekursiven Funktion, *Zeitschrift für mathematische Logik und Grundlagen der Mathematik*, Bd. 1, S. 93–95 (1955), https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19550010204

[90] John Myhill, A fixed point theorem in recursion theory, abstract, Eighteenth Meeting of the Association of Symbolic Logic, *The Journal of Symbolic Logic*, volume 20, no.2 (June 1955), p. 205.

[91] J. Myhill in Berkeley, California (USA), J.C. Sheperdson in Bristol, England, Effective operations in partial recursive functions, *Zeitschrift für mathematische Logik und Grundlagen der Mathematik*, Bd. 1, S. 310–317 (1955), https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.19550010407

[92] H.G. Rice, On completely recursive enumerable classes and their key arrays, *The Journal of Symbolic Logic*, volume 21, number 3, Sept. 1956, p. 304–308. (Received September 14, 1955) https://www.jstor.org/stable/2269105

[93] Martin Davis, *Computability and Unsolvability*, McGraw-Hill Book Company, 1958.

[94] Hartley Rogers, Jr. Gödel numberings of partial recursive functions, *Journal of Symbolic Logic*, Volume 23, Number 3, Sept. 1958, p. 331–341 (Received July 7, 1958), https://www.jstor.org/stable/2964292

[95] Richard M. Friedberg, Hartley Rogers jr., Reducibility and Completeness for Sets of Integers, *Zeitschrift für mathematische Logik und Grundlagen der Mathematik*, Bd. 5, S. 117–125 (1959), https://doi.org/10.1002/malq.19590050703

[96] Kreisel, G., Lacombe, D., Shoenfield, J.R., *Partial recursive functionals and effective operations*, in *Constructivity in Mathematics*, A. Heyting, editor, North Holland, 1959, p. 195–207.

[97] John Myhill, Note on degrees of partial functions, *Proceedings of the American Mathematical Society*, **12** (1961), p. 519–521, https://doi.org/10.1090/S0002-9939-1961-0125794-X

[98] Г. С. Цейтин, Алгорифмические операторы в конструктивных метрических про-
странствах, Труды математического института имени В. А. Стеклова, LVII,
Проблемы конструктивного направления в математике, 2 (Конструктивный мат-
тематический анализ), сборник работ под редакцией Н. А. Шанина, Издательство
Академии наук СССР, Москва, Ленинград, 1962, с. 295–361.

[99] *Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions*, сборник работ, составитель Martin Davis, Raven Press, Hewlett, New York, 1965.

[100] А. И. Мальцев, *Алгоритмы и рекурсивные функции*, М.:Наука, 1965. (2-е издание, 1986)
[101] Per Martin-Löf, The definition of random sequences, *Information and Control*, volume 9, issue 6, December 1966, p. 602–619, https://doi.org/10.1016/S0019-9958(66)80018-9

[102] *From Frege to Gödel. A Source Book in Mathematical Logic, 1879-1931*, сборник работ, составитель Jean van Heijenoort, Harvard University Press, Cambridge, Massachusetts, 1967.

[103] John Case, Enumeration reducibility and partial degrees, *Annals of mathematical logic*, vol. 2, no. 4 (1971), 419-439. (Received 9 September 1969), https://www.sciencedirect.com/science/article/pii/0003484371900039

[104] А. Шень, Аксиоматический подход к теории алгоритмов и относительная вычислимость, *Вестник Московского университета. Серия 1: Математика, механика*. 1980, выпуск 2, с. 27–29. (Английский перевод автора: https://hal-lirmm.ccsd.cnrs.fr/lirmm-01923123.)

[105] Stephen C. Kleene, The theory of recursive functions, approaching its centennial. (Elementarrekursiontheorie vom höheren Standpunkte aus.) *Bulletin of the American Mathematical Society*, volume 4, number 1, July 1981, 43–61.

[106] Nigel Cutland, *An introduction to recursive function theory*, Cambridge University Press, 1980. Русский перевод Ал. А. Мучника под редакцией С. Ю. Маслова: Н. Катленд, *Вычислимость. Введение в теорию рекурсивных функций*. М.:Мир, 1983.

[107] А.Х.Шень, Алгоритмические варианты понятия энтропии, *Доклады Академии наук, 1984, том 276, номер 3, с. 563–566*. (Английский перевод: Soviet Math. Doklady, **29**(3), 1984, 569–573.)

[108] Piergiorgio Odifreddi, *Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers* (Studies in logic and the foundations of mathematics, volume 125), Elsevier, 1989. xix+668 pages.

[109] Robert I. Soare, *Computability and Recursion, Bulletin of Symbolic Logic*, **2**(3), 284–321 (1996). См. также http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

[110] V.V. Vyugin, Ergodic theorems for individual random sequences, *Theoretical Computer Science*, volume 207, issue 2, November 6, 1998, p. 343–361, https://doi.org/10.1016/S0304-3975(98)00072-3.

[111] Mariya I. Soskova, The Turing Universe in the Context of Enumeration Reducibility. In: Bonizzoni P., Brattka V., Löwe B. (eds), *The Nature of Computation. Logic, Algorithms, Applications. CiE 2013*. Lecture Notes in Computer Science, vol 7921. Springer, Berlin, Heidelberg, p. 371–382, https://doi.org/10.1007/978-3-642-39053-1_44

[112] Robert I. Soare, *Turing Computability. Theory and Applications*. Springer, 2016, ISBN 978-3-642-31932-7, https://doi.org/10.1007/978-3-642-31933-4
[113] Wikipedia, страницы *Primitive recursive function*, https://en.wikipedia.org/wiki/Primitive_recursive_function и µ-recursive function, https://en.wikipedia.org/wiki/%CE%9C-recursive_function. Версия 5 ноября 2018 года.

[114] Szudzik, Matthew. *Recursive Function*. From MathWorld — A Wolfram Web Resource, created by Eric W. Weisstein. http://mathworld.wolfram.com/RecursiveFunction.html. Версия 5 ноября 2018 года.