Computation and automata. (English) Zbl 0565.68046

Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge etc.: Cambridge University Press. XIII, 282 p. £25.00; $ 39.50 (1985).
The monograph gives an introduction to certain central topics in theoretical computer science and presents the material in a clear and mathematical perspective. Each section is developed from the beginning and quickly proceeds to the more advanced contents. Proofs usually are concise and some of them are skipped or replaced by scarce references. This book is an exposition of an important part of areas dealing with mathematical foundations of computer science, not including correctness of programs, data structures, data bases, and semantics. A central role is occupied by the classical computability theory initiated by the work of Gödel, Tarski, Church, Thue, Post, Turing, and Kleene. The recursively enumerable sets are defined through phrase structure grammars using semi-Thue like rewriting systems. As equivalents to those are identified: Post canonical systems, Markov algorithms, and Turing machines. In the proofs tedious constructions with a formal machine model are avoided. Automata, not only GSM’s and Turing machines, are formally defined by certain rewriting (i.e., semi-Thue) systems. The recursive function theory includes, among others, the \(S_{m,n}\)-theorem, recursion-theorem, and discusses degrees of undecidability, creative and productive sets. The chapter on computational complexity contains axiomatic as well as machine oriented complexity theory. The undecidability results, as usual, are based on the halting problem and the therefrom derived PCP. The famous Hilbert’s tenth problem is included as well as a section on cryptography. As modern trends are shortly discussed: Petri nets, grammar forms, and systolic automata. Every chapter closes with exercises, and their titles (number of pages) are: Introduction: Models of Computation (4), Rudiments of Language Theory (36), Restricted Automata (29), Turing Machines and Recursive Functions (38), Famous Decision Problems (20), Computational Complexity (45), Cryptography (43), Trends in Automata and Language Theory (9). The book, dedicated to the advanced undergraduate is appropriate for the graduate as well.
Reviewer: M.Jantzen


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03Dxx Computability and recursion theory
68Q25 Analysis of algorithms and problem complexity
68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
94A60 Cryptography
03-00 General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to mathematical logic and foundations
03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to computer science
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science