Boris (Boaz) Abramovich Trakhtenbrot (Russian: Борис Авраамович Трахтенброт, Hebrew: בועז טרכטנברוט; 19 February 1921 – 19 September 2016) was a Russian-Israeli mathematician in logic, algorithms, theory of computation, and cybernetics.

Boris Trakhtenbrot
1994
Born(1921-02-19)19 February 1921
Died19 September 2016(2016-09-19) (aged 95)
Rehovot, Israel
Spouse
Berta I. Rabinovich
(m. 1947; died 2013)
Academic background
Alma materUkrainian Academy of Science
ThesisDecidability Problems for Finite Classes and Definitions of Finite Sets (1950)
Doctoral advisorPyotr Novikov
Academic work
Institutions

Biography

edit

Trakhtenbrot was born into a Jewish family in Brichevo, northern Bessarabia (now Tîrnova, Moldova).[1] He studied at the Moldovan State Pedagogical Institute in Kishinev, Chernivtsi University, and the Ukrainian Academy of Science's Mathematical Institute, completing a Ph.D. at the latter institution in 1950.[2]

He worked at Akademgorodok, Novosibirsk during the 1960s and 1970s.[3][4] In 1964 Trakhtenbrot discovered and proved a fundamental result in theoretical computer science called the gap theorem.[5] He also discovered and proved the theorem in logic, model theory, and computability theory now known as Trakhtenbrot's theorem.[6]

After immigrating to Israel in 1981, he became a professor in the Faculty of Exact Sciences at Tel Aviv University, and continued as professor emeritus until his death. He died on 19 September 2016, at the age of 95.[2][7]

Notes

edit
  1. ^ "Surnames starting with the letter T". Russian Jewish Encyclopedia. Translated by Charny, Josif; Charny, Vitaly. Moscow. 1995. Archived from the original on 15 April 2003.{{cite encyclopedia}}: CS1 maint: location missing publisher (link)
  2. ^ a b "Boaz (Boris) Trakhtenbrot, 1921–2016". Faculty of Exact Sciences. Tel Aviv University. Archived from the original on 6 March 2021.
  3. ^ Борис Абрамович Трахтенброт [Boris A. Trakhtenbrot]. Архив академика А.П. Ершова (in Russian). Archived from the original on 26 July 2011.
  4. ^ "History of Computing in Russia" Борис Авраамович Трахтенброт [Boris Avraamovich Trahtenbrot] (in Russian). Archived from the original on 29 April 2008. Retrieved 22 January 2008.
  5. ^ Boris Trakhtenbrot (1964). "Turing computations with logarithmic delay". Algebra and Logic (in Russian). 3 (4): 33–48.
  6. ^ Boris Trakhtenbrot (1950). "The Impossibility of an Algorithm for the Decidability Problem on Finite Classes". Proceedings of the USSR Academy of Sciences (in Russian). 70 (4): 569–572.
  7. ^ Fisher, Lawrence M. (21 September 2016). "In Memoriam: Boris Trakhtenbrot, 1921-2016". Communications of the ACM. Association for Computing Machinery.
edit