Boris Avraamovich Trakhtenbrot

Quick Info

20 February 1921
Briceva, Northern Bessarabia (now Moldova)
19 September 2016
Tel Aviv, Israel

Boris Trakhtenbrot was an Moldovan-born Russian mathematician who worked in logic, algorithms, theory of computation and cybernetics.


Boris Trakhtenbrot's first name is sometimes written Boaz, his middle name sometimes appears as Abramovich and his last name is sometimes transliterated as Trahtenbrot, Trachtenbrot or Trajhtenbrot. The village of Briceva or Brichevo in which he was born, mainly housing Jewish agricultural workers and their families, was close to the towns of Balti and Soroca. He was born into a Jewish family. It was in Briceva that he attended primary school but for his secondary schooling he was required to go to one of the larger nearby towns and he studied at schools in both Balti and Soroca. He wrote [13]:-
I was fortunate to have very good teachers of mathematics. My success in learning, and especially in mathematics, was echoed by the benevolence of the teachers and the indulgence of my fellow pupils. The latter was even more important to me, since it, to some degree, compensated for the discomfort and awkwardness caused by my poor vision.
On 1 September 1939 World War II began when German troops invaded Poland. This was the year that Trakhtenbrot graduated from high school. The Molotov-Ribbentrop non-aggression pact between Germany and the Soviet Union meant that initially the war had little effect on life in the Soviet Union and Trakhtenbrot continued with his education. However, it led to major political changes which saw Bessarabia become part of the Moldavian Soviet Socialist Republic on 2 August 1940. Having completed his secondary education, in 1940 he entered the Faculty of Physics and Mathematics of the Moldavian Pedagogical Institute in Kishinev. This new institution, which only opened in August 1940, was designed to train school teachers. Trakhtenbrot writes [13]:-
The curriculum covered a standard spectrum of teachers' training topics. In particular, mathematical courses presented basics in Calculus, Linear Algebra and Algebra of Polynomials, Analytical Geometry, Projective Geometry, Foundations of Geometry (including Lobachevsky Geometry), Elements of Set Theory and Number Theory.
On 8 November 1940, shortly after he began his studies, the area was struck by the powerful Vrancea earthquake which caused devastation across large areas of Moldova. Substantial damage occurred in Kishinev, the major city of Moldova. As if this was not trouble enough, things got much worse for Moldova on 22 June 1941 when Germany broke the non-aggression pact and invaded the Soviet Union. There was no time to even realise what was happening for, on that day, German bombers attacked Kishinev and bombs fell close to the Moldavian Pedagogical Institute campus. Continual bombing raids saw much of the city in flames and Trakhtenbrot fled from Kishinev in early July before the city fell to the advancing German troops on 14 July. We mentioned above his eyesight problems and these meant that he was not required to serve in the military. He writes [13]:-
... after many mishaps, [I] arrived as a refugee in Chkalov (now Orenburg) on the Ural River. Here, I enrolled in the local pedagogic institute. A year later we moved to Buguruslan in the Chkalov region, to where the Kishinev Institute was evacuated to in order to train personnel for the forthcoming return home as soon as our region would be liberated. Almost all the lecturers were former high school teachers - skilled people whose interests lay in the pedagogic aspects of mathematics and physics. ... Nikolai S Titov, a former Ph.D. student of Moscow University, who happened to flee to Buguruslan, lectured on Set Theory. I was deeply impressed by the beauty and novelty of this theory. Unfortunately, this was only a transient episode in those hard and anxious days. Actually, during the war years 1941-1944, my studies were irregular, being combined with employment in a felt boot factory, a storehouse and, finally, in the Kuybyshev-Buguruslan Gas Trust. In August 1944 the institute was evacuated to Kishinev and I returned to my native regions ...
Back in Kishinev, Trakhtenbrot qualified as a secondary school teacher of mathematics in 1945. The years of war had meant that he was approaching 25 years of age before obtaining this qualification but, nevertheless, he decided that he wanted to continue his study of mathematics. He enrolled for a Master's Degree at the University of Chernovtsy, in the Ukraine, in September 1945. There he attended lectures by Alexander A Bobrov, whose course on set theory, based on Felix Hausdorff's book on that topic, made him feel that this was a subject on which he would like to do research. He made a visit to Lviv University to meet Andrey Kolmogorov which proved useful, despite Kolmogorov cancelling his trip, since he was able to have discussions with Boris Gnedenko who advised him to contact Piotr Sergeevich Novikov and Alexey Andreevich Lyapunov (1911-1973). Around this time he met Berta Isakovna Rabinovich (1921-2013) whom he married in 1947. Berta:-
... lovingly, selflessly, and steadfastly supported Boaz "through fire and water". Berta was also a motherly figure for his many students, whom she always welcomed warmly and for whom she invariably prepared the most delicious meals.
Boris and Berta Trakhtenbrot had two sons, Mark (born 1950) and Yossef (born 1952). Mark Trakhtenbrot became a computer scientist and was a member of the team that received the ACM Software System Award in 2007 for Statemate. Let us return to Trakhtenbrot's time at Chernovtsy and his wish to continue to doctoral studies.

