Basic Recursive Function Theory
In the last section, we examined some reasonable models of computation. These models were found to be equivalent in the sense that they captured the same class of “computable” functions. Now we proceed to define our “generic” programming system syntactica
- PDF / 13,331,618 Bytes
- 155 Pages / 430.87 x 649.13 pts Page_size
- 1 Downloads / 221 Views
Cari H. Smith
A RECURSIVE INTRODUCTION TO THE THEORY OF COMPUTATION
Springer Science+Business Media, LLC
Carl H. Smith Department of Computer Science University of Maryland College Park, MD 20742 USA
Series Editors David Gries Fred B. Schneider Department of Computer Science Cornell University Upson Hall Ithaca, NY 14853-7501 USA
Library of Gongress Gataloging-in-Publication Data Smith, Garl. 1950A recursive introduction to the theory of computation / Garl Smith. p. cm. - (Graduate texts in computer science) Includes index. ISBN 978-1-4612-6420-0 ISBN 978-1-4419-8501-9 (eBook) DOI 10.1007/978-1-4419-8501-9
1. Electronic digital computers-Programming. 2. Recursive functions-Data processing. I. Title. 11. Series. QA76.6.S61547 1994 511.3'5-dc20 94-21785 Printed on acid-free paper. © 1994 Springer Science+Business Media New York Originally published by Springer-Verlag New York, Ine in 1994 Softcover reprint of the hardcover 1st edition 1994 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science + Business Media, LLC), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known, or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone.
Production coordinated by Publishing Network and managed by Henry Krell; manufacturing supervised by Jacqui Ashri. Photocomposed copy prepared from the author's LaTeX files.
987654321 ISBN 978-1-4612-6420-0
Preface
Once upon a time, I was quite content to use the excellent text An Introduction to the General Theory of Algorithms by M. Machtey and P. Young for my graduate theory of computation course. After the publisher declined to reprint the book , I hastily threw together some notes. Consequently, much of the organization, notation and actual proofs were taken straight from Machtey and Young's book. The notes soon took an electronic form . What follows is the result of several semesters' worth of embellishments and classroom testing. Over the semesters, many students have found typos, suggested clarifications and come up with interesting questions that became exercises. This document has been significantly improved due to their efforts. I would also like to thank my colleague Bill Gasarch for proofreading, discussions, agreements, disagreements and for creating a large cardinal number of problems. Ken Regan and the anonymous referees made several valuable comments. The material presented can be covered in a single semester. I have resisted the temptation to add material "to be covered, time permitting" since what material I would want to add c
Data Loading...
