Andréi Andréyevich Márkov ( en ruso : Андре́й Андре́евич Ма́рков ; 22 de septiembre de 1903, San Petersburgo - 11 de octubre de 1979, Moscú ) fue un matemático soviético , hijo del matemático ruso Andréi Márkov Sr. , y uno de los fundadores clave de la escuela rusa de matemáticas y lógica constructivas. Hizo contribuciones destacadas en varias áreas de las matemáticas, incluidas las ecuaciones diferenciales , la topología , la lógica matemática y los fundamentos de las matemáticas . [1] [2]
Su nombre está asociado en particular con el principio y la regla de Markov en lógica matemática, el teorema de Markov en teoría de nudos y el algoritmo de Markov en informática teórica . Un resultado importante que demostró en 1947 fue que el problema verbal de los semigrupos era irresoluble; Emil Leon Post obtuvo el mismo resultado de forma independiente aproximadamente al mismo tiempo. En 1953 se convirtió en miembro del Partido Comunista .
En 1960, Markov obtuvo resultados fundamentales que demostraban que la clasificación de variedades de cuatro dimensiones es indecidible : no existe ningún algoritmo general para distinguir dos variedades arbitrarias con cuatro o más dimensiones. Esto se debe a que las variedades de cuatro dimensiones tienen suficiente flexibilidad para permitirnos incrustar cualquier algoritmo dentro de su estructura. Por lo tanto, clasificar todas las variedades de cuatro dimensiones implicaría una solución al problema de parada de Turing . La incrustación implica el fracaso en la creación de una correspondencia entre los algoritmos y la indexación (naturalmente incontablemente infinita, pero aún mayor) de la estructura de las cuatro variedades. El fracaso es en el sentido de Cantor. La indexación es en el sentido de Gödel. Este resultado tiene profundas implicaciones para las limitaciones del análisis matemático.
Entre sus estudiantes de doctorado se incluyen Boris Kushner , Gennady Makanin y Nikolai Shanin .