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.
Le informazioni nella sezione "Riassunto" possono far riferimento a edizioni diverse di questo titolo.
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.
Book by Royer James S Case John
Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.
EUR 4,64 per la spedizione da Regno Unito a Italia
Destinazione, tempi e costiGRATIS per la spedizione da U.S.A. a Italia
Destinazione, tempi e costiDa: Phatpocket Limited, Waltham Abbey, HERTS, Regno Unito
Condizione: Like New. Used - Like New. Book is new and unread but may have minor shelf wear. Your purchase helps support Sri Lankan Children's Charity 'The Rainbow Centre'. Our donations to The Rainbow Centre have helped provide an education and a safe haven to hundreds of children who live in appalling conditions. Codice articolo Z1-F-038-01618
Quantità: 2 disponibili
Da: Romtrade Corp., STERLING HEIGHTS, MI, U.S.A.
Condizione: New. This is a Brand-new US Edition. This Item may be shipped from US or any other country as we have multiple locations worldwide. Codice articolo ABNR-91868
Quantità: 1 disponibili
Da: Basi6 International, Irving, TX, U.S.A.
Condizione: Brand New. New. US edition. Expediting shipping for all USA and Europe orders excluding PO Box. Excellent Customer Service. Codice articolo ABEJUNE24-129828
Quantità: 1 disponibili
Da: moluna, Greven, Germania
Gebunden. Condizione: New. Dieser Artikel ist ein Print on Demand Artikel und wird nach Ihrer Bestellung fuer Sie gedruckt. 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 Succinct. Codice articolo 5975490
Quantità: Più di 20 disponibili
Da: buchversandmimpf2000, Emtmannsberg, BAYE, Germania
Buch. Condizione: Neu. This item is printed on demand - Print on Demand Titel. Neuware -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.Springer Basel AG in Springer Science + Business Media, Heidelberger Platz 3, 14197 Berlin 264 pp. Englisch. Codice articolo 9780817637675
Quantità: 1 disponibili
Da: AHA-BUCH GmbH, Einbeck, Germania
Buch. Condizione: Neu. Druck auf Anfrage Neuware - Printed after ordering - 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. Codice articolo 9780817637675
Quantità: 1 disponibili
Da: Ria Christie Collections, Uxbridge, Regno Unito
Condizione: New. In. Codice articolo ria9780817637675_new
Quantità: Più di 20 disponibili
Da: Books Puddle, New York, NY, U.S.A.
Condizione: Used. pp. 264. Codice articolo 263099809
Quantità: 1 disponibili
Da: Majestic Books, Hounslow, Regno Unito
Condizione: Used. pp. 264 52:B&W 6.14 x 9.21in or 234 x 156mm (Royal 8vo) Case Laminate on White w/Gloss Lam. Codice articolo 5829502
Quantità: 1 disponibili
Da: Biblios, Frankfurt am main, HESSE, Germania
Condizione: Used. pp. 264. Codice articolo 183099819
Quantità: 1 disponibili