Classical Recursion Theory (eBook)

Cover 1
Copyright Page 5
Dedication 6
Foreword 8
Preface 10
Preface to the Second Edition 12
TOC$Contents 14
Introduction 22
What is 'Classical' 22
What is in the Book 23
Applications of Recursion Theory 26
How to Use the Book 32
Notations and Conventions 34
CH$Chapter I. Recursiveness and Computability 38
I.1 Induction 39
I.2 Systems of Equations 52
I.3 Arithmetical Formal Systems 60
I.4 Turing Machines 67
I.5 Flowcharts 82
I.6 Functions as Rules 96
I.7 Arithmetization 108
I.8 Church's Thesis 122
CH$Chapter II. Basic Recursion Theory 146
II.1 Partial Recursive Functions 147
II.2 Diagonalization 166
II.3 Partial Recursive Functionals 195
II.4 Effective Operations 226
II.5 Indices and Enumerations 235
II.6 Retraceable and Regressive Sets 259
CH$Chapter III. Post's Problem and Strong Reducibilities 272
III.1 Post's Problem 273
III.2 Simple Sets and Many-One Degrees 277
III.3 Hypersimple Sets and Truth-Table Degrees 288
III.4 Hyperhypersimple Sets and Q-Degrees 301
III.5 A Solution to Post's Problem 315
III.6 Creative Sets and Completeness 325
III.7 Recursive Isomorphism Types 340
III.8 Variations of Truth-Table Reducibility 351
III.9 The World of Complete Sets 362
III.10 Formal Systems and R.E. Sets 370
CH$Chapter IV. Hierarchies and Weak Reducibilities 382
IV.l The Arithmetical Hierarchy 384
IV.2 The Analytical Hierarchy 396
IV.3 The Set-Theoretical Hierarchy 418
IV.4 The Constructible Hierarchy 443
CH$Chapter V. Turing Degrees 468
V.1 The Language of Degree Theory 469
V.2 The Finite Extension Method 477
V.3 Baire Category 492
V.4 The Coinfinite Extension Method 505
V.5 The Tree Method 514
V.6 Initial Segments 537
V.7 Global Properties 551
V.8 Degree Theory with Jump 571
CH$Chapter VI. Many-One and Other Degrees 576
VI.1 Distributivity 576
VI.2 Countable Initial Segments 582
VI.3 Uncountable Initial Segments 590
VI.4 Global Properties 595
VI.5 Comparison of Degree Theories 603
VI.6 Structure Inside Degrees 612
Bibliography 624
Notation Index 664
IDX$Subject Index 670