The text is organized in 15 chapters and thus well suited for a one semester (under)graduate course. As said above, theory of computation is the place where theory and practice meet. Though nowadays many software packages include an impressive amount of the relevant programs, it is important to gain an understanding why and how everything works.

Expressing everything clearly, concisely and correctly requires a certain degree of formalization. We assume basic knowledge of discrete mathematics, only. In particular, it may be helpful if the reader has a basic understanding of what constitutes a proof of a mathematical assertion. All the remaining material is introduced in the text. Fundamental concepts are exemplified, too. We are strongly convinced that a solid compromise between formal correctness and intuitive ideas may help both the students and instructors to enjoy the wealth of insight this book is aiming to present.

Main emphasis is put on the interaction of theory and practice in informatics. Theory must deal with problems of practical importance and practical informatics needs a solid foundation to develop its full potential. Therefore, two thirds of the book are devoted to formal languages and automata theory. Formal languages are indispensable for applied computer science, since one meets them everywhere. Thus, we cover grammars (formalizing the generation), automata (formalizing the acceptance) and their interaction for regular and context-free languages.

The remaining third formalizes the intuitive notion of algorithm by introducing partial recursive functions and Turing machines. We show the equivalence of these two models and prove the existence of a universal Turing machine. That is, there is one computing device that can perform every possible computation. Finally, we show that there are problems which cannot be solved at all by any computer. Here we start with the halting problem, continue with Post's correspondence problem, and apply the theory developed to obtain a rather complete picture concerning problems arising naturally in formal language theory. Finally, we show the fixed point and recursion theorem, Rice's famous theorem, and introduce (abstract) complexity classes and study some of their properties.

The book also contains important material which is rarely covered in other textbooks, e.g., the Theorem of Chomsky-Schützenberger, our exposition of the partial recursive functions, Dedekind's justification theorem, abstract complexity classes and their properties.

Note that the book is accompanied by 15 sets of slides (in Japanese and English) which can be directly used in classrooms. We have tested these teaching materials at Hokkaido University. These slides and the book itself aim at Japanese students who wish to improve their English languages skills while studying their favorite subject and at international students who wish to complete their computer science studies at a Japanese university.

Experience shows that it is often difficult to find the correct technical term when dealing with a highly specialized subject such as theory of computation. We wish to facilitate this task and have included translations (English-Japanese) in the main text. If an important technical term is introduced, it is emphasized and followed by the appropriate Japanese term.

Definitions are written in italics except the term that is defined which is typeset in roman. Again, the term defined is translated into Japanese.

Of course, a textbook like the present one is also used as a reference. Consequently, we have added three indices, the usual subject index, a symbol index and a Japanese index to facilitate the search in such cases.

This book, like any other book has a certain disadvantage when compared with a teacher, i.e., it cannot speak and answer to questions. As a consequence, we have included exercises and problems. There is no principal difference between them such as the degree of difficulty. The only distinction is that the solutions to problems are included and the answers to exercises are excluded. These exercises and problems are recommended for classroom seminars and/or homework assignments, since they hopefully shed additional light on many interesting features. It should also be noted that our solutions are not the only possible ones. Sometimes, we included different solutions to the same problem to highlight this aspect.

Last but not least we confess that the course is demanding. But this is just in line with William S. Clark's (the founding vice-president of Hokkaido University) encouragement