Introduction
3

The WHILE Language
27

Programs as Data Objects
47

Universal Programs for WHILE and I
69

Metaprogramming Selfapplication and Compiler Generation
89

Other Sequential Models of Computation
111

Robustness of Computability
127

Some Natural Unsolvable Problems
151

Overview of Complexity Theory
239

Time Usage of Treemanipulating Programs
261

Linear and Other Time Hierarchies for WHILE Programs
285

Spacebounded Computations
315

Nondeterministic Computations
331

Characterizations of LOGSPACE and PTIME by GOTO Programs
349

Completeness and Reduction of One Problem to Another
365

Complete Problems for PTIME
383

Hilberts Tenth Problem by M H Serensen
167

Inference Systems and Godels Incompleteness Theorem
187

Computability Theory Based on Numbers
205

More Abstract Approaches to Computability
215

Complete Problems for NPTIME
397

Appendix
412

Bibliography
447