Computability And Complexity From A Programming Perspective

Cover......Page 1
Copyright......Page 2
Contents......Page 3
Preface......Page 5
List of Notations......Page 13
1 Introduction......Page 14
2 The While Language......Page 38
3 Programs as Data Objects......Page 57
4 Self-Interpretation: Universal Programs for WHILE and I......Page 77
5 Elements of Computability Theory......Page 83
6 Metaprogramming, Self-Application, and Compiler Generation......Page 97
7 Other Sequential Models of Computation......Page 119
8 Robustness of Computability......Page 134
9 Computability by Functional Languages......Page 144
10 Some Natural Unsolvable Problems......Page 158
11 Hilbert's Tenth Problem......Page 172
12 Inference Systems and Godel's Incompleteness Theorem......Page 191
13 Computability Theory Based on Numbers......Page 209
14 More Abstract Approaches to Computability......Page 218
15 Overview of Complexity Theory......Page 241
16 Measuring Time Usage......Page 251
17 Time Usage of Tree-Manipulating Programs......Page 263
18 Robustness of Time-Bounded Computation......Page 273
19 Linear and Other Time Hierarchies for WHILE Programs......Page 287
20 The Existence of Optimal Algorithms......Page 298
21 Space-Bounded Computations......Page 316
22 Nondeterministic Computations......Page 332
23 A Structure for Classifying the Complexity of Various Problems......Page 335
24 Characterizations of LOGSPACE and PTIME by GOTO Programs......Page 348
25 Completeness and Reduction of One Problem to Another......Page 362
26 Complete Problems for PTIME......Page 379
27 Complete Problems for NPTIME......Page 393
28 Complete Problems for PSPACE......Page 402
Appendix......Page 412
Bibliography......Page 441
Index......Page 450