Если к началу 60-х годов уже были достигнуты определённые успехи в изучении сложности алгоритмических вычислений[xxi], то проблемы изучения сложности описаний тех или иных алгоритмов ещё предстояло решать. Пионерские работы А.А. Маркова 1962–1964 годов [22–23] заложили основы соответствующей теории. В частности, во многих случаях оказалось возможным найти новое количественное представление сложности неразрешимости алгоритмических проблем через так называемые оценки сложности разрешения. Поясню вкратце сказанное. Предположим, что мы хотим отыскать алгоритм, распознающий принадлежность произвольного натурального числа nданному множеству M. Как известно, во многих случаях искомый алгоритм невозможен. Вместе с тем данную проблему P можно аппроксимировать финитарными проблемамиP_k – каждая такая проблема состоит в отыскании алгоритма, распознающего принадлежность к Mнатуральных чисел, не превосходящих k. При каждом k можно попытаться оценить сложность описания алгоритма, решающего соответствующую финитарную проблему. Ясно, что если указанная сложность неограниченно возрастает с ростом k, то начальная проблема P алгоритмически неразрешима.

Результаты и идеи Маркова получили значительное развитие в работах его учеников. И так как изучение колмогоровской сложности конструктивных объектов и сложности алгоритмов по Маркову часто приводили к сходным проблемам, в 60-е годы развилось значительное сотрудничество между школами Маркова и Колмогорова. Так же, как это когда-то случилось с Успенским,  молодой математик Н.В. Петри был приглашен А.Н. Колмогоровым вести совместный семинар по сложности алгоритмов. И здесь я хочу упомянуть о проявленной А.Н. деликатности. Поскольку Петри был учеником Маркова, Колмогоров позвонил Андрею Андреевичу и спросил, не имеет ли тот возражений против этой идеи. Об этом телефонном звонке мне рассказывал Марков.

 – Конечно, я ответил, что никаких возражений нет. Совсем наоборот... – добавил Марков.

Я видел, что он был очень доволен.

С другой стороны на семинарах Маркова стали появляться ученики Колмогорова нового поколения. Особенно запомнился блестящий, темпераментный и эксцентричный Л. Левин (ныне профессор Бостонского Университета). Непредсказуемость Левина порою выводила Маркова из себя[xxii], но, вне всякого сомнения, А.А. высоко ценил большой математический талант Левина и позже принимал живое участие в его судьбе. В особенности,   когда в 1971 году «царство тьмы» расправилось с диссертацией Левина (защита происходила в Новосибирске). Конечно, к этому были все основания: диссертант имел возмутительную национальность, и вдобавок его руководителем был А.Н. Колмогоров!

7. Пасмурным октябрьским днём 1987 года московские математики прощались с А.Н. Колмогоровым. Деревья под охраной чугунных ворот, старых, красных кирпичных стен и милиционеров ещё желтели негромкими красками московской осени. Было тепло, тихо, только вороны кричали о чём-то своём, вечном... Далеко за рекой, на холме угадывался силуэт Университета. Когда я бросил по старому обычаю горсть земли в открытую могилу, я вдруг остро почувствовал душою то, что мой ум давно понимал: с Колмогоровым навсегда ушла целая эпоха. Я видел эту боль и на многих лицах вокруг. Потом все разбрелись по кладбищу. У каждого кто-то был здесь. Если не родственник, друг, то хотя бы Чехов и Шостакович. Я поклонился могиле П.С. Новикова и Л.В. Келдыш, постоял у доски, за которой скрыта урна с прахом С.А. Яновской, и пошёл к воротам. Уже темнело, кончался 87-й год. Впереди было расставание с Россией.

ЛИТЕРАТУРА

1. Uspensky V.A. Kolmogorov and Mathematical Logic. The Journal of Symbolic Logic, v. 57, No 2, 385–412, 1992.

2. Люстерник Л.А. Ранние годы Московской математической школы. Успехи Математических Наук, т. 22, No. 1, 137–161, 1967.

3. Люстерник Л.А. Ранние годы Московской математической школы.  Там же, т. 22, No. 2, 199–239, 1967.

4. Люстерник Л.А. Ранние годы Московской математической школы. Там же, т. 22, No. 4, 199–239, 1967.

5. Кушнер Б.А. Марков и Бишоп. Вопросы Истории Естествознания и Техники, 1, 70–81, 1992.

6. Вейль Г. О философии математики. Сборник работ (пер. с немецкого) ГТТИ, 1934.

7. Гейтинг А. Обзор исследований по основаниям математики, М.-Л., ОНТИ, 1936.

8. Юшкевич А.П. Встречи с А.Н. Колмогоровым. Препринт. 1990.

9. Колмогоров А.Н. О принципе «tertiumnondatur», Математический Сборник, т.32, 646–667, 1924/1925.

10. Колмогоров А.Н. Zur Deutung der intuitionistischen Logic. Mathematische Zeitschrift, v. 35, 58–65, 1932.

11. А.Г. Драгалин, Б.А. Кушнер. Математический Интуиционизм. Большая Советская Энциклопедия, т.15, 488, 1974.

12. Borel E. Lecons sur theorie des fonctions, 3rd ed., Gauthier-Villars, Paris, 1928.

13. Dalen D. van, Troelstra A. S. Constructivity in Mathematics. An Introduction. Vol.1–2, North-Holland, Amsterdam-New York-Oxford-Tokyo, 1988.

14. Troelstra A.S. On the Early History of Intuitionistic Logic.In P.Petkov, Ed. Mathematical Logic, 3–17, Plenum Press, New York-London, 1990.

15. Колмогоров А.Н. Письма к Гейтингу. Успехи Математических Наук, т.43, No.6, 75–77, 1988.

16. Kleene S.C. On the interpretation of intuitionistic number theory. Journal of Symbolic Logic, v.10, 109–124, 1945.

17. Heijenort J. van.(Ed.) from Frege to Goedel: a source-book in mathematical logic, 1879–1931, Harvard University Press, Cambridge, Massachusetts, 1967.

18. Новиков П.С. On the consistency of certain logical calculus. Математический сборник, т. 12 (54), 231–261, 1943.

19. Feferman A.B. Politics, Logic, and Love. The Life of Jean van Heijenoort. Jones and Bartlett Publ., Boston-London, 1993.

20. Mendelson E. Second Thoughts about Church's Thesis and Mathematical Proofs. The Journal of Philosophy, v.87 No.5, 225–233, 1990.

21. Трахтенброт Б.А. Сложность алгоритмов и вычислений. Новосибирск 1967.

22. Марков А.А. О нормальных алгорифмах, вычисляющих булевы функции. Доклады АН СССР, т. 157б No. 2, 262–264, 1964.

23. Марков А.А. О нормальных алгорифмах, связанных с вычислением булевых функций. Известия АН СССР, сер. мат., т.31, No. 1, 161–208, 1967.

1-я редакция: январь 1993 г.

2-я редакция: март 2004 г.