| Naștere |
20 februarie 1921 Briceva ( d ) ( Regatul României ) |
|---|---|
| Moarte |
19 septembrie 2016(la 95 de ani) Rehovot |
| Înmormântare | Rehovot |
| Naţionalitate | Român, apoi sovietic, în cele din urmă israelian |
| Instruire |
Universitatea Pedagogică de Stat Ion Creangă ( ro ) Universitatea Națională Cernăuți |
| Activități | Matematician , informatician |
| Lucrat pentru | Universitatea din Tel Aviv , Divizia Siberiană a Academiei de Științe din Rusia (din1960) |
|---|---|
| Zone | Logică matematică , cibernetică |
| Supervizor | Piotr novikov |
| Premii | Premiul EATCS (2011 și 2011) |
| Trakhtenbrot lui teorema , decalaj teorema ( d ) |
Boris Avraamovich Trakhtenbrot (în rusă : Борис Авраамович Трахтенброт , în ebraică : בועז טרכטנברוט ), al cărui prenume este și Boaz , născut pe20 februarie 1921în satul Briceva ( raionul Dondușeni , în Moldova , apoi integrat în regatul României ), și a murit la19 septembrie 2016în Rehovot ( Israel ), este informatician, teoretician , logician și matematician, român , sovietic , devenit israelian .
Și-a încheiat cariera ca profesor la Universitatea din Tel Aviv .
Trakhtenbrot a susținut în 1950 o teză ( „Probleme de decizie pentru clasele finite și definițiile seturilor finite” ) sub supravegherea lui Pyotr Sergeyevich Novikov (ro) la Institutul de matematică al Academiei ucrainene de științe . În Uniunea Sovietică, a lucrat mai întâi la Penza, la aproximativ 700 km sud-est de Moscova, apoi de la începutul anilor 1960 și până la sfârșitul anilor 1970, în departamentul de cibernetică al institutului de matematică din Akademgorodok ( Novosibirsk ).
Trakhtenbrot a emigrat în Israel la sfârșitul anului 1980. A fost profesor la Universitatea Tel Aviv până în 1991, când s-a retras.
Câteva dintre lucrările sale îl fac unul dintre părinții fondatori ai informaticii teoretice. El este descris ca un mare vizionar, pionier în multe direcții și care introduce concepte inovatoare care au avut un impact uriaș retrospectiv, dar care nu au găsit ecoul pe care îl meritau la acea vreme. Această lucrare, clasificată apoi în categoria „cibernetică”, a întâmpinat critici și reticențe în URSS, atât științifice, cât și politice.
În 1964 Trakhtenbrot demonstrează o teoremă fundamentală în teoria complexității , numită acum teorema gap-ului Borodin (de) (în engleză „gap theorem”, „gap theorem” în Perifel). Nu a fost observat în Occident la acea vreme și a fost redescoperit în 1972 de Allan Borodin ; acum poartă numele celui de-al doilea. Teorema spune că există ierarhii mari în mod arbitrar în ierarhia claselor de complexitate.
În teza sa din 1950, el demonstrează ce este teorema lui Trakhtenbrot a teoriei modelelor . El spune că problema verificării în calculul predicatelor din clasa modelelor finite este indecidabilă sau, în mod echivalent, că setul de formule de ordinul întâi care sunt valide în structurile finite nu este recursiv enumerabil.
La sfârșitul anilor 1950, Trakhtenbrot, pe de o parte, J. Büchi și C. Elgot, pe de altă parte, demonstrează independent echivalența dintre automatele finite și logica monadică de ordinul doi (MSO), rezultat numit Büchi-Elgot- Teorema lui Trakhtenbrot.
La sfârșitul anilor 1970, Trakhtenbrot lucra la diferite concepte de concurență. De asemenea, contribuie la teoria automatelor finite, complexitatea abstractă, logica algoritmică, calculul probabilistic, verificarea programului, calculul lambda, semantica programării, teoria tipurilor, semantica sistemelor hibride sau concurente.
Printre studenții săi se numără Janis M. Barzdins, Rusins V. Freivalds, Valery Nepomnyashchy, Vladimir Yu. Sazanov, A. Ja. Dikovsky, Miroslav I. Kratko, Nikolai Beljakin.
În 2011, a primit premiul EATCS . Este doctor Honoris Causa al Universității din Jena .
Cărțile sale au fost traduse în multe limbi, inclusiv germană și engleză.