Subrecursive Programming Systems - Complexity & Succinctness (Hardcover, 1994 ed.)

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.

General

Imprint:	Birkhauser Boston
Country of origin:	United States
Series:	Progress in Theoretical Computer Science
Release date:	August 1994
First published:	1994
Authors:	James S. Royer • John Case
Dimensions:	235 x 155 x 15mm (L x W x T)
Format:	Hardcover
Pages:	253
Edition:	1994 ed.
ISBN-13:	978-0-8176-3767-5
Categories:	Books > Computing & IT > General theory of computing > Mathematical theory of computation Books > Computing & IT > Computer programming > General Promotions
LSN:	0-8176-3767-2
Barcode:	9780817637675

Is the information for this product incomplete, wrong or inappropriate? Let us know about it.

Does this product have an incorrect or missing image? Send us a new image.

Is this product missing categories? Add more categories.

Review This Product

No reviews yet - be the first to create one!