Computability, Complexity, Logic (eBook)

E. Borger (Autor)

eBook Download: PDF

1989 | 1. Auflage
591 Seiten
Elsevier Science (Verlag)
978-0-08-088704-3 (ISBN)

Infos

The theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning, facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for the solution of precisely described questions and problems.

The book is a unified introduction to the modern theory of these concepts, to the way in which they developed first in mathematical logic and computability theory and later in automata theory, and to the theory of formal languages and complexity theory. Apart from considering the fundamental themes and classical aspects of these areas, the subject matter has been selected to give priority throughout to the new aspects of traditional questions, results and methods which have developed from the needs or knowledge of computer science and particularly of complexity theory.

It is both a textbook for introductory courses in the above-mentioned disciplines as well as a monograph in which further results of new research are systematically presented and where an attempt is made to make explicit the connections and analogies between a variety of concepts and constructions.

Inhalt

Front Cover 1
Computability, Complexity, Logic 4
Copyright Page 5
Contents 12
Graph of dependencies 19
Introduction 20
Terminology and prerequisites 23
SECTION I: BOOK ONE ELEMENTARY THEORY OF COMPUTATION 26
CHAPTER A.THE MATHEMATICAL CONCEPT OF ALGORITHM 27
PART I: CHURCH'S THESIS 27
§1. Explication of Concepts 27
§2. Equivalence theorem 51
§3. Excursum into the semantics of programs 59
§4.Extended equivalence theorem 62
§5. Church's Thesis 73
PART II: UNIVERSAL PROGRAMS AND THE RECURSION THEOREM 12
§1. Universal programs 76
§2. Diagonalisation method 83
CHAPTER B. COMPLEXITY OF ALGORITHMIC UNSOLVABILITY 93
PART I: RECURSIVELY UNSOLVABLE PROBLEMS 93
§1. Halting problem K 94
§2. Simple reductions of K 96
§3. Exponential diophantine equations 107
§4. ëx,y,z.x = yz is dfophantina Pell equations 114
PART II: THE ARITHMETICAL HIERARCHY AND DEGREES OF UNSOLVABI LITY 128
§1. Recursively enumerable predicates 128
§2. Arithmetical hierarchy 133
§3.Reduction concepts and degrees of unsolvability 139
PART III: ABSTRACT COMPLEXITY OF COMPUTATION 169
§1. Speed-up phenomena 170
§2. Functions of arbitrary complexity 180
§3. Decomposition theory for universal automata 187
CHAPTER C. RECURSIVENESS AND COMPLEXITY 197
PART I: COMPLEXITY CLASSES OF RECURSIVE FUNCTIONS 198
§0. The k–tape Turing–rachine model 198
§1. Time– and place– hierarchy theorems 207
§2. Complexity of non–deterministic programs 216
PART II: COMPLEXITY CLASSES OF PRIMITIVE RECURSIVE FUNCTIONS 221
§1. Grzegorczyk hierarchy theorem 222
§2. En-Basic and En-computing time hierarchy theorem 236
§3. Ackermann function and Goodstein sequences 245
PART III: POLYNOMIALLY– AND EXPONENTIALLY– BOUNDED COMPLEXITY CLASSES 249
§1. NP–complete problems 251
§2. Complete problems for PTAPE and exponential classes 265
PART IV: FINITE AUTOMATA 267
§1. Characterisation by (non–) det erministic acceptors and regular expressionas 267
§2. Characterisation by indistinguishability congruence relation 275
§3. Decomposition theorems 281
§4 . Small universal programs 301
PART V: CONTEXT–FREE LANGUAGES 322
§1. Normal forms of Chomsky and Greibach, derivation Trees 322
§2. Periodicity properties 330
§3. Characterisation by machines 336
§4. Decision problems 341
§5. Comparison with the Chomsky hierarchy classes 352
SECTION II: BOOK TWO ELEMENTARY PREDICATE LOGIC 360
CHAPTER D. LOGICAL ANALYSIS OF THE TRUTH CONCEPT 362
PART I: SYNTAX AND SEMANTICS 362
§l. Formal languages of the first order 362
§2. Interpretation of formal languages 367
§3. Hilbert calculus 375
PART II: COMPLETENESS THEOREM 382
§1 . Derivations and deduction theorem for sentence logic 382
§2. Completeness of propositional logic 386
§3. Derivations and deduction theorem of the predicate logic 392
§4. Completeness of predicate logic 397
PART III: CONSEQUENCES OF THE COMPLETENESS THEOREM 403
§1. Weakness of expressibility of PL 1 403
§2. Second order predicate logic and type theory 407
§3. Canonical satisfiability 412
CHAPTER E. LOGICAL ANALYSIS OF THE CONCEPT OF PROOF 425
PART I: GENTZEN' S CALCULUS L.K. 426
§1. The calculus L.K. 426
§2. Equivalence to the Hilbert calculus 429
PART II: CUT ELIMINATION FOR L.K. 437
PART III: CONSEQUENCES OF THE CUT ELIMINATION THEOREM 448
§l. Gentzen's Hauptsatz 448
§2. Interpolation theorem 453
CHAPTER F. COMPLEXITY OF LOGICAL DECISION PROBLEMS 467
PART I: UNDECIDABILITY AND REDUCTION CLASSES 468
§1. Theorems of Church & Turing, Trachtenbrot
§2. Reduction class of Kahr–Moore– wang 487
PART II: INCOMPLETENESS OF ARITHMETIC 493
PART III: RECURSIVE LOWER COMPLEXITY BOUNDS 503
§0. Reduction method 504
§1. Complexity of Boolean functions 506
§2. Spectrum problem 522
§3. Complete decision problems for polynomial and exponential complexity classes 542
Bibliography 553
Index 599
List of symbols 615

Produkt-Details

• Erscheint lt. Verlag: 1.7.1989
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Allgemeines / Lexika
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Naturwissenschaften
• ISBN-10: 0-08-088704-X / 008088704X
• ISBN-13: 978-0-08-088704-3 / 9780080887043