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.

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.

... 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 ...

... 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.

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.

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.

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.

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 ...

... 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 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.

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 ... .

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.

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.

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.