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