## Reviews of Boris Trakhtenbrot's books

Boris Trakhtenbrot's books have been translated into many languages and there are often several editions.

For example, the first of the books below appeared first in Russian in 1957, then in German translation in 1959, in Japanese translation in 1959, in Polish in 1961, in French translation in 1975 and in Spanish translation in 1977.

The second book below appeared in Russian (1960), Czech (translation from Russian) (1963), French (translation from Russian) (1963), Bulgarian (translation from Russian) (1963), English (translation from Russian) (1963), Japanese (translation from Russian) (1964), Italian (translation from English) (1964), Turkish (translation from Russian) (1964), and Spanish (translation from Russian) (1964).

We have put our short extracts of reviews of the same book together although, in some cases, the review is of a different language edition.

For example, the first of the books below appeared first in Russian in 1957, then in German translation in 1959, in Japanese translation in 1959, in Polish in 1961, in French translation in 1975 and in Spanish translation in 1977.

The second book below appeared in Russian (1960), Czech (translation from Russian) (1963), French (translation from Russian) (1963), Bulgarian (translation from Russian) (1963), English (translation from Russian) (1963), Japanese (translation from Russian) (1964), Italian (translation from English) (1964), Turkish (translation from Russian) (1964), and Spanish (translation from Russian) (1964).

We have put our short extracts of reviews of the same book together although, in some cases, the review is of a different language edition.

**1. Algorithms and machine solution of problems (Russian) (1957), by B A Trakhtenbrot.**

**1.1. Review by: Walter Gautschi.**

*Mathematical Reviews*MR0120149

**(22 #10906)**.

A popular exposition of recursive function theory with the following section headings: numerical algorithms, game algorithms, algorithms for searching a path in a labyrinth, word problem, computing machine with automatic control, program (machine algorithm), necessity of defining more precisely the concept of algorithm, Turing machine, realization of an algorithm on a Turing machine, basic hypothesis of the theory of algorithms, universal Turing machine, algorithmically unsolvable problems, impossibility of an algorithm for the problem of equivalence of words.

**2. Algorithms and Automatic Computing Machines (1960), by B A Trakhtenbrot.**

**2.1. Review by: Alonzo Church.**

*The Journal of Symbolic Logic*

**28**(1) (1963), 104-105.

This is an English translation of the second edition of Trakhtenbrot's booklet and is one of a series of translations from the Russian series, "Popular lectures in mathematics," which are being prepared under a project at the University of Chicago. The popular character of the exposition means in the present case that no knowledge of mathematics beyond intermediate algebra is presupposed. But, as the translators explain in their preface, there are several passages in which the reader is expected to follow a rather complex train of logical inference. The main topic is the abstract theory of computability, based at first on an informal notion of algorithm, and then on the Turing machine. There are, however, two chapters which give a descriptive account of actual computing machines and of programs for them. The booklet includes a detailed account of the Turing machine and of the universal Turing machine, and proofs are given of the unsolvability of the self-computability problem for Turing machines and of the word problem for semigroups.

**2.2. Review by: Franz E Hohn.**

*The Mathematics Teacher*

**57**(4) (1964), 255-256.

'Algorithms and Automatic Computing Machines' discusses some familiar algorithms, the word problem, machine algorithms, Turing machines, etc. This is well done, but too advanced for most high school students. For a mature reader needing an introduction to these ideas, it is excellent.

**3. Introduction to the Theory of Finite Automata (1965), by N E Kobrinskii and B A Trakhtenbrot.**

**3.1. Review by: Martin Davis.**

*Mathematics of Computation*

**21**(97) (1967), 122.

The book begins with a self-contained lucid account of elementary logic. Real- time devices for processing digital data are introduced and shown to be associated with a definite class of mathematical operators. The physical characteristics of vacuum tubes (valves!), diodes, transistors, and ferromagnetic elements, are briefly discussed and their use in constructing flip-flops and in realizing basic logical operators is indicated. The problems of analysing (going from a physical circuit to the operator it realizes) and synthesizing (going from a mathematical operator to a circuit realizing it) are discussed in detail. A final chapter describes the work of Shannon and Lupanov on asymptotic estimates for nets realizing a given operator. The book is very well written and the English translation reads quite smoothly.

**3.2. Review by: Robert McNaughton.**

*The Journal of Symbolic Logic*

**33**(3) (1968), 466.

This book is an introduction to switching theory and the theory of finite automata. It is a well-integrated text, but with responsibility clearly divided between the two authors: Roughly, Kobrinskii is responsible for the switching theory and Trakhtenbrot for the automata theory. It covers its material fully and clearly, and thus serves well as an introduction for a mature reader previously unexposed to the subject matter ...

**3.3. Review by: G Asser.**

*Mathematical Reviews*MR0147349

**(26 #4866)**.

This book gives an excellent modern introduction to the theory of finite automata. In addition to the abstract mathematical considerations, the problems of the physico-technical realization are also dealt with to an appropriate extent.

**4. Finite Automata. Behavior and Synthesis (1973), by B A Trakhtenbrot and Ya M Barzdin.**

**4.1. Review by: Robert McNaughton.**

*The Journal of Symbolic Logic*

**42**(1) (1977), 111-112.

This book is a self-contained general exposition of the theory of finite automata, with special attention in the last two chapters to a special problem. The theoretical exposition is unique in paying equal attention right from the beginning to the representation of w-languages as it does to the representation of languages ...

**5. Algorithmen und Rechenautomaten (1977), by B A Trakhtenbrot.**

**Review by: Egon Borger.**

*Mathematical Reviews*MR0491083

**(58 #10356)**.

This book gives a very clear and detailed elementary introduction to the basic notions of the theory of algorithms. The first chapter introduces the concept of algorithms and of calculating machines from the intuitive point of view. It gives many interesting examples, such as algorithmic games, search algorithms, etc. This chapter together with the first parts of the second and third chapters reproduces essentially the author's earlier popular book

*Algorithms and machine solution of problems*(German). ... Throughout the book the examples and motivating discussions are particularly well suited for a beginner in the field of the theory of algorithms.

**6. Selected developments in Soviet mathematical cybernetics (1986), by B A Trakhtenbrot.**

**Review by: Menachem Dishon.**

*Mathematical Reviews*MR0961964

**(90h:68001)**.

This monograph is one in a series of scholarly studies on facets of work in the Soviet Union not well known or understood by the professional community or academia in the West. As aptly summarized in the foreword by Meyer, Trakhtenbrot's account of mathematical, or theoretical, cybernetics in the Soviet Union tells several stories. The greater part consists of an intellectual history of Soviet automata theory, combinational complexity and computational complexity over three decades, from the early 1950s to the early 1980s, and presents an in-depth survey of important results in these fields. A second story is that of the academic and political disputes which continue to shape the course of Soviet research in these areas. Finally, there is a laconic suggestion of the scientific life of a prolific mathematician and scholar, the author himself, one of the seminal researchers in automata theory and logic, who eventually emigrated (to Israel) in 1980. ... The author's selective account of the development of mathematical cybernetics in the Soviet Union relies much on his own recollections and is personally flavored. It makes fascinating reading. This monograph is highly recommended for anyone interested in the early development of theoretical cybernetics in the Soviet Union.