Theories of computability. (English) Zbl 0879.03013

Pippenger, Nicholas

Cambridge: Cambridge University Press. ix, 251 p. (1997).

This book gives an extremly broad account of computability, it embraces not only the general theory (halting problem, Turing computability, Turing and many-one reducibilities, degrees, immune and simple sets, Recursion Theorem, primitive recursion, oracle machines, recursive ennumerability, index sets, priority method, recursive isomorphisms, creative sets, cylinders, abstract complexity theory), but also the theory of finite functions and relations initiated by Post, the theory of regular languages from a number of points of view (finite automata, regular expressions, logical expressions, monoids, aperiodicity, varieties), and the theory of other families of languages (linear, context-free languages, ambiguity, rational cones, formal power series). These are addressed both from the classical perspective (grammars and automata) and from more modern perspectives (rational cones, logical descriptions). In large parts, the book is written for those making their way to the frontier of research. Proofs are given more fully than usual. Various exercises are included.

Reviewer: U.Schöning (Ulm)

MSC:

03Dxx	Computability and recursion theory
68Qxx	Theory of computing
03-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
68-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
03D05	Automata and formal grammars in connection with logical questions
03D10	Turing machines and related notions
03D75	Abstract and axiomatic computability and recursion theory
03D35	Undecidability and degrees of sets of sentences
68Q45	Formal languages and automata
68Q70	Algebraic theory of languages and automata
68Q42	Grammars and rewriting systems

Keywords:

halting problem; recursion theorem; finite automata; computability; Turing computability; reducibilities; degrees; primitive recursion; oracle machines; recursive ennumerability; index sets; priority method; recursive isomorphisms; creative sets; cylinders; abstract complexity theory; regular languages; regular expressions; logical expressions; monoids; aperiodicity; varieties; context-free languages; ambiguity; rational cones; formal power series