Computability Complexity Logic Book

Egon Börger: Computability, Complexity, Logic.

Studies in Logic and the Foundations of Mathematics, vol. 128, North-Holland, Amsterdam 1989, pp. XX+592.

CONTENTS

Graph of dependencies XIV

Introduction XV

Terminology and prerequisites XVIII

Book One ELEMENTARY THEORY OF COMPUTATION 1

Chapter A. THE MATHEMATICAL CONCEPT OF ALGORITHM 2

PART I. CHURCH'S THESIS 2

1. Explication of Concepts. Transition systems, 2 Computation systems, Machines (Syntax and Semantics of Programs), Turing machines. structured (Turing- and register-machine) programs (TO, RO).

2. Equivalence theorem, 26 LOOP-Program Synthesis for primitive recursive functions.

3. Excursus into the semantics of programs. 34 Equivalence of operational and denotational semantics for RM-while programs, fixed-point meaning of programs, proof of the fixed-point theorem.

4*. Extended equivalence theorem. Simulation of 37 other explication concepts: modular machines, 2-register machines, Thue systems, Markov algorithms, ordered vector addition systems (Petri nets), Post calculi (canonical and regular), Wang's non-erasing half-tape machines, word register machines.

5. Church's Thesis 48

PART II. UNIVERSAL PROGRAMS AND THE RECURSION THEOREM 51

1. Universal programs. Kleene normal form. 51 Acceptable universal programming system and effective program transformations.

2. Diagonalisation method. Recursion theorem: 58 fixed-point meaning (theorem of Rice), recursion meaning (implicit definitions: recursive enumeration of Fprim, injective translation functions in Goedel numbering, isomorphism theorem for Goedel numberings, self- reproducing programs), parametric effective version with infinitely many fixed points.

Chapter B COMPLEXITY OF ALGORITHMIC UNSOLVABILITY 68

PART I. RECURSIVELY UNSOLVABLE PROBLEMS (Reduction method) 68

1. Halting problem K. Special cases of Rice's 69 theorem.

2. Simple reductions of K. Decision problems of 71 universal computing systems, Post's correspondence problem, Domino problem. Roedding's path problem.

3*. Exponential diophantine equations. Simulation 82 of RO.

4*. exponentiation is diophantine. Pell equations. 89

PART II. THE ARITHEMTICAL HIERARCHY AND DEGREES OF UNSOLVABILITY 103

1. Recursively enumerable predicates. 103 Representation theorem. Universality.

2. Arithmetical hierarchy. Enumeration- and 108 hierarchy-theorems, representation theorem, determination of complexity (infinity and cardinality statements, arithmetical truth-concept)

3*. Reduction concepts and degrees of unsolvability. 114 Reduction concepts (theorem of Post), index sets (theorem of Rice and Shapiro, Sn-complete program properties), creativityand S1-completeness (theorem of Myhill), simple sets (theorem of Dekker and Yates), priority method (theorem of Friedberg and Mucnik), complexity of the arithmetical truth concept.

PART III. ABSTRACT COMPLEXITY OF COMPUTATION 144

1. Speed-up phenomena. Abstract measures of 145 complexity, Blum's speed-up theorem, impossibility of effective speed-up.

2. Functions of arbitrary complexity. Theorem of 155 Rabin-Blum-Meyer on functions of arbitrarily large program- or computing-time complexity, Blum's program-shortening theorem, gap theorem, union theorem.

3*. Decomposition theory for universal automata. 162 Characterisation of the run-time-, input-, output- transition-, and stop-functions of universal automata; impossiblity of uniform recursive simulation bounds on universal automata.

Chapter C RECURSlVENESS AND COMPLEXITY 172

PART I. COMPLEXITY CLASSES OF RECURSIVE FUNCTIONS 173

0. The k-tape Turing-machine model. Tape 173 reduction, tape- and time-compression, simulation complexity of a universal program.

1. Time- and place- hierarchy theorems. Theorem 182 of Fuehrer.

2. Complexity of non-deterministic programs 191 Theorem of Savitch.

PART II. COMPLEXITY CLASSES OF PRIMITIVE RECURSIVE 196 FUNCTIONS.

1. Grzegorczyk hierarchy theorem Equivalence of 197 the characterisation by growth-rate (limited recursion, excursus on Ackermann branches), recursion- and loop- depth, computing-time complexity from Kleene normal form with polynomially bounded or R3-coding functions.

2*. En-Basis- and En-computing time hierarchy theorem 211

3*. Ackermann function and Goodstein sequences 220 Theorem of Goodstein, Kirby and Paris.

PART III POLYNOMIALLY- AND EXPONENIALLY- BOUNDED 224 COMPLEXITY CLASSES.

1. NP-complete problems Halting-, domino-, 226 partition-, knapsack-, clique-, Hamiltonian cycle-, travelling salesman-, integer-programming-problems.

2. Complete problems for PTAPE and exponential classes. 240

PART IV FINITE AUTOMATA 242 1. Characterisation by (non-)deterministic 242 acceptors and regular expressions. Theorems of Rabin and Scott, Kleene.