Two visits to Moscow led to Novikov agreeing to supervise Trakhtenbrot's doctoral dissertation which he began in October 1947 in the Kiev Mathematical Institute of the Ukrainian Academy of Sciences. He wrote [14]:-
My first acquaintance with S A Yanovskaya occurred in 1947 at the seminar she ran together with P S Novikov. Having graduated from the Chernovtsy University, I had just started my Ph.D. studies at the Kiev Mathematical Institute of the Ukrainian Academy of Sciences. The director of the institute, M A Lavrentev, approved my petition to specialize in mathematical logic under P S Novikov, who held a permanent position at the Moscow Mathematical Institute of the USSR Academy. It was also agreed to grant me long-term scientific visits to Moscow where I would stay with my advisor. At that time departments of mathematical logic did not yet exist in the USSR and the Yanovskaya-Novikov research seminar "Mathematical Logic and Philosophical Problems of Mathematics" was the main medium in which research and concomitant activities in the area were conducted. ... The atmosphere dominating the meetings of the seminar was democratic and informal. Everybody, including the students, felt and behaved at ease without strong regulations and formal respect for rank. For me - a graduate of a provincial university, this seemed quite unusual; I was happy to acquire these habits and later to promote them at my own seminars.
Trakhtenbrot was awarded his doctorate in 1950 for his thesis Decidability Problems for Finite Classes and Definitions of Finite Sets. Here are two major results from that thesis:
  1. There is no algorithm which decides for an arbitrary given formula of the first-order logic of predicates whether this formula has or does not have a finite interpretation.
  2. In each "elementary axiomatisable" set theory there exist two definitions of finite set whose equivalence can neither be proved nor refuted in this theory.
He published his first paper, The impossibility of an algorithm for the decidability problem on finite classes, in Doklady in 1950. Haskell Curry writes in a review:-
The author asserts that there does not exist any general recursive algorithm for deciding whether a formula of the restricted functional calculus is true in every finite domain. This is related to Church's result that no such algorithm exists for deciding whether a formula is derivable (and hence true in every domain, finite or infinite). ... An application to the theory of finite sets is mentioned.
On 5 December 1950, after the defence of his thesis, Trakhtenbrot moved to Penza, about 700 km south east of Moscow, for a position at the Belinski Pedagogical Institute. However, there were problems as soon as he arrived. He wrote to Alexey Lyapunov on 13 December:-
Dear Alexey, arrived safely in Penza and have already begun work. I have trouble with the flat (as usual, it was promised but not given), and I will have a decisive conversation with the boss ... If I knew that I still have some opportunity to go elsewhere, I would even leave Penza, if they do not resolve the housing problem ...
His arrival in Penza is described in [12]:-
... the new Ph.D. Trakhtenbrot, who arrived in 1950 in the University at Penza, was certainly not of proletarian background - a Jew who spoke eight languages, whose research was decidedly abstract and "pure", and who, if his present manner may accurately be extrapolated back over fifty years, must have seemed to the casual observer an easy fit to the stereotype of an absent-minded professor. Whispered accusations of bourgeois idealism were heard: in that era of Stalinist paranoia they were gravely threatening.
The "gravely threatening" accusations against Trakhtenbrot were based on his research topics and on the seminars that he gave. He gives a very full account of this "Penza Affair" in [14]. Let us give an indication here what the affair was about.

