UID:
almahu_9947367990402882
Format:
1 online resource (689 p.)
Edition:
[2nd ed.].
ISBN:
1-281-75468-4
,
9786611754686
,
0-08-088659-0
Series Statement:
Studies in logic and the foundations of mathematics ; v. 125
Content:
1988 marked the first centenary of Recursion Theory, since Dedekind's 1888 paper on the nature of number. Now available in paperback, this book is both a comprehensive reference for the subject and a textbook starting from first principles. Among the subjects covered are: various equivalent approaches to effective computability and their relations with computers and programming languages; a discussion of Church's thesis; a modern solution to Post's problem; global properties of Turing degrees; and a complete algebraic characterization of many-one degrees. Included are a number of application
Note:
Description based upon print version of record.
,
Cover; Copyright Page; Dedication; Foreword; Preface; Preface to the Second Edition; TOCContents; Introduction; What is 'Classical'; What is in the Book; Applications of Recursion Theory; How to Use the Book; Notations and Conventions; CHChapter I. Recursiveness and Computability; I.1 Induction; I.2 Systems of Equations; I.3 Arithmetical Formal Systems; I.4 Turing Machines; I.5 Flowcharts; I.6 Functions as Rules; I.7 Arithmetization; I.8 Church's Thesis; CHChapter II. Basic Recursion Theory; II.1 Partial Recursive Functions; II.2 Diagonalization; II.3 Partial Recursive Functionals
,
II.4 Effective OperationsII.5 Indices and Enumerations; II.6 Retraceable and Regressive Sets; CHChapter III. Post's Problem and Strong Reducibilities; III.1 Post's Problem; III.2 Simple Sets and Many-One Degrees; III.3 Hypersimple Sets and Truth-Table Degrees; III.4 Hyperhypersimple Sets and Q-Degrees; III.5 A Solution to Post's Problem; III.6 Creative Sets and Completeness; III.7 Recursive Isomorphism Types; III.8 Variations of Truth-Table Reducibility; III.9 The World of Complete Sets; III.10 Formal Systems and R.E. Sets; CHChapter IV. Hierarchies and Weak Reducibilities
,
IV.l The Arithmetical HierarchyIV.2 The Analytical Hierarchy; IV.3 The Set-Theoretical Hierarchy; IV.4 The Constructible Hierarchy; CHChapter V. Turing Degrees; V.1 The Language of Degree Theory; V.2 The Finite Extension Method; V.3 Baire Category; V.4 The Coinfinite Extension Method; V.5 The Tree Method; V.6 Initial Segments; V.7 Global Properties; V.8 Degree Theory with Jump; CHChapter VI. Many-One and Other Degrees; VI.1 Distributivity; VI.2 Countable Initial Segments; VI.3 Uncountable Initial Segments; VI.4 Global Properties; VI.5 Comparison of Degree Theories
,
VI.6 Structure Inside DegreesBibliography; Notation Index; IDXSubject Index
,
English
Additional Edition:
ISBN 0-444-87295-7
Additional Edition:
ISBN 0-444-89483-7
Language:
English
