POST EMIL LEON (1897-1954)

Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États-Unis en 1904, Emil Post obtint son Ph.D. à l'université Columbia de New York en 1920. Il était membre de l'American Mathematical Society depuis 1918 et de l'Association for Symbolic Logic dès sa fondation en 1935.

Sa thèse de doctorat, publiée en 1921, porte sur le calcul propositionnel de A. N. Whitehead et B. Russell dont il montre la consistance et le caractère complet. Ici, consistance et complétude sont définies de façon syntaxique. C'est le début de la théorie moderne de la démonstration. (Une théorie est consistante au sens de Post si aucune variable propositionnelle n'est démontrable, et une théorie est complète si toute formule devient démontrable si l'on ajoute aux axiomes une formule non démontrable.) Pour arriver à ces résultats, il utilise cependant la méthode « sémantique » des tables de vérité. Il examine ensuite les logiques à plusieurs valeurs à l'époque où I. Lukasiewicz étudiait, de façon plus philosophique que mathématique, les logiques à trois valeurs. En 1925, poursuivant les travaux de sa thèse, il cherche à montrer le caractère incomplet du système des Principia Mathematica de Russell et Whitehead. Les résultats qu'il obtient ainsi sont contenus dans ceux que K. Gödel et A. Church obtiendront dans les années 1930. Ses principaux travaux sont ensuite consacrés à l'étude des processus effectifs que l'on rencontre en mathématiques.

Ainsi, en 1947, il résout, en même temps que A. A. Markov, le problème posé par A. Thue en 1914 de savoir s'il existe un algorithme permettant de décider, étant donné un mot sur un alphabet fini et un système fini de relations entre des mots sur cet alphabet, si le mot donné est équivalent à l'identité dans le monoïde quotient du monoïde libre par la plus petite congruence compatible avec les relations données.

Pour montrer qu'il n'existe pas de tel algorithme, il introduit ce que l'on appelle les systèmes de Post, grâce auxquels on peut exprimer (comme avec les machines de Turing, les algorithmes de Markov, etc.) le calcul de n'importe quelle fonction récursive. Ce résultat de Post est équivalent à la non-résolubilité du problème des mots, que l'on peut formuler de la façon suivante : soient L(X) et L(Y) deux monoïdes libres ayant un nombre fini de générateurs. Dès que [X] ≥ 3, il n'existe pas d'algorithme permettant de décider si deux morphismes (f, g) de L(X) vers (Y) ont une solution commune (un z ∈ L(X) tel que f(z) = g(z) ; f et g sont donnés par leurs valeurs sur X). Ce résultat de Post a été affiné par M. L. Minsky en 1966, qui considère le cas où f est épimorphisme (Post-Tag problem), et enfin par Y. Lecerf en 1967, qui impose à f et g d'être tous les deux des épimorphismes.

Ce sont ces différents résultats d'indécidabilité qui sont à la base de ceux que l'on rencontre dans la théorie des grammaires formelles.

Pour terminer, indiquons ce que W. Quine écrivait en 1954 à l'occasion de la mort de Post : « Le concept de fonction récursive, concept mathématique précis rendant compte de la notion de calculabilité, fut découvert indépendamment et sous des formes différentes par quatre mathématiciens et Post fut l'un d'entre eux », et, en 1972, W. Quine ajoutait : « La théorie des fonctions récursives dont Post fut un des cofondateurs est deux fois plus âgée qu'en 1954 ; elle a bien montré, depuis, quel champ fertile elle est. »

— Bernard JAULIN