×

The theory of computability. Programs, machines, effectiveness and feasibility. (English) Zbl 0743.68010

International Computer Science Series. Wokingham, England: Addison- Wesley. XII, 441 p. (1988).
Unlike most other books on the subject this one introduces computability by giving an exact definition of syntax and semantics of a high level programming language called SAL. A function is then defined as computable iff there exist an SAL-program computing it. This approach has the advantage that algorithms can be formulated and, thus, problems shown to be computable, much more easily, the same holds true for many of the standard constructions in computability theory. The equivalence of this definition to the traditional ones by recursive functions of Turing machines is shown.
The book contains the major results of recursion theory concerning decidability and solvability. Besides, a considerable part is devoted to complexity theory. Hierarchy theorems for time and space complexity are presented, as well as the notions of reducibility and completeness. Also, the major complexity classes P, NP, co-NP, PSPACE, NL are considered, where one chapter is dealing with NP-completeness.
The book finishes with a chapter on alternative models of computation like approximation algorithms, randomized and parallel algorithms.
Reviewer: H.Alt (Berlin)

MSC:

68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D10 Turing machines and related notions
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite