Computability and UnsolvabilityCourier Corporation, 2013/04/16 - 288 ページ In this classic text, Dr. Davis provides a clear introduction to computability, at an advanced undergraduate level, that serves the needs of specialists and non-specialists alike. In Part One (Chapters 1–5), Professor Davis outlines the general theory of computability, discussing such topics as computable functions, operations on computable functions, recursive functions, Turing machines, self-applied, and unsolvable decision problems. The author has been careful, especially in the first seven chapters, to assume no special mathematical training on the part of the reader. Part Two (Chapters 6–8) comprises a concise treatment of applications of the general theory, incorporating material on combinatorial problems, Diophantine Equations (including Hilbert's Tenth Problem) and mathematical logic. The final three chapters (Part 3) present further development of the general theory, encompassing the Kleene hierarchy, computable functionals, and the classification of unsolvable decision problems. When first published in 1958, this work introduced much terminology that has since become standard in theoretical computer science. Indeed, the stature of the book is such that many computer scientists regard it as their theoretical introduction to the topic. This new Dover edition makes this pioneering, widely admired text available in an inexpensive format. For Dover's edition, Dr. Davis has provided a new Preface and an Appendix, "Hilbert's Tenth Problem Is Unsolvable," an important article he published in The American Mathematical Monthly in 1973, which was awarded prizes by the American Mathematical Society and the Mathematical Association of America. These additions further enhance the value and usefulness of an "unusually clear and stimulating exposition" (Centre National de la Recherche Scientifique, Paris) now available for the first time in paperback. |
目次
| 3 | |
| 5 | |
Resz a 1 | 22 |
Operations on Computable Functions | 25 |
gn M 57 81 | 36 |
Recursive Functions | 41 |
az | 42 |
Tl Py rn | 52 |
Pz | 88 |
Diophantine Equations | 102 |
Mathematical Logic | 117 |
The Kleene Hierarchy | 145 |
V | 160 |
Computable Functionals | 162 |
lim ra | 174 |
The Classification of Unsolvable Decision Problems | 179 |
他の版 - すべて表示
多く使われている語句
A-computable A-primitive A-recursively A-semicomputable algorithm alphabet arithmetical logic associated axiom called Chap combinatorial system completely computable functional completely recursive constructive Corollary decision problem defined Definition 1.5 Diophantine equation diophantine predicate Diophantine sets domain exists finite function first-order logic follows at once fºr function f given Gödel number Hence Hilbert's tenth problem implies instantaneous description integers internal configuration Julia Robinson Lemma mathematical modus ponens n-ary n-tuples normal system obtained partial propositional calculus partial recursive function partially computable polynomial positive integers primitive recursive function problem is recursively productions proved quadruples quantifiers recursively enumerable set recursively solvable respect Resz satisfies semi-Thue system semicomputable predicate semigroup sequence simple Turing machine solution suppose Theorem 3.1 theory Thue system total functions Turing machine U(min undefined unsolvable decision problem variables word write yields