1. 1. What This Book is About This book is a study of subrecursive programming systems, efficiency/program-size trade-offs between such systems, and how these systems can serve as tools in complexity theory. Section 1. 1 states our basic themes, and Sections 1. 2 and 1. 3 give a general outline of the book. Our first task is to explain what subrecursive programming systems are and why they are of interest. 1. 1. 1. Subrecursive Programming Systems A subrecursive programming system is, roughly, a programming language for which the result of running any given program on any given input can be completely determined algorithmically. Typical examples are: 1. the Meyer-Ritchie LOOP language [MR67, DW83], a restricted assem bly language with bounded loops as the only allowed deviation from straight-line programming; 2. multi-tape 'lUring Machines each explicitly clocked to halt within a time bound given by some polynomial in the length ofthe input (see [BH79, HB79]); 3. the set of seemingly unrestricted programs for which one can prove 1 termination on all inputs (see [Kre51, Kre58, Ros84]); and 4. finite state and pushdown automata from formal language theory (see [HU79]). lOr, more precisely, the collection of programs, p, ofsome particular general-purpose programming language (e. g. , Lisp or Modula-2) for which there is a proof in some par ticular formal system (e. g. , Peano Arithmetic) that p halts on all inputs.
Inhaltsverzeichnis
1 Introduction. - 1. 1 What This Book is About. - 1. 2 Outline of Part I. A Subrecursion Programming Systems Toolkit. - 1. 3 Outline of Part II. Program Succinctness. - 1. 4 Brief History of Prior Results. - 1. 5 How to Use This Book. - 1. 6 Acknowledgments. - I A Subrecursion Programming Systems Toolkit. - 2 Basic Notation and Definitions. - 3 Deterministic Multi-tape Turing Machines. - 4 Programming Systems. - 5 The LOOP Hierarchy. - 6 The Poly-Degree Hierarchy. - 7 Delayed Enumeration and Limiting Recursion. - 8 Inseparability Notions. - 9 Toolkit Demonstrations. - II Program Succinctness. - 10 Notions of Succinctness. - 11 Limiting-Recursive Succinctness Progressions. - 12 Succinctness for Finite and Infinite Variants. - 13 Succinctness for Singleton Sets. - 14 Further Problems. - Appendix A Exercises. - Appendix B Solutions for Selected Exercises. - Notation Index.
