目次

Foreword; Preface; Figures; 1. Introduction; Part I. Formalisms forComputation: Register Machines, Exponential Diophantine Equations, andPure LISP: 2. The arithmetization of register machines; 3. A version ofPure LISP; 4. The LISP interpreter EVAL; Part II. Program Size, HaltingProbabilities, Randomness, and Metamathematics: 5. Conceptualdevelopment; 6. Program size; 7. Randomness; 8. Incompleteness; 9.Conclusion; Bibliography.