2. Characterisation by indistinguishability 250 congruence relation Theorem of Myhill and Nerode with corollaries (state minimisation, examples of non-regular languages, loop lemma, 2-way automata ).

3*. Decomposition theorems Product decomposition, 256 modular decomposition (Roedding normal form in sequential and parallel signal processing).

4*. Small universal programs. 2-dimensional Turing 276 machine with 2 states and 4 letters, 2-dimensional Thue-system with 2 rules and 3 letters, PTAPE-complete Loop problem.

PART V CONTEXT-FREE LANGUAGES 297

1. Normal forms of Chomsky and Greibach, 297 derivation trees.

2. Periodicity properties. Loop lemma, Parikh's 305 theorem, inductive characterisation through substitution iteration.

3. Characterisation by machines. Push-down automata, 311 closure properties.

4. Decision problems. Decidability theorem for 316 context-free and regular grammars, complexity of the equivalence problem for regular expressions, undecidability theorem for context-free grammars, impossibility of effective minimisation.

5*. Comparison with the Chomsky hierarchy classes. 327 Intersection of regular with bracket languages, L-R derivation restrictions of type-0 grammars, context- dependent languages (space-requirement theorem and the LBA problem).

Book Two 335

ELEMENTARY PREDICATE LOGIC

Chapter D LOGICAL ANALYSIS OF THE TRUTH CONCEPT 337

PART I. SYNTAX AND SEMANTICS 337

1. Formal languages of the first order. 337

2. Interpretation of formal languages. 342

3. Hilbert calculus. 350

PART II. COMPLETENESS THEOREM 357

1. Derivations and deduction theorem for 357 sentence logic

2. Completeness of propositional logic. 361 (Lindenbaum maximisation process; analytical tables, resolution )

3. Derivations and deduction theorem of the 367 predicate logic

4. Completeness of predicate logic. 372

PART III. CONSEQUENCES OF THE COMPLETENESS THEOREM 378

1. Weakness of expressibility of PL 1. Theorem of 378 Skolem, compactness theorem, non-characterisability of the concept of infiniteness, non-standard models of number theory.

2*. Second order predicate logic and type theory. 382 characterisation of finiteness and countability and of (N; 0, +1) in second order; languages of n-th order.

3. Canonical satisfiability. Skolem normal form, 387 (minimal) Herbrand models, predicate logic resolution, procedural interpretation of Horn formulas, completeness of SLD-resolution.

Chapter E. LOGICAL ANALYSIS OF THE CONCEPT OF PROOF. 400

PART I. GENTZEN' S CALCULUS LK. 401

1. The calculus LK. 401

2. Equivalence to the Hilbert calculus. 404

PART II*. CUT ELIMINATION FOR LK 412

PART III*. CONSEQUENCES OF THE CUT ELIMINATION THEOREM. 423

1. Gentzen's Hauptsatz. (Cor: Herbrand's Theorem) 423

2. Interpolation theorem Cor: Definability 428 theorem. Analysis of interpolation- and definability- theorems in the finite.

Chapter F. COMPLEXITY OF LOGICAL DECISION PROBLEMS 442

PART I. UNDECIDABILITY AND REDUCTION CLASSES 443

1. Theorems of Church & Turing. Trachtenbrot. 443 Aanderaa & Boerger. Cor: PROLOG program as axiom of an essentially undecidable theory, respectively, as a satisfiable formula without recursive models, PROLOG- definability of all computable functions, impossibility of recursive interpolation and of recursive explication bounds of implicit definitions.

2*. Reduction class of Kahr-Moore-Wang. 462

PART II INCOMPLETENESS OF ARITHMETIC 468

Incompleteness theorem of Goedel. theorem of Loeb.

PART III RECURSIVE LOWER COMPLEXITY BOUNDS 478

0. Reduction method. 479

1. Complexity of Boolean functions. Theorem of 481 Cook, theorem of Henschen & Wos, polynomial equivalence of Horn- and network-complexity, theorem of Stockmeyer.

2*. Spectrum problem Spectrum characterisation of 497 the E3-computation time hierarchy (theorem of Roedding & Schwichtenberg, Jones & Selman, Christen), logical characterisation of NP by global existential second order predicate (theorem of Fagin), of p by PL1+LFP- with-order (theorem of Immerman & Vardi), of PTAPE by PL2+TC (theorem of Immerman).

3. Complete decision problems for polynomial and 517 exponential complexity classes. Theorem of Lewis (NEXPTlME-completeness of the satisfiability problem of the monadic Goedel-Kalmar-Schuette class, theorem of Plaisted (EXPTlME-completeness of the satisfiability problem of the Bernays-Schoenfinkel class in Horn formulas. Corollary: NEXPTIME-completeness), theorem of Plaisted and Denenberg & Lewis (PTAPE-completeness of the satisfiability problem of the Bernays-Schoenfinkel class in Krom- (and Horn-) formulas. Corollary: Its PTAPE-completeness in deterministic Krom- and Horn formulas.

(Sections marked with * contain more advanced material which can be read at the conclusion of the basic course. )

Bibliography 528

Index 574

List of symbols 590