Boris Trakhtenbrot

Boris Abramovich Trakhtenbrot was a Russian-Israeli mathematician and computer scientist, born in 1921 in Bessarabia, who specialized in logic, algorithms, the theory of computation, and cybernetics. He discovered the gap theorem in computational complexity in 1964 and proved what is known as Trakhtenbrot's theorem in model theory and computability theory. He worked for many years at Akademgorodok in Novosibirsk before immigrating to Israel in 1981, where he became a professor at Tel Aviv University and later professor emeritus; he received the EATCS Award in 2011 and died in 2016.