In three issues of Pravda in June, July and August 1950 Stalin published Marxism and Problems of Linguistics. This led to academics criticising the work of others, particularly to see if it complied with Communist thinking. The foundations of mathematics had already been an area where certain works were considered contrary to such thinking, for example Hilbert's ideas that mathematics could be completely built on sets of provably consistent axioms were considered "correct" but Gödel's incompleteness, Russell's set paradoxes and Tarski's logic were all considered "wrong". In fact Russell had been labelled a warmonger and Tarski as a militant bourgeois. When Trakhtenbrot delivered his first lecture at Penza, The Method of Symbolic Calculi in Mathematics, to his fellow mathematicians, in which he talked about results from his thesis, he was denounced as "an idealist of Carnapian variety." In further lectures throughout 1951 he tried to undo the damage but the attacks on him being an idealist only became worse. Here is an extract from a letter he received from one of his colleagues in June 1951 (see [14]):-
The lecturer circumvents philosophical problems. He does not criticize the bourgeois idealists, who parasitize on mathematical logic (Russell, Tarski and others). The lecturer persistently holds a neutral position in the dispute between materialism and idealism in mathematical logic, deliberately avoiding the subjects broached in his lectures. The very term "good formula" is not appropriate: a formula which is good for the capitalist is bad for us. I asked you several times and you always replied that you chose basic formulas and arbitrary transformations, that you did not apply any restrictions. What drives you to cling to this freedom? Holding on to it you reveal yourself as an idealist.
Trakhtenbrot replied to these criticisms (see [14] for copies of his replies) and some leading mathematicians such as P S Novikov and A A Lyapunov, and to a lesser extent A N Kolmogorov and A G Kurosh, all came to his defence. Trakhtenbrot explains that he learnt to play the game of attacking "vulgarisers of Marxism" to make himself acceptable. However, the affair had consequences and he wrote to Alexey Lyapunov on 2 February 1952:-
Dear, dear Alexey. I thought that I would be able to travel to Moscow for the holidays, but the exacerbation of my stomach illness will not allow me. This aggravation is due, apparently, in part, to the unrest and feelings of relentless persecution that I abundantly receive from the Head of the Department of Mathematics. The story of "idealism" has received wide publicity in the Institute; the feisty nature of the case became more and more pronounced. I gave a talk at the Department of Marxism-Leninism, and they liked my report. The Department determined that "there is no idealism in this symbolic calculus" ... Finally, on 31 January after a meeting of the Academic Council, I was informed that the management and the party organization of the Institute had investigated the case and concluded that in my reports, and in my work there is no idealism ... I'm incredibly tired of all these squabbles ... In general, this year for me is lost in a senseless fight with windmills ... .
In a similar vein, he wrote in [14]:-
My health was undermined by permanent tension, dread and a hard teaching load (often more than 20 hours weekly). It goes without saying that for about two years I was unable to dedicate time to research. In those circumstances it was the selfless care and support of my wife Berta that saved me from collapse. I should also mention the beneficial and calming effect of the charming central Russian landscape which surrounded our dwelling.
In fact he only published one paper between 1950 and 1955, namely On recursive separability (1953). Haskell Curry writes in a review of that paper:-
It is well known that there is an analogy between the theory of recursive functions and the theory of analytic sets; further that this analogy breaks down in that it is possible to have two disjoint recursively enumerable sets which cannot be separated by a recursive set. The author shows that the set of all identically true formulas of the first-order predicate calculus and the set of all formulas refutable in some finite domain give rise (by a Gödel enumeration) to such a pair of recursively inseparable sets.
From 1950 to 1960 Trakhtenbrot worked in Penza, both at the Belinski Pedagogical Institute and at the Penza Industrial Institute which was renamed the Penza Polytechnical Institute in 1958. In 1960 he moved to the Siberian branch of the Mathematical Institute of the USSR Academy of Sciences, the Akademgorodok, near Novosibirsk. This had been established in 1957 by Mikhail Alekseevich Lavrentev, Sergei Lvovich Sobolev and Sergey Alekseyevich Khristianovich (1908-2000) with Lavrentev as its founding chairman. Trakhtenbrot was based in Novosibirsk and in that city he also taught at the State University. He worked there until December 1980 when he left and emigrated to Israel. He was appointed as a professor at Tel Aviv University from 1 January 1981.

We have said little about Trakhtenbrot's remarkable contributions. For some extracts from reviews of some of his books, see THIS LINK.

