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.