| Geburt |
20. Februar 1921 Briceva ( d ) ( Königreich Rumänien ) |
|---|---|
| Tod |
19. September 2016(bei 95) Rehovot |
| Beerdigung | Rehovot |
| Staatsangehörigkeit | Rumänisch, dann Sowjet, schließlich Israelisch |
| Ausbildung |
Ion Creanga Staatliche Pädagogische Universität ( en ) Chernivtsi National University |
| Aktivitäten | Mathematiker , Informatiker |
| Arbeitete für | Universität Tel Aviv , Sibirische Abteilung der Russischen Akademie der Wissenschaften (seit1960) |
|---|---|
| Bereiche | Mathematische Logik , Kybernetik |
| Supervisor | Piotr novikov |
| Auszeichnungen | EATCS Award (2011 und 2011) |
| Der Trakhtenbrot Theorem , Lückensatz ( d ) |
Boris Avraamovich Trakhtenbrot (auf Russisch : Борис Авраамович Трахтенброт , auf Hebräisch : בועז טרכטנברוט ), dessen Vorname ebenfalls Boaz ist , geboren am20. Februar 1921im Dorf Briceva (Region Dondușeni in Moldawien , dann in das Königreich Rumänien integriert ) und starb am19. September 2016in Rehovot ( Israel ) ist ein Informatiker, Theoretiker , Logiker und Mathematiker, Rumäne , Sowjet , der Israeli wurde .
Er beendete seine Karriere als Professor an der Universität Tel Aviv .
Trakhtenbrot verteidigte 1950 eine Dissertation ( "Entscheidbarkeitsprobleme für endliche Klassen und Definitionen endlicher Mengen" ) unter der Aufsicht von Pjotr Sergejewitsch Nowikow (en) am Institut für Mathematik der Ukrainischen Akademie der Wissenschaften . In der Sowjetunion arbeitete er zunächst in Penza, etwa 700 km südöstlich von Moskau, dann von Anfang der 1960er bis Ende der 1970er Jahre in der Abteilung für Kybernetik des Instituts für Mathematik der Akademgorodok ( Nowosibirsk ).
Trakhtenbrot wanderte Ende 1980 nach Israel aus. Er war Professor an der Universität Tel Aviv, bis er 1991 in den Ruhestand ging.
Mehrere seiner Werke machen ihn zu einem der Gründerväter der theoretischen Informatik. Er wird als großer Visionär beschrieben, Pionier in verschiedene Richtungen und mit innovativen Konzepten, die im Nachhinein einen großen Einfluss hatten, aber nicht die Resonanz fanden, die sie zu dieser Zeit verdient hatten. Diese Arbeit, die damals in die Kategorie „kybernetisch“ eingestuft wurde, stieß in der UdSSR auf Kritik und Zurückhaltung, sowohl in wissenschaftlicher als auch in politischer Hinsicht.
1964 demonstriert Trakhtenbrot einen grundlegenden Satz in der Komplexitätstheorie , der jetzt als Satz der Lücke Borodin (de) bezeichnet wird (auf Englisch "Gap Theorem", "Gap Theorem" in Perifel). Es wurde im Westen zu dieser Zeit nicht bemerkt und 1972 von Allan Borodin wiederentdeckt ; es trägt jetzt den Namen des zweiten. Der Satz besagt, dass die Hierarchie der Komplexitätsklassen beliebig große Löcher aufweist.
In seiner Diplomarbeit von 1950 demonstriert er das Trakhtenbrot-Theorem der Modelltheorie . Er sagt, dass das Problem der Verifikation bei der Berechnung von Prädikaten der Klasse der endlichen Modelle unentscheidbar ist oder dass die Menge der Formeln erster Ordnung, die in endlichen Strukturen gültig sind, nicht rekursiv aufzählbar ist.
Ende der 1950er Jahre demonstrierten Trakhtenbrot einerseits, J. Büchi und C. Elgot andererseits unabhängig voneinander die Äquivalenz zwischen endlichen Automaten und monadischer Logik zweiter Ordnung (MSO), ein Ergebnis namens Büchi-Elgot- Trakhtenbrot-Theorem.
In den späten 1970er Jahren arbeitete Trakhtenbrot an verschiedenen Wettbewerbskonzepten. Er leistet auch Beiträge in der Theorie endlicher Automaten, der abstrakten Komplexität, der algorithmischen Logik, der Wahrscheinlichkeitsrechnung, der Programmverifikation, der Lambda-Rechnung, der Programmiersemantik, der Typentheorie und der Semantik hybrider oder gleichzeitiger Systeme.
Zu seinen Schülern zählen Janis M. Barzdins, Rusins V. Freivalds, Valery Nepomnyashchy und Vladimir Yu. Sazanov, A. Ja. Dikovsky, Miroslav I. Kratko, Nikolai Beljakin.
2011 erhielt er den EATCS-Preis . Er ist Doktor Honoris Causa von der Universität Jena .
Seine Bücher wurden in viele Sprachen übersetzt, darunter Deutsch und Englisch.