COMPUTABILITY An introduction to recursive function theory

【实例简介】
COMPUTABILITY An introduction to recursive function theory一书，可计算理论的教，pdf版，比较清晰。
COMPUTABILITY An introduction to recursive function theory NIGEL CUTLAND Department of Pure Mathematics, University of hull CAMBRIDGE UNIVERSITY PRESS Cambridge London New York New rochelle Melbourne Sydney Published by the Press Syndicate of the unive of brid The Pitt Building, Trumpington Street, Cambridge CB2 1RP 32 East 57th Street, New York, NY 10022, USA 296 Beaconsfield Parade. Middle Park, Melbourne 3206. Australia C Cambridge University Press 1980 First published 19b0 Printed in Great Britain by J w. Arrowsmith Ltd, Bristol Library of co P aloguing in Publcation Computability: an introduction to recursive function theory. Bibliography: p. de 1. Computable functions. 2. Re y.L. Title QA959c8751947951823 isbn 0 521 22384 9 hard covers ISBN0521294657 Contents Prefs Prologue. Prerequisites and notation 2 Functions 3 Relations and predicates 4 Logical notation 1 Computable function 1 Alg 2 The unlimited register machine 3 URM-computable functions 16 4 Decidable predicates and problems 22 5 Computability on other domains 2 Generating computable functions 25 1 The basic functi 25 2 Joining programs together 25 3 Substitution 29 4 Recursion 32 5 Minimalization 42 3 Other approaches to computability: Churchs thesis 48 Other approaches to computability 48 Partial recursi (Godel-Kl 49 3 A digression: the primitive recursive functions 51 4 Turing-computability 52 5 Symbol manipulation systems of Post and Marke tabili d other than n 65 7 Churchs thesj Numbering computable functions ring programs 72 <2 Numbering computable functions 76 i3 Discussion: the diagonal method 4 The s-mt-h theorem 81 Contents 5 Universal programs 85 1 Universal functions and universal programs 85 2 Two applications of the universal program 90 3 Effective operations on computable functions 93 Appendix. Computability of the function om 6 Decidability, undecidability and partial decidability 1 Undecidable problems in computability 101 2 The word problem for groups 106 3 Diophantine equations 4 Sturm's algorit 108 5 Mathematical logic 109 6 Partially decidable predicates 7 Recursive and recursively enumerable sets 121 1 Recursive sets 121 2 Recursively enumerable sets 123 3 Productive and creative sets 133 4 Simple sets 8 Arithmetic and Godel's incompleteness theorem 143 1 Formal arithmetic 143 146 3 Godels incompleteness theorem 149 4 Undecidability 155 9 Reducibility and degrees 157 y 158 161 3 m-complete r e sets 165 4 Relati mputabilit 167 Turing reducibility and turi 174 10 Effective operations on partial functions 182 1 The second Recursion theorem 182 2 Effecti Itable functions 189 3 The first Recursion th 4 An application to the semantics of programming languages 196 11 The second Recursion theorem 1 The second Recursion theorem 2 Discus 207 3 Myhill's theorem 12 Complexity of computation 212 1 Complexity and complexity measures 213 2 The Speed-up theorem 218 3 Complexity cl 223 4 The elementary 225 Contents 13 Further study 236 Bibliography 239 Index of notation Subject Index 246 reface The emergence of the concept of a computable function over fifty years ago marked the birth of a new branch of mathematics: its importance may be judged from the fact that it has had applications and implications in fields as diverse as computer science, philosophy and the foundations of mathematics, as well as in many other areas of mathematics itself. This book is designed to be an introduction to the basic ideas and results of computability theory (or recursion theory, as it is traditionally known among mathematicians) The initial purpose of computability theory is to make precise the intuitive idea of a computable function; that is, a function whose values can be calculated in some kind of automatic or effective way. Thereby we can gain a clearer understanding of this intuitive idea; and only thereby can we begin to explore in a mathematical way the concept of compu- tability as well as the many related ideas such as decidability and effective enumerability. A rich theory then arises, having both positive and negative aspects(here we are thinking of non-computability and undeci- dability results), which it is the aim of this book to introduce We could describe computability theory, from the viewpoint of computer science, as beginning with the question what can computers do principle (without restrictions of space, time or money)?-and, by implication - What are their inherent theoretical limitations? Thus this book is not about real computers and their hardware, nor is it about programming languages and techniques. Nevertheless, our subject matter is part of the theoretical background to the real world of computers and their use, and should be of interest to the computin communit For the basic definition of computability we have used the"idealised computer'orregister machine approach; we have found that this is readily grasped by students, most of whom are aware of the idea of a computer (We do not, however, assume such an awareness(although it is helpful) and even less do we assume any practical experience with computers or calculators. )Our approach is mathematically equivalent to the many others that have been discovered, including Turing machines, the favourite of many. (We discuss these equivalences in chapter 3. This text grew out of a course given to undergraduates in mathematics and computer science at the University of Hull. The reader envisaged is a mathematics student with no prior knowledge of this subject, or a student of computer science who may wish to supplement his practical expertise with something of the theoretical back ground to his subject. We have aimed at the second or third year undergraduate level, although the earlier chapters covering the basic theory(chapters 1-7)should be within the grasp of good students in sixth forms, high schools and colleges(and their teachers). The anly prerequisites are knowledge of the mathemati- cal language of sets and functions (reviewed in the Prologue)and the ability to follow a line of mathematical reasoning The later chapters(8-12) are largely independent of each other. Thus a short introductory course could consist of chapters 1-7 supplemented by selection according to taste from chapters 8-12. It has been our aim in these later chapters to provide an introduction to some of the ramifications and applications of basic computability theory and thereby provide a stepping stone towards more advanced study. To this end, the final chapter contains a brief survey of possible directions for further study, and some suggestions for further reading. The two main texts that might be regarded as natural sequels to this one are M. L. Minsky, Computation: Finite and infinite Machines, which would complement the present volume by its broad and comprehensive study of computation (as opposed to computability), and h. rogers, Theory of recursive Functions and Efective Computability, which provides a more advanced treatment of recursion theory in depth. Many people have helped towards the writing of this book. I would first hank John Cleave, who taught me recursive function theory in a gradu ate course at the University of Bristol in 1966, and introduced me to the register machine approach that i have used here. i have greatly appreci ated the sustained interest and encouragement from Stan Wainer(who also made valuable suggestions for the material in chapters 10 and 12) and David Jordan I thank them. i would also like to thank david Jordan and Dick Epstein for reading a draft of the manuscript and making many valuable comments and corrections. I am grateful to the Cambridge University Press for their interest and advice which has resulted in the emergence of the completed manuscript Prefs Finally, a big thank you to my wife mary for her patience and encouragement during the many phases of writing and preparation of this book; her idealism and understanding have been a sustaining influence throughout 【实例截图】
【核心代码】