# [FOM] Boris (Boaz) Trakhtenbrot 1921-2016

Arnon Avron aa at tau.ac.il
Sun Oct 2 02:20:43 EDT 2016

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