Egon Börger: Computability, Complexity, Logic.
Studies in Logic and the Foundations of Mathematics, vol. 128,
North-Holland, Amsterdam 1989, pp. XX+592.
Graph of dependencies XIV
Terminology and prerequisites XVIII
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
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
1. Universal programs. Kleene normal form. 51
Acceptable universal programming system and effective
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
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
4*. exponentiation is diophantine. Pell equations. 89
PART II. THE ARITHEMTICAL HIERARCHY AND DEGREES OF
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
PART III. ABSTRACT COMPLEXITY OF COMPUTATION 144
1. Speed-up phenomena. Abstract measures of 145
complexity, Blum's speed-up theorem, impossibility of
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
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
2. Complexity of non-deterministic programs 191
Theorem of Savitch.
PART II. COMPLEXITY CLASSES OF PRIMITIVE RECURSIVE 196
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
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
PART V CONTEXT-FREE LANGUAGES 297
1. Normal forms of Chomsky and Greibach, 297
2. Periodicity properties. Loop lemma, Parikh's 305
theorem, inductive characterisation through substitution
3. Characterisation by machines. Push-down automata, 311
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
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
2. Completeness of propositional logic. 361
(Lindenbaum maximisation process; analytical tables,
3. Derivations and deduction theorem of the 367
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
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
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. )
List of symbols 590