This book provides a comprehensive albeit short introduction into the
theory of computation. The intended audience are all
students of computer science independently of whether they aim to
specialize in applied computer science, software engineering,
computerbased media technologies, artificial intelligence, knowledge
discovery, or any branch of computer science including theory. Graduate
students may find this book also useful as a reference or when writing
their first own research papers.
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 contextfree 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 ChomskySchü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 (EnglishJapanese)
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 vicepresident
of Hokkaido University) encouragement
