Subrecursive Programming systems: Complexity & Succinctness

What this book is about - subrecursive programming systems, relative succinctness trade-offs, the toolkit; outline of Part I - a subrecursion programming systems toolkit; outline of Part II - program succinctness; brief history of prior results; how to use this book; acknowledgments. Part 1 A subrecursion programming systems toolkit: basic notation and definitions - equation numbering, general notation and conventions, the standard pairing function, representing numbers, of lengths and logarithms, classes of sets and functions, programming systems and numberings, complexity measures, the arithmetic hierarchy, formal systems; deterministic multi-tape turing machines - details of the model - TM conventions, coding TMs, the standard acceptable programming system and complexity measures, the complexity of basic functions and operations, standard complexity classes; efficient universal simulation, costs of combining turing machines and efficiency of the combinations, TM normalisation; clocked TMs, combining TMs; slowed simulations; programming systems - closure properties and control structures, formalising the notion of a control structure, building control structures, clocked programming systems, formalizations, constructing clocked systems, inherited properties of clock systems, clocked systems for collections of sets, provably bounded programming systems, provably explicitly bounded systems, provably implicitly bounded systems, reducibility induced programming systems, induced systems and their properties, the generality of induced systems; the LOOP hierarchy; the poly-degree hierarchy; delayed enumeration and limiting recursion - uniform enumerations, limiting recursion, uniform limits; inseparability notions - productiveness and related notions, an-inseparability, en-inseparability; toolkit demonstrations: uniform density, a generalisation of uniform density, upper bounds on upward chains, minimal pairs, sufficient conditions for effective E2-inseparability. Part 2 Program succinctness: notions of succinctness - program size, relative succinctness - definitions, invariances and limitations, invariance with respect to program size measures, limits on succinctness, invariance under choice of programming systems, programming systems that represent classes of sets; limiting-recursive succinctness progressions - a technical prelude, the key theorem, a cornucopia of corollaries, a tight incompleteness theorem about complexity bounds, characterisations of limiting-recursive succinctness; succinctness for finite and infinite variant - the =m case, considerations for the =* and =x cases, the =* case, the =x case; succinctness for singleton sets - progressions for clocked systems, succinctness for programs with provable complexity; further problems. Appendices: exercises; solutions for selected exercises. Subject Index.