Description
Book Synopsis
This book gives an introduction to theories of computability from a mathematically sophisticated point of view. It treats not only 'the' theory of computability, but also a variety of other theories. Each topic is taken from the beginning and developed to a point at which the results can be appreciated.
Trade Review
"The author is extremely precise and meticulous, giving as much care to a proof that any context-free language can be generated by a grammar in Greibach normal form (GNF) as to a priority argument." Computing Reviews
"...an excellent textbook for a beginning researcher who wants to familiarize himself/herself with several axiomatic frameworks for the theory of computability...I enjoyed the nuggets of wit spread throughout the book, providing a pleasant contrast to the abstract material." SIGACT News
"Aiming readers at the frontier of research, the book has a point to make, and it makes it in an elegant and attractive way." Mathematical Reviews
"The book, which has a list of about 200 references, is well indexed, well organized, and quite well written. But the strongest commendation is for its selection of material and its coherent organization." Siam Review
Table of Contents
Preface; 1. Finite functions and relations; 2. Finite automata and their languages; 3. Grammars and their languages; 4. Computable functions and relations; References; Author index; Subject index; Math index.
