Scienceבוריס טרכטנברוט

Boris Trakhtenbrot

Boris Trakhtenbrot was a Soviet-born Israeli mathematician and computer scientist who worked in logic, algorithms and the theory of computation.

1921 to 2016Trakhtenbrot's theoremThe gap theoremLogic and theory of computation

Born: 20 February 1921, Briceva
Died: 19 September 2016, Rehovot
Occupation: mathematician, computer scientist, university teacher
Education: Ion Creangă Pedagogical State University, Chernivtsi University, Institute of Mathematics of the National Academy of Sciences of Ukraine

Boris Trakhtenbrot was born in 1921 in Briceva

Trakhtenbrot was born in 1921 into a Jewish family in Brichevo, a village in northern Bessarabia, then part of Romania. He lost his mother at 3. He began learning Hebrew at 7 and was a member of Hashomer Hatzair as a youth.

In 1940 he began studying physics and mathematics at the Moldovan Pedagogical Institute in Kishinev. After the German attack in 1941 he fled to Chkalov and later moved to Buguruslan with the institute. He earned a doctorate in 1950 at the Mathematical Institute in Kiev, under Pyotr Novikov.

He taught in Penza and in 1961 moved to Novosibirsk, where he worked at Akademgorodok. In 1950 he proved the result now called Trakhtenbrot's theorem, and in 1964 he proved the gap theorem in complexity theory. His books on computer science were translated into many languages.

He immigrated to Israel in December 1980 and became a professor at Tel Aviv University, retiring as professor emeritus in 1991. He received the EATCS award in 2011. He died in 2016 and was buried in Rehovot.