Theory of Computation

The focus of this book is on finite problems and concrete computational models. It covers the traditional topics of formal languages, automata and complexity classes, as well as an introduction to the more modern topics of space-time tradeoffs, memory hierarchies, parallel computation, the VLSI model, and circuit complexity. These topics are integrated throughout the book as illustrated by the early introduction of P-complete and NP-complete problems.

The book as a whole acquaints the reader with automata theory fundamentals. The book provides theoretical coverage of the essential principles, solve instances, and solve multiple-choice problems with solutions. The theory and computation of automata presented in this book will greatly assist students and professors alike.

In this book partial implementations of Von Neumann's Universal Constructor and universal copier are provided, starting out with three types of simple building blocks using minimal assumptions. Using the same principles, several Turing machines are constructed. Combining both, we arrive at a proposal for a self-replicating Turing machine.

This is the first English book on Component Pascal and BlackBox Component Builder.