Bookstore

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.

Subrecursive Programming Systems: Complexity & Succinctness

1 Introduction.- 1.1 What This Book is About.- 1.1.1 Subrecursive Programming Systems.- 1.1.2 Relative Succinctness Trade-offs.- 1.1.3 The Toolkit.- 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.- 2.1 Equation Numbering.- 2.2 General Notation and Conventions.- 2.3 The Standard Pairing Function.- 2.4 Representing Numbers.- 2.5 Of Lengths and Logarithms.- 2.6 Classes of Sets and Functions.- 2.7 Programming Systems and Numberings.- 2.8 Complexity Measures.- 2.9 The Arithmetic Hierarchy.- 2.10 Formal Systems.- 3 Deterministic Multi-tape Turing Machines.- 3.1 Details of the Model.- 3.1.1 TM Conventions.- 3.1.2 Coding TMs.- 3.1.3 The Standard Acceptable Programming System and Complexity Measures.- 3.1.4 The Complexity of Basic Functions and Operations..- 3.1.5 Standard Complexity Classes.- 3.1.6 Efficient Universal Simulation.- 3.2 Costs of Combining Turing Machines and Efficiency of the Combinations.- 3.2.1 TM Normalization.- 3.2.2 Clocked TMs.- 3.2.3 Combining TMs.- 3.2.4 Slowed Simulations.- 4 Programming Systems.- 4.1 Closure Properties and Control Structures.- 4.1.1 Formalizing the Notion of a Control Structure.- 4.1.2 Building Control Structures.- 4.2 Clocked Programming Systems.- 4.2.1 Formalizations.- 4.2.2 Constructing Clocked Systems.- 4.2.3 Inherited Properties of Clocked Systems.- 4.2.4 Clocked Systems for Collections of Sets.- 4.3 Provably Bounded Programming Systems.- 4.3.1 Provably Explicitly Bounded Systems.- 4.3.2 Provably Implicitly Bounded Systems.- 4.4 Reducibility Induced Programming Systems.- 4.4.1 Induced Systems and Their Properties.- 4.4.2 The Generality of Induced Systems.- 5 The LOOP Hierarchy.- 6 The Poly-Degree Hierarchy.- 7 Delayed Enumeration and Limiting Recursion.- 7.1 Uniform Enumerations.- 7.2 Limiting Recursion.- 7.3 Uniform Limits.- 8 Inseparability Notions.- 8.1 Productiveness and Related Notions.- 8.2 ?n-Inseparability.- 8.3 ?n-Inseparability.- 9 Toolkit Demonstrations.- 9.1 Uniform Density.- 9.2 A Generalization of Uniform Density.- 9.3 Upper Bounds on Upward Chains.- 9.4 Minimal Pairs.- 9.5 Sufficient Conditions for Effective ?2-Inseparability.- II Program Succinctness.- 10 Notions of Succinctness.- 10.1 Program Size.- 10.2 Relative Succinctness: Definitions.- 10.3 Invariances and Limitations.- 10.3.1 Invariance with Respect to Program Size Measures..- 10.3.2 Limits on Succinctness.- 10.3.3 Invariance Under Choice of Programming Systems ..- 10.3.4 Programming Systems That Represent Classes of Sets.- 11 Limiting-Recursive Succinctness Progressions.- 11.1 A Technical Prelude.- 11.2 The Key Theorem.- 11.3 A Cornucopia of Corollaries.- 11.4 A Tight Incompleteness Theorem about Complexity Bounds.- 11.5 Characterizations of Limiting-Recursive Succinctness.- 12 Succinctness for Finite and Infinite Variants.- 12.1 The =m Case.- 12.2 Considerations for the =* and =? Cases.- 12.3 The =* Case.- 12.4 The =? Case.- 13 Succinctness for Singleton Sets.- 13.1 Progressions for Clocked Systems.- 13.2 Succinctness for Programs with Provable Complexity.- 14 Further Problems.- Appendix A Exercises.- Appendix B Solutions for Selected Exercises.- Notation Index.