Computability and Complexity: From a Programming Perspective (Foundations of Computing) (FOUNDATIONS OF COMPUTING SERIES)

Computability and complexity theory should be of central concern to practitioners as well as theorists. Unfortunately, however, the field is known for its impenetrability. Neil Jones's goal as an educator and author is to build a bridge between computability and complexity theory and other areas of computer science, especially programming. In a shift away from the Turing machine- and Gödel number-oriented classical approaches, Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists and more applicable to practical programming problems. According to Jones, the fields of computability and complexity theory, as well as programming languages and semantics, have a great deal to offer each other. Computability and complexity theory have a breadth, depth, and generality not often seen in programming languages. The programming language community, meanwhile, has a firm grasp of algorithm design, presentation, and implementation. In addition, programming languages sometimes provide computational models that are more realistic in certain crucial aspects than traditional models. New results in the book include a proof that constant time factors do matter for its programming-oriented model of computation. (In contrast, Turing machines have a counterintuitive "constant speedup" property: that almost any program can be made to run faster, by any amount. Its proof involves techniques irrelevant to practice.) Further results include simple characterizations in programming terms of the central complexity classes PTIME and LOGSPACE, and a new approach to complete problems for NLOGSPACE, PTIME, NPTIME, and PSPACE, uniformly based on Boolean programs. Foundations of Computing series Booknews A computer science text bridging the gap between the perceived impenetrability of computability and complexity theory and practical programming problems. Jones (computer science, U. of Copenhagen) offers new results, including a proof that constant time factors do matter for its programming-oriented model of computation, and other results regarding characterizations in programming terms of the central complexity classes PTIME and LOGSPACE, as well as a new approach to complete problems for NLOGSPACE, PTIME, NPTIME, and PSPACE, uniformly based on Boolean programs. Annotation c. by Book News, Inc., Portland, Or. 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 log2n 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 Computability and complexity theory should be of central concern to practitioners as well as theorists. Unfortunately, however, the field is known for its impenetrability. Neil Jones's goal as an educator and author is to build a bridge between computability and complexity theory and other areas of computer science, especially programming. In a shift away from the Turing machine- and Gödel number-oriented classical approaches, Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists and more applicable to practical programming problems.According to Jones, the fields of computability and complexity theory, as well as programming languages and semantics, have a great deal to offer each other. Computability and complexity theory have a breadth, depth, and generality not often seen in programming languages. The programming language community, meanwhile, has a firm grasp of algorithm design, presentation, and implementation. In addition, programming languages sometimes provide computational models that are more realistic in certain crucial aspects than traditional models.New results in the book include a proof that constant time factors do matter for its programming-oriented model of computation. (In contrast, Turing machines have a counterintuitive "constant speedup" property: that almost any program can be made to run faster, by any amount. Its proof involves techniques irrelevant to practice.) Further results include simple characterizations in programming terms of the central complexity classes PTIME and LOGSPACE, and a new approach to complete problems for NLOGSPACE, PTIME, NPTIME, and PSPACE, uniformly based on Boolean programs.Foundations of Computing series Computability and complexity theory should be of central concern to practitioners as well as theorists. Unfortunately, however, the field is known for its impenetrability. Neil Jones's goal as an educator and author is to build a bridge between computability and complexity theory and other areas of computer science, especially programming. In a shift away from the Turing machine- and Gdel number-oriented classical approaches, Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists and more applicable to practical programming problems. According to Jones, the fields of computability and complexity theory, as well as programming languages and semantics, have a great deal to offer each other. Computability and complexity theory have a breadth, depth, and generality not often seen in programming languages. The programming language community, meanwhile, has a firm grasp of algorithm design, presentation, and implementation. In addition, programming languages sometimes provide computational models that are more realistic in certain crucial aspects than traditional models. New results in the book include a proof that constant time factors do matter for its programming-oriented model of computation. (In contrast, Turing machines have a counterintuitive "constant speedup" that almost any program can be made to run faster, by any amount. Its proof involves techniques irrelevant to practice.) Further results include simple characterizations in programming terms of the central complexity classes PTIME and LOGSPACE, and a new approach to complete problems for NLOGSPACE, PTIME, NPTIME, and PSPACE, uniformly based on Boolean programs. Foundations of Computing series