Computational theory (also known as computability theory) is a fundamental logical approach to understanding the capabilities of computation by machines. As technology advances at ever-increasing speeds, students not versed in the theory of computation develop the impression that the “sky is the limit,” meaning that computation is without limits. In fact, unsolvability results prove that there are inherent limitations on computation. Exploring these limitations and properly categorizing those problems that are solvable are at the heart of computational theory.

The author walks a delicate path between presenting the breadth of topics and exploring all the depths of the theory, and between writing a comprehensive (encyclopedic) textbook and providing a concise overview of the essential topics. The author, a professor in the faculty of science and engineering at the Ishinomaki Senshu University in Japan, originally wrote a concise text in Japanese for his students to understand the depths and appreciate the profoundness of the theory. When translating the text, the author extended it for the classroom setting by expanding the discussions, extensively adding problems at the end of the appropriate chapters, and providing solutions at the end of the book (chapter 11).

The book is divided into five parts composed of 12 chapters. The first chapter describes the context for understanding the barriers to computation, introduces the protagonists of the field, and guides students on how to make the best use of the text. Chapter 2 concisely provides the fundamental mathematical concepts that would be studied in a discrete mathematics course. As mentioned, chapter 11 provides the solutions to all of the problems found in chapters 2 through 10. Keeping to the goal of being concise, the author, whenever warranted, just gives the solution in its final form. Chapter 12 (one page of text) contains the author’s concluding remarks.

Part 2 (chapters 3, 4, and 5) covers the lower half of the Chomsky hierarchy from a grammar, language, and machine perspective. Except for presenting the definitions and a basic example, the class of context-sensitive languages and its corresponding machines, linear bounded automata (LBA), are not discussed because these languages do not provide major practical or theoretical results. The lowest two levels of the hierarchy provide many practical results (type three, regular languages are the basis of pattern expressions and type two, context-free languages are used in describing programming languages).

The highest level of the hierarchy is Turing machines (Part 3, chapters 6 and 7), which provide the basis of most major results in computability theory. Part 3 examines the definitions, universality, and limitations of the Turing machine.

Part 4 (chapters 8 through 10) investigates computational complexity based on Turing machines (chapter 8) and Boolean circuits (chapter 9), as well as the notion of NP-completeness and the famous P=NP question (chapter 10).

The last part provides the solutions to the problems throughout the book (chapter 11) and concluding remarks (chapter 12).

This textbook provides a concise introduction to the theory of computation, concentrating on the fundamental results that have the greatest impact on the theory and its practical applications. This text would be very appropriate for graduate students in computer science or those academics who want a refresher course on the main results of the discipline. It could also be utilized for an undergraduate theory course if the instructor were to work through all of the examples in class.