ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

MARKOV Andreï Andreïevitch (junior), russe, 1903-1979

» Biographie issue du Laboratoire de logique mathématique de l' Institut Steklov de Mathématiques de Saint-Pétersbourg.

Diplômé de l'Université de Leningrad en 1924, A. A. Markov est le fils de A. A. Markov bien connu pour ses processus markoviens. Il obtint une chaire d'enseignement à l 'Université de Leningrad en 1936 et sera à la tête du Département de Géométrie de cette université jusqu'en 1953. Markov dirigera de 1959 jusqu'à sa disparition, le Département de Logique Mathématique de l'université de Moscou. Il fut membre de l'Institut mathématique de l'Académie des sciences.

Markov (junior) est le fondateur de l'école russe de logique et de mathématiques constructives. Les principaux domaines de sa recherche mathématique sont la topologie, l'algèbre topologique, les systèmes dynamiques, la théorie des algorithmes (langages formels, fonctions récursives).

En topologie, en introduisant la notion d'algorithme normal, il prouva l'insolubilité, dans le cas général, du problème de l'homéomorphisme (Insolubility of the problem of homeomorphy, 1958) :

Problème de l'homéomorphisme :

Si X et Y sont deux espaces topologiques, un homéomorphisme (le terme est de Poincaré) entre X et Y est une application bijective et bicontinue (f-1 est continue) de X sur Y. On dit alors que X et Y sont homéomorphes. On définit ainsi une relation d'équivalence et toute propriété vraie dans X le sera dans Y et inversement : invariant topologique. On appelle problème de l'homéomorphisme la question de décider si, étant donnés deux espaces topologiques, ils sont homéomorphes (recherche et construction d'un algorithme).

Le problème des mots (Word problem), posé par Thue en 1914 :

Soit (G,*) un groupe abstrait engendré par une partie H (finie ou non) de ses éléments. Tout élément de G est donc, par définition, un composé fini de la forme g = x1*x2*...*xp, p entier naturel quelconque non nul, composé fini d'éléments ou d'inverses d'éléments de H éventuellement égaux. Un mot, au sens de ce sujet est un p-uplet (x1, x2, ..., xp).

Le problème fut de savoir, problème de Thue (inspiré par celui de Dehn sur l'isomorphie entre groupes abstraits) s'il existe un algorithme susceptible de montrer que deux mots distincts désignent en fait le même élément de G, ce qui revient à la résolution de l'équation m1*m2-1 = e en notant e l'élément neutre du groupe et m2-1 le symétrique de m2 dans G.

Si le groupe G est fini, le problème est trivial. On suppose donc G non fini (il possède une infinité d'éléments). Ce problème relève de la théorie de la décision (» Turing). Le problème fut étudié dans un cadre plus adapté à la démarche algorithmique : une démarche générale se doit de remplacer le groupe étudié par un groupe abstrait qui lui est isomorphe; ainsi tout résultat prouvé pour l'un sera vrai pour l'autre. Or, à un isomorphisme près, tout groupe est isomorphe à un groupe quotient d'un groupe libre.

Andreï A. Markov, On the impossibility of certain algorithms in the theory of associative systems et Emil Post (1897-1954) montrèrent (1947) que le problème est indécidable dans le cas général pour les demi-groupes (monoïdes unifères).

Dans les années 1930/50, des réponses partielles furent obtenues dont une positive pour une certaine classe de groupes à deux éléments générateurs. Piotr Novikov (père) en 1955 puis William Boone (» réf.2) en 1957 (indépendamment et plus simplement) ont montré grâce au nouvel outil que furent les groupes de présentation finie (définies par des systèmes finis de générateurs et de relations de définition) qu'il existe des groupes pour lesquels le problème est indécidable, par inexistence d'un algorithme au sens de Turing de par la non récursivité des relations de définition. Ce qui mettait fin à près d'un demi-siècle de recherches sur le sujet.

Groupes libres, présentation de groupes :  »

 i  William Werner Boone (1920-1983) : mathématicien américain qui étudia à l'université de Princeton auprès de Church et dont la thèse de doctorat dirigée par ce grand logicien et soutenue à Princeton  en 1952 porta sur le fameux word problem sous le titre Several simple and unsolvable problems of group theory related to the word problem. Le sujet l'intéressa tout au long de sa carrière qu'il fit principalement à l'université de l'Illinois (Urbana-Champaign) de 1958 à sa retraite.

 ➔   Pour en savoir un peu plus :

  1. Problème de l'homéomorphisme : on trouvera quelques informations sur ce sujet sur cette page de Francis Lazarus  (CNRS) :
    http://www.gipsa-lab.grenoble-inp.fr/~francis.lazarus/Enseignement/indecidabilite.pdf

  2. Problème des mots : The word problem par William Boone (1958) : http://www.pnas.org/content/44/10/1061.full.pdf

  3. Problèmes de Dehn pour des groupes élémentaires, problème du mot généralisé par Jean-Philippe Préaux, univ Aix-Marseille :
     http://www.i2m.univ-amu.fr/~preaux/PDF/DEA_3.pdf

  4. Problème des mots pour les groupes sur Wikipedia (en) : https://en.wikipedia.org/wiki/Word_problem_for_groups

Kolmogorov  Stone
© Serge Mehl - www.chronomath.com