计算理论基础:可计算性、复杂性和语言(英文影印版)

    书籍
    计算机书籍
本书是理论计算机科学领域的名作，是计算机科学核心主题的导论性教材。全书分为可计算性、文法与自动机、逻辑学、复杂性及语义学5个部分，分别讲述了可计算性理论、形式语言、逻辑学与自动演绎、可计算复杂性（包括NP完全问题）和编程语言的语义等主题，并展示了它们之间如何相互关联。.
本书是计算机及相关专业高年级本科生和研究生的理想教学参考书，对于计算机领域的专业人士也是很好的技术参考书。...

Martin D．Davis，著名计算机科学家和数学家。1950年在普林斯顿大学获得博士学位，与图灵同门(导师均为计算科学大师Alonzo Church)。后长期任教于纽约大学柯朗数学研究所。他是自动演绎理论先驱，还是DPLL算法的发明人之一，Post-Turing机更使其声名远播。除本书外，他还著有经典名著Computability and Unsolvability。.
Ron Sigal，资深软件工程师。1983年在纽约大学获得计算机科学博士学位。曾先后任教于纽约城市大学、意大利卡塔尼亚大学、耶鲁大学、Hofstra大学。他参与的软件项目有NASA的火星探路者、JBoss等。..
Elaine J．Weyuker，著名女计算机科学家。美国国家工程院院士、IEEE和ACM会士、AT&T院士、ACM妇女委员会主席、ACM执行委员，现任AT&T实验室研究员。她的主要研究领域是软件测试与可靠性。此前曾任纽约大学柯朗数学研究所计算机科学教授近20年。...

I Preliminaries .　1
1. Sets and n-tuples　1
2. Functions　3
3. Alphabets and Strings　4
4. Predicates　5
5. Quantifiers　6
6. Proof by Contradiction　8
7. Mathematical Induction　9
Part 1 Computability　15
2 Programs and Computable Functions　17
1. A Programming Language　17
2. Some Examples of Programs　18
3. Syntax　25
4. Computable Functions　28
5. More about Macros　32
3 Primitive Recursive Functions　39
I. Composition　39
2. Recursion　40
3. PRC Classes　42
4. Some Primitive Recursive Functions　44

