In Models of Computation: Exploring the Power of Computing, John Savage re-examines theoretical computer science, offering a fresh approach that gives priority to resource tradeoffs and complexity classifications over the structure of machines and their relationships to languages. This viewpoint reflects a pedagogy motivated by the growing importance of computational models that are more realistic than the abstract ones studied in the 1950s, '60s and early '70s.

Assuming only some background in computer organization, Models of Computation uses circuits to simulate machines with memory, thereby making possible an early discussion of P-complete and NP-complete problems. Circuits are also used to demonstrate that tradeoffs between parameters of computation, such as space and time, regulate all computations by machines with memory. Full coverage of formal languages and automata is included along with a substantive treatment of computability. Topics such as space-time tradeoffs, memory hierarchies, parallel computation, and circuit complexity, are integrated throughout the text with an emphasis on finite problems and concrete computational models

The released electronic version of the book, now available for free download, corrects all errors known to the author. Errors that occurred in print versions of the book can be found at Errata. Additional errata, as well as comments about the book, can be sent to John Savage.

Additional commentary on the book by Andy Yao, Jan van Leeuwen, and Akira Maruoka is provided below.

Download a PDF of the full book or of each individual chapter:

Models of Computation: Exploring the Power of Computing

Creative Commons License Models of Computation: Exploring the Power of Computing is currently released, as of July 23, 2008, in electronic form under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License.

Models of Computation was originally published as a book in 1998 by Addison-Wesley. Addison-Wesley, now a division of Pearson Publishing Group, has returned all rights to the document to the author.

Models of Computation document was then published as a book from 2002 until 2007 by XanEdu OriginalWorks, a division of ProQuest Information & Learning, Ann Arbor, MI 48106, 800-218-5971.boo


Commentary

This is an impressive book. The subject has been thoroughly researched and carefully presented. All the machine models central to the modern theory of computation are covered in depth; many for the first time in textbook form. Readers will learn a great deal from the wealth of interesting material presented.

-Andrew C. Yao

 Professor of Computer Science at Princeton University

 Turing Prize Winner


A magnificent piece of work! Models of Computation gives a superb treatment of modern complexity theory, in a perfect textbook style. Your book fills the gap which all of us felt existed too long. Congratulations on this excellent contribution to our field.

-Jan van Leeuwen

 Professor of Computer Science at Utrecht University, Netherlands

 Editor of the Handbook of Theoretical Computer Science The MIT Press/Elsevier, 1990


Models of Computation is an excellent new book that thoroughly covers the theory of computation including significant recent material and presents it all with insightful new approaches. This long-awaited book will serve as a milestone for the theory community.

-Akira Maruoka

 Professor of Information Sciences at Tohoku University, Japan