What is the theory of computation all about? The theory of computation embodies the principle by which computers have become the basis of modern digital technology, which makes a computer perform as desired, and which, consequently, has led to the prosperity of our advanced information society (just as physical sciences constitute the principle by which physical phenomena are elucidated, thereby bringing all the prosperity of our material civilization). Throughout this book, the term “computation” points to all tasks that are performed by a computer.

A computer not only performs basic arithmetic operations; it tells us what the weather is going to be, and it can inform us of the most popular product by extracting useful information from enormous amounts of customer purchasing data. The IBM computer Deep Blue has even defeated a grand master chess player. In this book, we describe how a computer performs these tasks in principle, and we also clarify the limits on what computers can do. We think of what a computer executes as a problem, which is defined as a correspondence relation between input and output data. When we try to forecast weather or to compute the most popular product based on available data, there might be cases in which the information is not sufficient to accomplish these tasks. In such cases, we need to somehow infer a conclusion based on insufficient data, but this type of discussion will be omitted from this book.

We will take up the game of chess to explain what computation time is. Given an arrangement of pieces on one side of a chessboard, to decide the best move, one must trace all possible sequences of moves until the game is completed. To do so, all possible moves must first be enumerated; then all possible countermoves of an opponent for each move of the player must be envisioned. Those processes must be repeated until the end of the game. Tracing all the possible moves in this way, the first player can choose the best move based on all the moves traced. In principle, a program that plays chess executes those tasks. But it is impossible in practice because it takes too much time, even for a computer, to read ahead all the moves to the end of the game. If even a supercomputer takes, say, 1,000,000 years to compute the next move, it is of no use. So, to beat a grand master of chess, it becomes crucial for a chess program to render a sufficiently appropriate, but perhaps not perfect, judgment about the next move based on some proper criterion of judgment.