Boris Trakhtenbrot ^People

From 1960 to 1980, he conducted research at the Mathematical Institute ofthe USSR Academy of Sciences Siberian branch, and lectured at Novosibirsk StateUniversity in Akademgorodok, Novosibirsk. After immigrating to Israel in 1981, he became a professor of computer science at Tel Aviv University. In the years before hisretirement 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 annualDistinguished Achievements Award. The organization described him asunquestionably 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.