computability

可计算理论中的国际经典教材,适合较为专业的人来查阅COMPUTABILITYAn introduction to recursive function theoryNIGEL CUTLANDDepartment of Pure Mathematics, University of hullCAMBRIDGE UNIVERSITY PRESSCambriageLondon New York New rochelleMelbourne SydneyPublished by the Press Syndicate of the University of CambridgeThe Pitt Building, Trumpington Street, Cambridge CB2 1RP32 East 57th Street, New York, NY 10022, USA296 Beaconsfield Parade, Middle Park, Melbourne 3206, AustraliaC Cambridge University Press 1980First published 1980Printed in Great Britain by w. Arrowsmith Ltd, BristolLibrary of Congress Cataloguing in Publication DataCutland, NigelComputability: an introduction to recursive function theory.Bibliography: pIncludes index1. Computable functions. 2. Recursion theory. I. TitleQA959C8751947951823isbN 0 521 22384 9 hard coversisbn 0 521 29465 7 paperbackContentsPefacePrologue. Prerequisites and notation1 Sets2 Functions3 Relations and predicates4 Logical notation5 References1 Computable functions1 Algorithms, or effective procedures24457792 The unlimited register machine3 URM-computable functions164 Decidable predicates and problems225 Computability on other domains2 Generating computable functions251 The basic functions2 Joining programs together253 Substitution294 Recursion5 Minimalisation423 Other approaches to computability: Church's thesis481 other approaches to computability48pArtial recursive functions(Godel-Kleene)493A digression: the primitive recursive functions4 Turing-computability525 Symbol manipulation systems of post and markov576 Computability on domains other than N657 Church's thesis674 Numbering computable functions72Numbering programs72Numbering computable functions763 Discussion: the diagonal method4 The s-m-n theorem81Contents5 Universal programs851 Universal functions and universal programs852 Two applications of the universal program903 Effective operations on computable functions93Appendix. Computability of the function on956 Decidability, undecidability and partial decidability1 Undecidable problems in computability1012 The word problem for groups1063 Diophantine equations4 Sturm's algorithMathematical logic6 Partially decidable predicates1127 Recursive and recursively enumerable sets1211 Recursive sets1212 Recursively enumerable sets1233 Productive and creative sets1334 Simple sets140f Arithmetic and Godel's incompleteness theorem1431 Formal arithmetic1432 Incompleteness1463 Godel's incompleteness theorem1494 Undecidability1559 Reducibility and degrees1571 Many-one reducibility1582 Degrees1613 m-complete r.e. sets1654 Relative computability1675 Turing reducibility and Turing degrees17410 Effective operations on partial functions1821 The second Recursion theorem1822 Effective operations on computable functions1893 The first Recursion theorem1924 An application to the semantics of programming languages 19611 The second Recursion theorem2001 The second Recursion theorem2002 Discussion2073 Myhill's theorem21012 Complexity of computation1 Complexity and complexity measures2132 The Speed-up theorem218Complexity classes2234 The elementary functions225Contents13 Further study236Bibliograph239Index of notation241Subject Index246PrefaceThe emergence of the concept of a computable function over fifty yearsago marked the birth of a new branch of mathematics: its importance maybe judged from the fact that it has had applications and implications infields as diverse as computer science, philosophy and the foundations ofmathematics, as well as in many other areas of mathematics itself. Thisbook is designed to be an introduction to the basic ideas and results ofcomputability theory (or recursion theory, as it is traditionally knownamong mathematicians)The initial purpose of computability theory is to make precise theintuitive idea of a computable function; that is, a function whose valuescan be calculated in some kind of automatic or effective way. Thereby wecan gain a clearer understanding of this intuitive idea; and only therebycan we begin to explore in a mathematical way the concept of computability as well as the many related ideas such as decidability and effectiveenumerability. A rich theory then arises, having both positive andnegative aspects(here we are thinking of non-computability and undeci-dability results), which it is the aim of this book to introduceWe could describe computability theory, from the viewpoint ofcomputer science, as beginning with the question What can computers doin principle (without restrictions of space, time or money )?-and, byimplication -What are their inherent theoretical limitations? Thus thisbook is not about real computers and their hardware, nor is it aboutprogramming languages and techniques. Nevertheless, our subjectmatter is part of the theoretical background to the real world ofcomputers and their use, and should be of interest to the computingcommunity.For the basic definition of computability we have used the ' idealisedcomputeror register machine approach; we have found that this is readilygrasped by students, most of whom are aware of the idea of a computer.(We do not, however, assume such an awareness(although it is helpfulPrefaceand even less do we assume any practical experience with computers orcalculators. ) Our approach is mathematically equivalent to the manyothers that have been discovered, including Turing machines, thefavourite of many. (We discuss these equivalences in chapter 3.This text grew out of a course given to undergraduates in mathematicand computer science at the University of Hull. The reader envisaged is amathematics student with no prior knowledge of this subject, or a studentof computer science who may wish to supplement his practical expertisewith something of the theoretical back ground to his subject. We haveaimed at the second or third year undergraduate level, although theearlier chapters covering the basic theory(chapters 1-7)should be withinthe grasp of good students in sixth forms, high schools and colleges(andtheir teachers). The only prerequisites are knowledge of the mathematical language of sets and functions (reviewed in the Prologue) and theability to follow a line of mathematical reasoningThe later chapters(8-12) are largely independent of each other. Thus ashort introductory course could consist of chapters 1-7 supplemented byselection according to taste from chapters 8-12. It has been our aim inthese later chapters to provide an introduction to some of theramifications and applications of basic computability theory, and therebyprovide a stepping stone towards more advanced study. To this end, thefinal chapter contains a brief survey of possible directions for furtherstudy, and some suggestions for further reading. (The two main texts thatmight be regarded as natural sequels to this one are M. L. minsky,Computation: Finite and Infinite Machines, which would complement thepresent volume by its broad and comprehensive study of computation(asopposed to computability), and h. rogers, Theory of recursive functionsand effective Computability, which provides a more advanced treatmentof recursion theory in depthMany people have helped towards the writing of this book. I would firstthank John Cleave, who taught me recursive function theory in a graduate course at the university of bristol in 1966, and introduced me to theregister machine approach that I have used here. i have greatly appreci-ated the sustained interest and encouragement from Stan wainer(whoalso made valuable suggestions for the material in chapters 10 and 12)and david jordan, i thank them i would also like to thank David Jordanand Dick Epstein for reading a draft of the manuscript and making manyvaluable comments and corrections. I am grateful to the CambridgeUniversity Press for their interest and advice which has resulted in theemergence of the completed manuscriptPrefaceFinally, a big thank you to my wife Mary for her patience andencouragement during the many phases of writing and preparation of thisbook; her idealism and understanding have been a sustaining influencethroughout