Андрей Андреевич Марков ( 22 сентября 1903 , Санкт-Петербург — 11 октября 1979, Москва ) — советский математик , сын русского математика Андрея Маркова-старшего , один из основоположников русской школы конструктивной математики и логики. Он внёс выдающийся вклад в различные области математики, включая дифференциальные уравнения , топологию , математическую логику и основания математики . [1] [2]
Его имя, в частности, связано с принципом Маркова и правилом Маркова в математической логике, теоремой Маркова в теории узлов и алгоритмом Маркова в теоретической информатике . Важным результатом, который он доказал в 1947 году, было то, что проблема слов для полугрупп неразрешима; Эмиль Леон Пост получил тот же результат независимо примерно в то же время. В 1953 году он стал членом Коммунистической партии .
В 1960 году Марков получил фундаментальные результаты, показывающие , что классификация четырехмерных многообразий неразрешима : не существует общего алгоритма для различения двух произвольных многообразий с четырьмя или более измерениями. Это связано с тем, что четырехмерные многообразия обладают достаточной гибкостью, чтобы позволить нам встроить любой алгоритм в их структуру. Следовательно, классификация всех четырехмерных многообразий подразумевала бы решение проблемы остановки Тьюринга . Вложение подразумевает неспособность создать соответствие между алгоритмами и индексацией (естественно, несчетно бесконечной, но даже большей) структуры четырехмерных многообразий. Неудача в смысле Кантора. Индексация в смысле Гёделя. Этот результат имеет глубокие последствия для ограничений математического анализа.
Среди его докторантов — Борис Кушнер , Геннадий Маканин и Николай Шанин .