Subrecursive Programming Systems: Complexity & Succinctness (Progress in Theoretical Computer Science)

Chapter 1 - Introduction1.1. What This Book is AboutThis 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 SystemsA 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 assembly language with bounded loops as the only allowed deviation from straight-line programming;2. multi-tape Turing Machines each explicitly clocked to halt within a time bound given by some polynomial in the length of the input (see [BH79,HB79]);3. the set of seemingly unrestricted programs for which one can prove termination on all inputs1 (see [Kre51,Kre58,Ros84]); and4. finite state and pushdown automata from formal language theory (see [HU79]).Lisp and Modula-2 are not subrecursive programming systems since, for example, they have unsolvable halting problems (see [Rog67,DSW94]). Front Matter....Pages i-viii Introduction....Pages 1-18 Front Matter....Pages 19-19 Basic Notation and Definitions....Pages 21-30 Deterministic Multi-tape Turing Machines....Pages 31-55 Programming Systems....Pages 56-94 The LOOP Hierarchy....Pages 95-104 The Poly-Degree Hierarchy....Pages 105-112 Delayed Enumeration and Limiting Recursion....Pages 113-121 Inseparability Notions....Pages 122-127 Toolkit Demonstrations....Pages 128-151 Front Matter....Pages 153-153 Notions of Succinctness....Pages 155-161 Limiting-Recursive Succinctness Progressions....Pages 162-190 Succinctness for Finite and Infinite Variants....Pages 191-199 Succinctness for Singleton Sets....Pages 200-220 Further Problems....Pages 221-222 Back Matter....Pages 223-253