### 基本信息

- 原书名：Introduction to the Theory of Computation
- 原出版社： Thomson Learning

### 内容简介

### 目录

To the student

To the educator

The current edition

Feedback to the author

Acknowledgments

0 Introduction

0. l Automata, Computability, and Complexity

Complexity theory

Computability theory

Automata theory

0.2 Mathematical Notions and Terminology

Sets

Sequences and tuples

Functions and relations

Graphs

Strings and languages

Boolean logic

Summary of mathematical terms

### 前言

Welcome !

Yon are about to embark on the study of a fascinating and important subject: the theory of compuation. It comprises the fundamental mathematical properties of computer hardware, software, and certain applications thereof. In studying this subject we seek to determine what can and cannot be computed, how quickly, with how muck memory, and on which type ofcompuational model. The subject has obvious connections with engineering practice, and, as in many sciences, it also has purely philosophial aspects.

I know that many ofyou are lookiog forward to studying this material but some may not be here out of choice. You may want to obtain a degree in compater science or engineering, and a course in theory is required-God knows why. After all, isn't theory arcane, boring, and worst of all, irrelevant?

To see that theory is neither arcane nor boring, but instead quite understandable and even interesting, read on. Theoretical computer science does have many fascinating big ideas, but it also has many small and sometimes dull details that can be tiresome. Learning any new subject is hard work but it becomes easier and more enjoyable if the subject is properly presented. My primary objective in writing this book is to expose you to the genuinely exciting aspects of computer theory, without getting bogged down in the drudgery. Of course, the only way to determine whether theory interests you is to try learning it.

Theory is relevant to practice. It provides conceptual tools that practitioners use in computer engineeting. Designing a new pro cialized application? What you learned about gr handy. Dealing with string searching and pattern .matching? Rememberfinite automata and regular expressions. Confronted with a problem that seems to require more computer time than you can afford? Think back to what you learned about NP-completeness. Various application areas, such as modem cryptographic protocols, rely on theoretical principles that you will learn here.

Theory also is relevant to you because it shows you a new, simpler, and more elegant side of computers, which we normally consider to be compliated'machines. The best computer designs and appliations are conceived with elegance in mind. A theoretical course can heighten your aesthetic sense and help you build more beautiful systems.

Finally, theory is good for you because studying it expands your mind. Computer technology changes quickly. Specific technical knowledge, though useful-today, becomes outdated in just a few years. Consider instead the abilities to think, to express yourself clearly and precisely, to solve problems, and to know when you haven't solved a problem. These abilities have lasting value. Studying theory trains you in these areas.

Practical considerations aside, nearly everyone working with computers is curious aboot these amazing creations, their apabilities, and their limitations. A whole new branch of mathematics has grown up in the past 30 years to answer certain basic questions. Here's a big one that remains unsolved: If I give you a large number, say, with 500 digits, can you find in factors (the numbers that divide it evenly), in a reasonable amount of time? Even using a supercomputer, no one presently knows how to do that in all cases witbin the lifetime of the universe!

The factoring problem is connected to certain secret codes in modern cryptosystems. Find a fast way to factor and fame is yours!

TO THE EDUC.ATOR

This book is intended as an upper-level undergraduate or introductory graduate text in computer science theory. It conains a mathematical treatment ofthe subject, designed around theorems and proofs. I have made some effort to accommodate students with little prior experience in proving theorems, though more experienced students will have an easier time.

My primary goal in presenting the material has been to make it clear and interesting. In so doing, I have emphasized intuition and "the big picture" in the subject over some lower level details.

For example, even though I present the method ofproofby induction in Chapter O along with other mathematial preliminaries preliminaries, it doesn't play an important role subsequently. Generally I do not present the usual induction proofs of the correctness of various constructions concerning automata. If presented clearly, these constructions convince and do not need further argument An induction may confuse rather than enlighten because induction itself is a rather sophisticated technique that many and mysterious. Belaboring the obvioas with an induction risks teaching students that mathematical proof is a formal manipulation instead of teaching them what is and what is not a cogent argument.

A second example occurs in Parts II and III, where I describe algorithms in prose instead of pseudocode. I don't spend much time programming Turing machines (or any other formal model). Students today come with a pro background and find the Church-Turing thesis to be self-evident. Hence I don't present lengthly simulations of one model by another to establish their equivalence.

Besides giving extra intuition and suppressing some details, I give what might be called a classical presentation of the subject material. Most theorist will find the choice of material, terminology, and order of presentation consistent with that of other widely used textbooks. I have introduced original terminology only a few places, when I found the standard terminology particularly obscure or confusing. For example I introduce the term mapping reducibility instead of many-one reducibility.

Practice through solving problems is essential to learning any mathematical subject In this book, the problems are organized into two main categories called Exercises and Problems. The Exercises review definitions and concepts. The Problems require some ingenuity. Problems marked with a sar are more difficult. I have tried to make both the Exercises and Problems interesting challenges.

THE CURRENT EDITION

Introduction to the Theory of computation first appeared as a Preliminary Edition in paperback The current edition differs from the Preliminary Edition in several substantial ways. The final three chapters are new: Chapter 8 on space complexity Chapter 9 on provable intractability; and Chapter 10 on advanced topics in complexity theory. Chapter 6 was expanded to include several advanced topics in computability theory. Other chapters were improved through the inclusion of additional example and exercises.

Comments from instructors and students who used the Pre