Computability and complexity from a programming perspective

Cover......Page 1
Series......Page 3
Title......Page 4
Copyright......Page 5
Contents......Page 6
Series Foreword......Page 8
The view from Olympus......Page 10
The perspective of the book......Page 11
How to read this book......Page 13
Novel aspects, in a nutshell......Page 14
What is not considered......Page 16
Acknowledgments......Page 17
Part I: Toward the Theory......Page 18
1.1 The scope and goals of computability theory......Page 20
1.2 What is an effective procedure?......Page 21
1.2.1 Alan Turing’s analysis of computation......Page 22
1.2.2 The Church-Turing thesis......Page 25
1.2.3 Are algorithms hardware or software?......Page 26
1.3.1 Effectively computable functions......Page 27
1.3.3 Algorithms versus functions......Page 28
1.4.1 Countable sets and enumeration functions......Page 30
1.4.2 The diagonal method and uncontable sets......Page 31
1.4.3 Existence of effectively uncomputable functions......Page 32
1.4.4 Unsolvability of the halting problem......Page 33
1.4.5 The Busy Beaver problem: an explicit uncomputable function......Page 35
1.4.6 Unsolvability of the halting problem......Page 36
1.4.7 Consequences of unsolvability of the halting problem......Page 37
1.5.1 Polynomial time......Page 38
1.5.2 Complexity hierarchies and complete problems......Page 39
1.6 Historical background......Page 40
Exercises......Page 42
References......Page 44
2.1 Syntax of WHILE data and programs......Page 46
2.1.1 Binary trees as data values......Page 47
2.1.2 Syntax of WHILE programs......Page 48
2.1.3 Informal semantics......Page 50
2.1.4 Truth values and if-then-else......Page 51
2.1.5 Lists......Page 52
2.1.6 Numbers......Page 53
2.1.7 Syntactic sugar: some useful macro notations......Page 54
2.2 Semantics of WHILE programs......Page 55
2.2.2 Evaluation of expressions......Page 56
2.2.4 Semantics of WHILE programs......Page 57
2.2.5 Calculating semantic values......Page 58
2.3 Equality versus atomic equality......Page 59
2.3.1 More syntactic sugar......Page 60
Exercises......Page 62
References......Page 63
3.1 Programming languages and simulation......Page 64
3.2 Representing WHILE programs in ID......Page 65
3.3.1 Compiling without change of data representation......Page 67
3.3.2 TI-diagrams......Page 68
3.3.3 Compiling with change of data representation......Page 69
3.4.1 Interpretation without change of data representation......Page 70
3.4.2 An interpretation example: straightline Boolean programs......Page 71
3.5 Ways to combine compiler and interpreter diagrams......Page 73
3.6 Specialization......Page 74
3.7.1 The I language: one-variable WHILE-programs......Page 76
3.7.2 Restriction to one operator......Page 78
Exercises......Page 79
References......Page 80
Part II: Introduction to Computatility......Page 82
4.1.1 Interpretation of a subset of WHILE in WHILE......Page 84
4.1.2 Interpretation of the full WHILE language......Page 86
4.2 A universal program for the I language......Page 87
References......Page 88
5.1 Computability, decidability, enumerability......Page 90
5.2 Kleene’s s-m-n theorem......Page 91
5.3 Unsolvability of the halting problem......Page 92
5.4 Rice’s theorem......Page 93
5.5 Decidable versus semi-decidable sets......Page 95
5.6 The halting problem is semi-decidable......Page 96
5.7 Enumerability related to semi-decidability......Page 97
5.7.1 Enumerability characterized by semi-decidability......Page 98
Exercises......Page 100
References......Page 102
6.1 Timed programming languages......Page 104
6.2.1 Interpretation overhead in practice......Page 105
6.2.3 Layers of interpretation......Page 106
6.3 Compiler bootstrapping: an example of self-application......Page 108
6.4 Partial evaluation: efficient program specialization......Page 111
6.4.1 A slightly more complex example: Ackermann’s function......Page 112
6.5.1 The first Futamura projection......Page 113
6.5.3 Compiler generator generation by the third Futamura projection......Page 115
6.5.5 Metaprogramming without order-of-magnitude loss of efficiency......Page 116
6.6 Desirable properties of a specializer......Page 117
6.7 How specialization can be done......Page 120
6.7.1 Annotated programs and a sketch of an off-line partial evaluator......Page 121
6.7.2 Congruence, binding-time analysis, and finiteness......Page 124
Exercises......Page 125
References......Page 126
7. Other Sequential Models of Computation......Page 128
7.1.2 Control structures......Page 129
7.2 A flowchart language GOTO......Page 130
7.3 The Turing machine TM......Page 131
7.4 The counter machine CM......Page 133
7.5 The random access machine RAM......Page 134
7.6 Classical Turing machines......Page 137
Exercises......Page 140
References......Page 141
8.2 From GOTO to WHILE and back......Page 144
8.3 Compilations with change of data......Page 146
8.3.1 Common characteristics of the simulations......Page 147
8.4 Compiling RAM to TM......Page 148
8.5 Compiling TM to GOTO......Page 150
8.6 Compiling GOTO to CM......Page 151
8.7 Compiling CM to 2CM......Page 152
References......Page 153
9.1.1 The language F......Page 154
9.2 Interpretation of I by F and vice versa......Page 156
9.3 A higher-order functional language LAMBDA......Page 157
9.4.1 Implementing I in the lambda calculus......Page 161
9.4.2 Implementing the semantics of I......Page 163
9.4.3 Interpreting the lambda calculus in F+......Page 166
Exercises......Page 168
References......Page 169
10.1 Do there exist natural unsolvable problems?......Page 170
10.2.1 An undecidable problem in string rewriting......Page 172
10.2.2 String rewriting: undecidability of derivability......Page 173
10.3 Post’s correspondence problem......Page 175
10.4 Some problems concerning context-freegrammars......Page 180
Exercises......Page 181
References......Page 182
Part III: Other Aspects of Computability Theory......Page 184
11.1 Introduction......Page 186
11.2 Exponential Diophantine equations and sets......Page 188
11.3 Encoding of finite sequences......Page 190
11.4 The Davis-Putnam-Robinson Theorem......Page 193
Exercises......Page 201
References......Page 203
12. Inference Systems and Gödel’s Incompleteness Theorem......Page 206
12.1 Examples of operational semantics by inferencesystems......Page 207
12.1.1 Expression evaluation by inference rules......Page 208
12.1.2 Recursion by syntactic unfolding......Page 210
12.2 Predicates......Page 211
12.3 Predicates and program descriptions......Page 213
12.4.1 A formalization of inference systems......Page 214
12.4.2 Examples of inference systems......Page 215
12.4.3 Recursive enumerability of sets defined by inference systems......Page 216
12.5 A version of Gödel’s incompleteness theorem......Page 217
12.5.1 The logical language DL for ID......Page 218
12.5.2 Representation of predicates in DL......Page 219
12.5.3 Proof of a version of Gödel’s incompleteness theorem......Page 221
Exercises......Page 222
References......Page 223
13. Computability Theory Based on Numbers......Page 224
13.2.1 Primitive recursive functions......Page 225
13.2.2 Primitive recursiveness and CM-computability......Page 226
13.3 Equivalence of μ-recursiveness and CM-computability......Page 227
13.4 Kleene’s Normal Form theorem for the WHILE language......Page 229
References......Page 231
14.1 Recursion by semantics: fixpoints of functionals......Page 232
14.2.1 The theorems and some applications......Page 237
14.2.2 Proof for a reflexive extension of I......Page 239
14.3 A model-independent approach to computability......Page 242
14.3.1 Acceptable enumerations of recursive functions......Page 243
14.3.2 Kleene’s and Rogers’ theorems revisited......Page 245
14.4 Rogers’ isomorphism theorem......Page 247
References......Page 253
Part IV: Introduction to Complexity......Page 254
15.1 Where have we been?......Page 256
15.2.1 How complexity differs from computability......Page 257
15.2.2 Robustness of ptime and pspace......Page 258
15.3 Computational resources and problems......Page 259
15.4 ptime and tractability......Page 261
15.6 A backbone hierarchy of set membership problems......Page 262
15.7 Complete problems for (most of) the problem classes......Page 263
15.8 Intrinsic characterizations of logspace and ptime......Page 264
References......Page 265
16.1.1 Some simplifications......Page 266
16.2 Relating binary trees and bit strings......Page 267
16.3.1 Comparing languages......Page 268
16.3.2 Program-dependent or -independent overhead......Page 269
16.4.2 GOTO revisited......Page 270
16.5 Fair time complexity measures......Page 271
16.5.1 Random access machine instruction times......Page 272
16.5.2 Two time cost models for the RAM......Page 274
Exercises......Page 276
References......Page 277
17.1.1 Justification of unit cost timing for GOTO programs......Page 278
17.1.2 From ID to DSGs and back......Page 280
17.1.3 Correctness of the DAG semantics......Page 282
17.2.1 Simulating input-free programs......Page 283
17.2.2 Data initialization......Page 285
References......Page 287
18.1 Classifying programs by their running times......Page 288
18.2.2 Efficiently compiling GOTO to SRAM......Page 290
18.2.3 Compiling SRAM to TM......Page 291
18.3.1 Running times of F programs......Page 292
18.3.2 Linear-time equivalence of GOTO, WHILE, I, and F......Page 293
18.4 Linear time factors don’t matter for Turing machines......Page 294
References......Page 301
19. Linear and Other Time Hierarchies for WHILE Programs......Page 304
19.1 An efficient universal program for I......Page 305
19.2 An efficient timed universal program for I......Page 307
19.3 A linear-time hierarchy for I: constant time factors do matter......Page 308
19.5 Hierarchy results for superlinear times......Page 310
Exercises......Page 313
References......Page 314
20. The Existence of Optimal Algorithms......Page 316
20.1 Levin’s Theorem......Page 317
20.2 Functions arbitrarily hard to compute......Page 323
20.3 Blum’s Speedup Theorem......Page 326
20.4 The Gap Theorem......Page 330
Exercises......Page 331
References......Page 332
21. Space-bounded Computations......Page 334
21.1.2 Some read-only machine models and their space or size usage......Page 335
21.1.3 Comparing ordinary and read-only machines......Page 337
21.1.4 Space-bounded classes of programs and problems......Page 338
21.2 Comparing space usage of Turing and counter machines......Page 339
21.4 Robustness of pspace......Page 341
21.5 Relations between space and time......Page 343
21.6 Functions computable in logarithmic space......Page 344
21.7 Hierarchies of problems solvable in bounded space......Page 347
Exercises......Page 349
References......Page 350
22.1 Definition of nondeterministic acceptance......Page 352
22.3 Resource-bounded nondeterministic algorithms......Page 353
References......Page 354
23.1 Some convenient normalizations......Page 356
23.2 Program state transition graphs......Page 358
23.3.1 Graph accessibility in nondeterministic logarithmic space......Page 359
23.3.2 Graph inaccessibility in nondeterministic logarithmic space......Page 360
23.3.3 Graph accessibility in polynomial time......Page 361
23.3.4 Graph accessibility in log²n space......Page 362
23.3.5 Time and space to generate a state transition graph......Page 364
23.4 Some inclusions between deterministic and nondeterministic classes......Page 366
23.5 An enigmatic hierarchy......Page 367
References......Page 368
24.1 Characterizing logspace by cons-free GOTO programs......Page 370
24.1.1 Some central simulation lemmas......Page 371
24.1.2 Constructions to prove the simulation lemmas......Page 372
24.1.3 Relation to functional and Wadler’s treeless programs......Page 374
24.2.1 The recursive extension of a programming language......Page 376
24.2.2 Simulating ptime without cons......Page 377
References......Page 381
Part V: Complete Problems......Page 384
25.1 Introduction......Page 386
25.1.2 Three example problems......Page 387
25.1.3 Complete problems by reduction to programs with only boolean variables......Page 388
25.2 Invariance of problem representations......Page 389
25.3 Reduction for complexity comparisons......Page 391
25.3.1 A general definition of problem reduction......Page 392
25.3.2 Sources of complete problems......Page 395
25.4 Complete problems for re by recursive reductions......Page 396
25.5 Complete problems for nlogspace by logspace reductions......Page 397
25.6 A problem complete for nlintime......Page 399
References......Page 401
26. Complete Problems for ptime......Page 404
26.1 SBOOLE computation is complete for ptime......Page 405
26.2 The monotone circuit value problem......Page 408
26.3 Provability by Horn clauses......Page 410
26.4 Context-free emptiness and other problems complete for ptime......Page 413
26.5 Parallel computation and problems complete for ptime......Page 415
References......Page 416
27. Complete Problems for nptime......Page 418
27.1 Boolean program nontriviality is complete for nptime......Page 419
27.2 Satisfiability is complete for nptime......Page 421
27.2.1 Construction of a 3CNF expression from a program and its input......Page 422
27.3 Other problems complete for nptime......Page 423
References......Page 425
28.1 Acceptance by boolean programs with goto......Page 426
28.2 Quantified boolean algebra......Page 428
28.3 Regular expression totality......Page 431
28.4 Game complexity......Page 433
References......Page 434
Part VI: Appendix......Page 436
A.1 Boolean algebra......Page 438
A.1.1 Evaluation of boolean expressions......Page 439
A.2.1 Definition and examples......Page 440
A.3.1 Total Functions......Page 441
A.3.3 Partial functions......Page 443
A.3.5 Equality of functions and partial values......Page 444
A.3.6 Some operations on partial functions......Page 445
A.3.8 Lambda notation......Page 446
A.3.9 Injective, surjective, bijective, and monotonic total functions......Page 447
A.3.11 Comparing the growth of functions......Page 448
A.4 Graphs......Page 449
A.5.1 Alphabets and strings......Page 450
A.5.2 Grammars......Page 451
A.5.3 Classes of grammars......Page 452
A.5.4 Decidability problems for grammars......Page 453
A.5.5 Regular expressions......Page 454
A.5.6 NFA and DFA......Page 455
A.6.1 Inductive proofs......Page 457
A.6.2 Inductive definitions......Page 459
A.6.3 Other structures than numbers......Page 460
A.7 Pairing functions......Page 461
Exercises......Page 462
References......Page 465
A-B......Page 466
C-D......Page 467
E-F-G......Page 468
H-I-J......Page 469
K-L......Page 471
M......Page 472
N-P......Page 473
R-S......Page 474
T-V-W......Page 475
List of Notation......Page 476
A-B-C......Page 477
D......Page 478
E-F......Page 479
G-H-I-J-L......Page 480
M-N-O-P......Page 481
Q-R......Page 482
S-T......Page 483
U-V-W......Page 484