Foundations of Computation Theory

This book is intended as a text for senior and graduate students, and was originally used at the University of Tokyo and the Tokai University. The author describes the theory of computational complexity with special attention to the origin of computation theory. An historical overview of the computability problem and its mathematical origins gives the freshman reader the minimal background to the three main chapters of the book - which are essentially self contained. The second chapter introduces the motions of algorithm and Turning Machine, and variations thereof. The book proceeds to cover decidability and the halting problems. The main part of the work covers complexity and gives an introduction to this core part of theoretical computer science. Since the 1960s, interests have been focused on how much resources (time and space) are needed to compute a function or to solve a problem. The computational power of computers has increased rapidly year-by-year, so people may think that it is not very significant whether a problem has only exponential time algorithms, or that it is not necessary to find more effective algorithms.
The author contends that problems having only exponential time algorithms are thought to be infeasible in principle, that is, not practically computable even if the computation power of computers were increased 1000 times beyond the power of current computers. A brief chapter on cryptography completes this book.