# Boris Trakhtenbrot

Boris Avraamovitch Trakhtenbrot (en russe : Борис Авраамович Трахтенброт, en hébreu : בועז טרכטנברוט), dont le prénom est aussi Boaz, né le 20 février 1921$^,$ dans le village de Briceva (raion de Dondușeni, en Moldavie, alors intégré au royaume de Roumanie), et mort le 19 septembre 2016 à Rehovot (Israël), est un informaticien théoricien, logicien et mathématicien roumain, soviétique, devenu israélien.
Il termine sa carrière comme professeur à l'université de Tel Aviv.

## Biographie

Trakhtenbrot soutient en 1950 une thèse (« Decidability Problems for Finite Classes and Deﬁnitions of Finite Sets ») sous la direction de Pyotr Sergeyevich Novikov (en) à l'Institut de mathématiques de l'Académie ukrainienne des sciences. En Union soviétique, il travaille d'abord à Penza, à environ 700 km au sud-est de Moscou, puis à partir du début des années 1960 et jusqu'à la fin des années 1970, au département de cybernétique de l'institut de mathématiques de Akademgorodok (Novossibirsk).
Trakhtenbrot émigre en Israël fin 1980. Il est professeur à l'université de Tel Aviv jusqu'en 1991, où il prend sa retraite.

## Œuvre

Plusieurs de ses travaux en font un des pères fondateurs de l'informatique théorique. Il est décrit comme un grand visionnaire, pionnier dans plusieurs directions, et introduisant des concepts novateurs qui ont eu un impact considérable rétrospectivement, mais qui n'ont pas trouvé l'écho qu'ils méritaient à l'époque. Ces travaux, alors classés dans la catégorie « cybernétique », rencontraient en URSS des critiques et des réticences, à la fois scientifiques et politiques.
En 1964, Trakhtenbrot démontre un théorème fondamental en théorie de la complexité, appelé maintenant le théorème de la lacune de Borodin (de) (en anglais « gap theorem », « théorème de la lacune » chez Perifel). Il n'a pas été remarqué en Occident à l'époque, et a été redécouvert en 1972 par Allan Borodin; il porte maintenant le nom du second. Le théorème dit qu'il existe des trous arbitrairement grands dans la hiérarchie des classes de complexité.
Dans sa thèse, en 1950, il démontre ce qui est le théorème de Trakhtenbrot de la théorie des modèles. Il dit que le problème de la vérification dans le calcul des prédicats de la classe des modèles finis est indécidable ou, de manière équivalente, que l'ensemble des formules du premier ordre qui sont valides dans des structures finies n'est pas récursivement énumérable.
À la fin des années 1950, Trakhtenbrot d'une part$^,$, J. Büchi et C. Elgot d'autre part$^,$$^,$, démontrent de manière indépendante l'équivalence entre les automates finis et la logique monadique du second ordre (MSO), résultat appelé le théorème de Büchi-Elgot-Trakhtenbrot.
À la fin des années 1970, Trakhtenbrot travaille sur divers concepts de concurrence. Il fait également des contributions en théorie des automates finis, complexité abstrait, logique algorithmique, calcul probabiliste, vérification de programmes, lambda calcul, sémantique de programmation, théorie des types, sémantique des systèmes hybrides ou concurrents.
Parmi ses élèves, on compte Janis M. Barzdins, Rusins V. Freivalds, Valery Nepomnyashchy, Vladimir Yu. Sazanov, A. Ja. Dikovsky, Miroslav I. Kratko, Nikolai Beljakin.

## Prix et distinctions

En 2011, il reçoit le Prix EATCS. Il est docteur honoris causa de l'université d'Iéna.

## Livres (sélection)

Ses livres ont été traduits en de nombreuses langues, notamment en allemand et en anglais.
* (en) Boris A. Trakhtenbrot, Algorithms And Automatic Computing Machines, Boston, Massachucetts, D.C. Heath and Company, 1963, 101 p. (lire en ligne)
* (en) N. E. Kobrinskii et Boris A. Trakhtenbrot, Introduction to the Theory of Finite Automata, Amsterdam, North-Holland, 1965, x+337 (MR 0186454)
* (en) Boris A. Trakhtenbrot et Ya. M. Barzdin, Finite Automata. Behavior and Synthesis, Amsterdam-Londres et New York,, North Holland et American Elsevier Publishing, coll. « Fundamental Studies in Computer Science, Vol. 1. », 1973, xi+321 (MR 0351686)
* I. Yaglom, Boris A. Trakhtenbrot, E. Ventsel et A. Solodovnikov, Nouvelles orientations des mathématiques, Moscou, Édition Mir, coll. « Initiation aux Mathématiques », 1975, 408 p. (MR 0449951) — La deuxième partie contient une version du texte de 1963.