[FOM] Boris (Boaz) Trakhtenbrot 1921-2016

[Arnon Avron]

Boris (Boaz) Abramovich Trakhtenbrot,  founding father of computer science, 
passed away September 19, 2016 at age 95, in Rehovot, Israel.  His beloved wife, 
Berta (née Rabinovich), died three years prior.  He is survived by two sons, 
Mark Trakhtenbrot and Yosef Halakhmi, five grandchildren, and two great-grandchildren.

Trakhtenbrot was born in Brichevo, a shtetl in Northern Bessarabia (now Moldova), 
about which he always spoke fondly.  He studied at the Moldavian Pedagogical 
Institute in Kishinev, Chernivtsi National University (Ukraine), Kiev Mathematical 
Institute (Ukraine), and (unofficially) at Moscow University.  After completing his 
doctorate in 1950, under Petr S. Novikov, he took a position at the Belinsky 
Pedagogical Institute in Penza (Western Russia), and later - in 1960 - joined the 
just-established Mathematical Institute at Novosibirsk Akademgorodok, where he 
established and headed the Theory of Automata and Mathematical Linguistics 
Department.  He received a Doctor of Sciences degree in 1962.

Boris suffered much under the Stalin-plagued era, with its persecution of "idealists"
"cosmopolitans", and the like.  Moreover, the official mathematical establishment was 
hostile to logic and computer science at the time.  While residing in the USSR, 
he was barred from attending international congresses in the West 
to which he had been invited.  

In 1980, Boris immigrated to Israel and joined Tel Aviv University's School 
of Mathematical Sciences.  There he was instrumental in the major growth phase 
of its computer science department.  He remained vitally active for many years 
after his official retirement in 1991.

Today, Boaz is universally admired as a founding father and long-standing 
pillar of the discipline of computer science.  He was the field's pre-eminent 
distinguished researcher, and a most illustrious trailblazer and disseminator.  
He made very many deeply significant contributions to theoretical computer science, 
on decidability problems in logic, finite automata theory, the connection between 
automata and monadic second-order logic, complexity of algorithms, 
abstract complexity, algorithmic logic, probabilistic computation, 
program verification, the lambda calculus and foundations of programming languages, 
programming semantics, semantics and methodology for concurrency, networks, 
hybrid systems, and more.  He was unmatched in combining farsighted vision, 
unfaltering commitment, masterful command of the field, technical virtuoso, 
aesthetic expression, eloquent clarity, and creative vigor with humility and 
devotion to students and colleagues.

No fewer than three famous theorems in logic and
theoretical computer science bear Trakhtenbrot's name:

Trakhtenbrot's Theorem (1950): The validity of first-order statements that hold 
true for all finite universes is undecidable.

The Büchi-Elgot-Trakhtenbrot Theore (1962): Finite automata and weak
 monadic second-order logic have the same expressive power.

The Borodin-Trakhtenbrot Gap Theorem (1964): There are arbitrarily large 
computable gaps in the hierarchy of complexity classes.

Trakhtenbrot's doctoral dissertation inaugurated finite model theory.  
His subsequent Novosibirsk period was very productive; his regular seminar 
there was legendary.  He introduced the use of monadic second-order logic 
as a specification formalism for the infinite behavior of finite automata.  
This logic has turned out to be very fundamental; various temporal logics are 
just "sugared" fragments of monadic logic.  And he was among the very first 
to consider time and space efficiency of algorithms (using what he called 
"signalizing functions") and to speak about abstract complexity measures 
(independently and in parallel with similar developments by Western theoreticians).  

Trakhtenbrot initiated the study of topological aspects of \omega-languages 
and operators and provided a characterization of operators computable by 
finite automata. Furthermore, he supplied solutions to special cases of the 
Church synthesis problem, later solved by Büchi and Landweber.The equivalence 
with automata and the solvability of Church's problem laid the necessary 
underpinnings for the development of formalisms for describing interactive 
systems and their properties.  These have led to tools for algorithmic verification 
and automatic synthesis of correct implementations and for the advanced 
algorithmic techniques that are now embodied in industrial tools for verification 
and validation.

His justly famous and truly elegant Gap Theorem (proved independently by Allan 
Borodin in the West) and his development of the "crossing sequence" method were 
groundbreaking.  His paper on "auto-reducibility" provided a turning point in 
abstract complexity.  In the USSR, these works quickly became very influential, 
and, in the US, complexity took over as the central preoccupation of 
theoretical computer science.

Trakhtenbrot was at the same time a master pedagogue and expositor.  His book, 
Algorithms and Automatic Computing Machines, first written in Russian in 1957, 
was translated into English and a dozen other languages, and is recognized 
worldwide as the first important text in the field.  He played the key role in 
the dissemination of Soviet computer science research in the West, writing 
surveys on such topics as Soviet approaches to brute force search (perebor). 

His later works dealt with various aspects of concurrency, including data 
flow networks, Petri nets, partial-order versus branching-time equivalence, 
bi-simulation, real-time automata, and hybrid systems.  All told, he published 
some one hundred articles, books, and monographs.

For over half a century, Trakhtenbrot has been making seminal contributions to 
virtually all of the central aspects of theoretical computer science, inaugurating 
numerous brand-new areas of investigation....  The entire body of his work 
demonstrates the same unique melding of supreme mathematical prowess, combined 
with profound depth and thoroughness.  His operative style has always been 
patient in-depth survey of existing literature, uncompromising evaluation and 
critical comparison of existing approaches, followed by extraordinary and 
prescient contributions.

Trakhtenbrot's contributions are astounding under any measure; how much more 
so when consideration is given to the fact that he worked under very adverse 
conditions: persecution, lack of support, almost no access to foreign meetings, 
and so on.  His undaunted spirit should serve as an inspiration to all.

His wisdom, courage, and generosity will be sorely missed.