Subrecursive Programming Systems
Birkhauser Boston Inc (Verlag)
978-0-8176-3767-5 (ISBN)
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.
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.
| Erscheint lt. Verlag | 1.8.1994 |
|---|---|
| Reihe/Serie | Progress in Theoretical Computer Science |
| Zusatzinfo | VIII, 253 p. |
| Verlagsort | Secaucus |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Themenwelt | Mathematik / Informatik ► Informatik ► Betriebssysteme / Server |
| Mathematik / Informatik ► Informatik ► Software Entwicklung | |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| ISBN-10 | 0-8176-3767-2 / 0817637672 |
| ISBN-13 | 978-0-8176-3767-5 / 9780817637675 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
