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