We quote from [3] to give an overview of his contributions:-
He is unmatched in combining farsighted vision, unfaltering commitment, masterful command of the field, technical virtuosity, aesthetic expression, eloquent clarity, and creative vigour with humility and devotion to students and colleagues. For over half a century, Trakhtenbrot has been making seminal contributions to virtually all of the central aspects of theoretical computer science, inaugurating numerous new areas of investigation. He has displayed an almost prophetic ability to foresee directions that are destined to take centre stage, a decade or more before anyone else takes notice. He has never been tempted to slow down or limit his research to areas of endeavour in which he has already earned recognition and honour. Rather, he continues to probe the limits and position himself at the vanguard of a rapidly developing field, while remaining, as always, unassuming and open-minded. ... The list of topics upon which Trakhtrenbrot has made a lasting impression is breathtaking in its scope: 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 much more. Despite this prolificacy of subjects, the entire body of his work demonstrates the same unique melding of supreme mathematical prowess, with profound depth and thoroughness.
In June 1991 "An International Symposium on Theoretical Computer Science in honour of Boris A Trakhtenbrot on the occasion of his Retirement and Seventieth Birthday" took place in Tel Aviv. On Friday, 28 April 2006, the School of Computer Science at Tel Aviv University held a "Computation Day Celebrating Boaz (Boris) Trakhtenbrot's Eighty-Fifth Birthday". The book [1] was produced to celebrate this 85th birthday. In 2011, the European Association for Theoretical Computer Science awarded Trakhtenbrot, then about to turn 90, its annual Distinguished Achievements Award.

References (show)

  1. A Avron, N Dershowitz and A Rabinovich (eds.) Pillars of Computer Science. Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday (Springer-Verlag, Berlin-Heidelberg, 2008).
  2. B A Trakhtenbrot, Selected developments in Soviet mathematical cybernetics (Delphic Associates, 1986).
  3. A Avron, N Dershowitz and A Rabinovich, Preface, in A Avron, N Dershowitz and A Rabinovich (eds.) Pillars of Computer Science. Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday (Springer-Verlag, Berlin-Heidelberg, 2008), ix-xv.
  4. A Avron, N Dershowitz and A Rabinovich, Boris A Trakhtenbrot: Academic Genealogy and Publications, in A Avron, N Dershowitz and A Rabinovich (eds.) Pillars of Computer Science. Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday (Springer-Verlag, Berlin-Heidelberg, 2008), 46-57.
  5. A Church, Review: Algorithms and Automatic Computing Machines, by B A Trakhtenbrot, The Journal of Symbolic Logic 28 (1) (1963), 104-105.
  6. M Davis, Review: Introduction to the Theory of Finite Automata, by N E Kobrinskii and B A Trakhtenbrot, Mathematics of Computation 21 (97) (1967), 122.
  7. L M Fisher, In Memoriam: Boris Trakhtenbrot, 1921-2016, Association for Computing Machinery (21 September 2016).
  8. F E Hohn, Review: Algorithms and Automatic Computing Machines, 'Topics in Mathematics' by B A Trakhtenbrot, The Mathematics Teacher 57 (4) (1964), 255-256.
  9. G Longo, Review: Comparing the Church and Turing Approaches: Two Prophetical Messages, by Boris Trakhtenbrot, The Journal of Symbolic Logic 59 (4) (1994), 1434-1436.
  10. R McNaughton, Review: Finite Automata. Behavior and Synthesis. by B A Trakhtenbrot and Ya M Barzdin, The Journal of Symbolic Logic 42 (1) (1977), 111-112.
  11. R McNaughton, Review: Introduction to the Theory of Finite Automata, by N E Kobrinskii and B A Trakhtenbrot, The Journal of Symbolic Logic 33 (3) (1968), 466.
  12. A R Meyer, Reminiscences, in A Avron, N Dershowitz and A Rabinovich (eds.) Pillars of Computer Science. Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday (Springer-Verlag, Berlin-Heidelberg, 2008), 39-45.
  13. B A Trakhtenbrot, From Logic to Theoretical Computer Science - An Update, in A Avron, N Dershowitz and A Rabinovich (eds.) Pillars of Computer Science. Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday (Springer-Verlag, Berlin-Heidelberg, 2008), 1-38.
  14. B A Trakhtenbrot, In memory of S A Yanovskaya (1896-1966) on the centenary of her birth, Modern Logic 7 (2) (1997), 160-187.

Additional Resources (show)

Other pages about Boris Trakhtenbrot:

  1. Reviews of Boris Trakhtenbrot's books

Other websites about Boris Trakhtenbrot:

  1. Mathematical Genealogy Project
  2. MathSciNet Author profile
  3. zbMATH entry

Written by J J O'Connor and E F Robertson
Last Update February 2017