From 1960 to 1980, he conducted research at the Mathematical Institute of the USSR Academy of Sciences Siberian branch, and lectured at Novosibirsk State University in Akademgorodok, Novosibirsk. After immigrating to Israel in 1981, he became a professor of computer science at Tel Aviv University. In the years before his retirement in 1991, he also visited and collaborated with many Western universities and research centers. In 1964, Trakhtenbrot discovered and proved a fundamental result in theoretical computer science called the Gap theorem, regarding the com- plexity of computable functions. He also discovered and proved what is now called Trakhtenbrot's theorem, which states the problem of validity in first-order logic (FO) on the class of al finite models is undecidable, and that the class of valid sen- tences over finite models is not recursivelv enumerable. The theorem was first pub- lished in 1950, in the paper "The Impossibility of an Algorithm for the Decidability Problem on Finite Classes". In 2011, the European Association for Theoretical Computer Science (EATCS) awarded Trakhtenbrot, then about to turn 90, its annual Distinguished Achievements Award. The organization described him as "unquestionably a principal founding father of the discipline of computer science, a preeminent distinguished researcher, and amost illustrious leader and diseminator". as well as "a grand visionary who pioneered many fascinating directions and concepts.