　　Theoretical computer science is the mathematical study of models ofcomputation. As such, it originated in the 1930s, well before the existenceof modern computers, in the work of the logicians Church, G6del, Kleene,Post, and Turing. This early work has had a profound influence on thepractical and theoretical development of computer science. Not only hasthe Turing machine model proved basic for theory, but the work of thesepioneers presaged many aspects of computational practice that are nowcommonplace and whose intellectual antecedents are typically unknown tousers. Included among these are the existence in principle of all-purpose(or universal) digital computers, the concept of a program as a list ofinstructions in a formal language, the possibility of interpretive programs,the duality between software and hardware, and the representation oflanguages by formal structures, based on productions. While the spotlightin computer science has tended to fall on the truly breathtaking technolog-ical advances that have been taking place, important work in the founda-tions of the subject has continued as well. It is our purpose in writing thisbook to provide an introduction to the various aspects of theoreticalcomputer science for undergraduate and graduate students that is suffi-ciently comprehensive that the professional literature of treatises andresearch papers will become accessible to our readers. .
　　We are dealing with a very young field that is still finding itself.Computer scientists have by no means been unanimous in judging whichparts of the subject will turn out to have enduring significance. In thissituation, fraught with peril for authors, we have attempted to select topicsthat have already achieved a polished classic form, and that we believe willplay an important role in future research.
　　In this second edition, we have included new material on the subject ofprogramming language semantics, which we believe to be established as animportant topic in theoretical computer science. Some of the material oncomputability theory that had been scattered in the first edition has beenbrought together, and a few topics that were deemed to be of onlyperipheral interest to our intended audience have been eliminated. Nu-merous exercises have also been added. We were particularly pleased to beable to include the answer to a question that had to be listed as open inthe first edition. Namely, we present Neil Immerman's surprisinglystraightforward proof of the fact that the class of languages accepted bylinear bounded automata is closed under complementation.
　　We have assumed that many of our readers will have had little experi-ence with mathematical proof, but that almost all of them have hadsubstantial programming experience. Thus the first chapter contains anintroduction to the use of proofs in mathematics in addition to the usualexplanation of terminology and notation. We then proceed to take advan-tage of the reader's background by developing computability theory in thecontext of an extremely simple abstract programming language. By system-atic use of a macro expansion technique, the surprising power of thelanguage is demonstrated. This culminates in a universal program, which iswritten in all detail on a single page. By a series of simulations, we thenobtain the equivalence of various different formulations of computability,including Turing's. Our point of view with respect to these simulations isthat it should not be the reader's responsibility, at this stage, to fill in thedetails of vaguely sketched arguments, but rather that it is our responsibil-ity as authors to arrange matters so that the simulations can be exhibitedsimply, clearly, and completely.
　　This material, in various preliminary forms, has been used with under-graduate and graduate students at New York University, Brooklyn College,The Scuola Matematica Interuniversitaria-Perugia, The University of Cal-ifornia-Berkeley, The University of California-Santa Barbara, WorcesterPolytechnic Institute, and Yale University.
　　Although it has been our practice to cover the material from the secondpart of the book on formal languages after the first part, the chapters onregular and on context-free languages can be read immediately afterChapter 1. The Chomsky-Schiitzenberger representation theorem for con-text-free languages in used to develop their relation to pushdown au-tomata in a way that we believe is clarifying. Part 3 is an exposition of theaspects of logic that we think are important for computer science and canalso be read immediately following Chapter 1. Each of the chapters of Part4 introduces an important theory of computational complexity, concludingwith the theory of NP-completeness. Part 5, which is new to the secondedition, uses recursion equations to expand upon the notion of computabil-ity developed in Part 1, with an emphasis on the techniques of formalsemantics, both denotational and operational. Rooted in the early work ofG/Sdel, Herbrand, Kleene, and others, Part 5 introduces ideas from themodern fields of functional programming languages, denotational seman-tics, and term rewriting systems. ..
　　Because many of the chapters are independent of one another, this bookcan be used in various ways. There is more than enough material for afull-year course at the graduate level on theory of computation. We haveused the unstarred sections of Chapters 1-6 and Chapter 9 in a successfulone-semester junior-level course, Introduction to Theory of Computation,at New York University. A course on finite automata and formal languagescould be based on Chapters 1, 9, and 10. A semester or quarter course onlogic for computer scientists could be based on selections from Parts 1 and3. Part 5 could be used for a third semester on the theory of computationor an introduction to programming language semantics. Many other ar-rangements and courses are possible, as should be apparent from thedependency graph, which follows the Acknowledgments. It is our hope,however, that this book will help readers to see theoretical computerscience not as a fragmented list of discrete topics, but rather as a unifiedsubject drawing on powerful mathematical methods and on intuitionsderived from experience with computing technology to give valuable in-sights into a vital new area of human knowledge.
　　Note to the Reader
　　Many readers will wish to begin with Chapter 2, using the material of Chapter 1 for reference as required. Readers who enjoy skipping aroundwill find the dependency graph useful.
　　Sections marked with an asterisk (*)may be skipped without loss ofcontinuity. The relationship of these sections to later material is given inthe dependency graph.
　　Exercises marked with an asterisk either introduce new material, referto earlier material in ways not indicated in the dependency graph, orsimply are considered more difficult than unmarked exercises.
　　A reference to Theorem 8.1 is to Theorem 8.1 of the chapter in whichthe reference is made. When a reference is to a theorem in anotherchapter, the chapter is specified. The same system is used in referring tonumbered formulas and to exercises.
　　Acknowledgments
　　It is a pleasure to acknowledge the help we have received. CharleneHerring, Debbie Herring, Barry Jacobs, and Joseph Miller made theirstudent classroom notes available to us. James Cox, Keith Harrow, SteveHenkind, Karen Lemone, Colm O'Dunlaing, and James Robinett providedhelpful comments and corrections. Stewart Weiss was kind enough toredraw one of the figures. Thomas Ostrand, Norman Shulman, LouisSalkind, Ron Sigal, Patricia Teller, and Elia Weixelbaum were particularlygenerous with their time, and devoted many hours to helping us. We areespecially grateful to them.
　　Acknowledgments to Corrected Printing
　　We have taken this opportunity to correct a number of errors. We aregrateful to the readers who have called our attention to errors and whohave suggested corrections. The following have been particularly helpful:Alissa Bernholc, Domenico Cantone, John R. Cowles, Herbert Enderton,Phyllis Frankl, Fred Green, Warren Hirsch, J. D. Monk, Steve Rozen, andStewart Weiss.
　　Acknowledgments to Second Edition
　　Yuri Gurevich, Paliath Narendran, Robert Paige, Carl Smith, and particu-larly Robert McNaughton made numerous suggestions for improving thefirst edition. Kung Chen, William Hurwood, Dana Latch, Sidd Puri,Benjamin Russell, Jason Smith, Jean Toal, and Niping Wu read a prelimi-nary version of Part 5.
　　Acknowledgments to Reprint of Second Edition
　　We are grateful to the following people for their careful reading of theSecond Edition: John Case, P. Klingsberg, Ken Klein, Eugenio Omodeo,David Schedler, John David Stone, and Lenore Zuck. ...