دانلود کتاب The Foundations of Computability Theory

فهرست مطالب :

Preface
Context
Aims
Contents
Approach
Audience
Teaching
Origin
Acknowledgments
Preface to the Second Edition
Acknowledgments for the Second Edition
Contents
Part I THE ROOTS OF COMPUTABILITY THEORY
Chapter 1 Introduction
1.1 Algorithms and Computation
1.1.1 The Intuitive Concept of the Algorithm and Computation
1.1.2 Algorithms and Computations Before the Twentieth Century
1.2 Chapter Summary
Chapter 2 The Foundational Crisis of Mathematics
2.1 Crisis in Set Theory
2.1.1 Axiomatic Systems
2.1.2 Cantor’s Naive Set Theory
2.1.3 Logical Paradoxes
2.2 Schools of Recovery
2.2.1 Slowdown and Revision
2.2.2 Intuitionism
2.2.3 Logicism
2.2.4 Formalism
2.3 Chapter Summary
Chapter 3 Formalism
3.1 Formal Axiomatic Systems and Theories
3.1.1 What Is a Formal Axiomatic System?
3.1.2 The Notion of Truth
3.1.3 Interpretations and Models
3.2 Formalization of Logic, Arithmetic, and Set Theory
3.3 Chapter Summary
Chapter 4 Hilbert’s Attempt at Recovery
4.1 Hilbert’s Program
4.1.1 Fundamental Problems of the Foundations of Mathematics
4.1.2 Hilbert’s Program
4.2 The Fate of Hilbert’s Program
4.2.1 Formalization of Mathematics: Formal Axiomatic System M
4.2.2 Decidability of M: Entscheidungsproblem
4.2.3 Completeness of M: Godel’s First Incompleteness Theorem
4.2.4 Consequences of the First Incompleteness Theorem
4.2.5 Consistency of M: Godel’s Second Incompleteness Theorem
4.2.6 Consequences of the Second Incompleteness Theorem
4.3 Legacy of Hilbert’s Program
4.4 Chapter Summary
Problems
Bibliographic Notes
Part II CLASSICAL COMPUTABILITY THEORY
Chapter 5 The Quest for a Formalization
5.1 What Is an Algorithm and What DoWe Mean by Computation?
5.1.1 Intuition and Dilemmas
5.1.2 The Need for Formalization
5.2 Models of Computation
5.2.1 Modeling After Functions
5.2.2 Modeling After Humans
5.2.3 Modeling After Languages
5.2.4 Reasonable Models of Computation
5.3 Computability (Church-Turing) Thesis
5.3.1 History of the Thesis
5.3.2 The Thesis
5.3.3 Difficulties with Total Functions
5.3.4 Generalization to Partial Functions
5.3.5 Applications of the Thesis
5.4 Chapter Summary
Problems
Bibliographic Notes
Chapter 6 The Turing Machine
6.1 Turing Machine
6.1.1 Basic Model
6.1.2 Generalized Models
6.1.3 Equivalence of Generalized and Basic Models
6.1.4 Reduced Model
6.1.5 Equivalence of Reduced and Basic Models
6.1.6 Use of Different Models
6.2 Universal Turing Machine
6.2.1 Coding and Enumeration of Turing Machines
6.2.2 The Existence of a Universal Turing Machine
6.2.3 The Importance of the Universal Turing Machine
6.2.4 Practical Consequences: Data vs. Instructions
6.2.5 Practical Consequences: General-Purpose Computer
6.2.6 Practical Consequences: Operating System
6.2.7 Practical Consequences: RAM Model of Computation
6.3 Use of a Turing Machine
6.3.1 Function Computation
6.3.2 Set Generation
6.3.3 Set Recognition
6.3.4 Generation vs. Recognition
6.3.5 The Standard Universes and N
6.3.6 Formal Languages vs. Sets of Natural Numbers
6.4 Chapter Summary
Problems
Bibliographic Notes
Chapter 7 The First Basic Results
7.1 Some Basic Properties of Semi-decidable (C.E.) Sets
7.2 Padding Lemma and Index Sets
7.3 Parameter (s-m-n) Theorem
7.3.1 Deduction of the Theorem
7.4 Recursion (Fixed-Point) Theorem
7.4.1 Deduction of the Theorem
7.4.2 Interpretation of the Theorem
7.4.3 Fixed Points of Functions
7.4.4 Practical Consequences: Recursive Program Definition
7.4.5 Practical Consequences: Recursive Program Execution
7.4.6 Practical Consequences: Procedure Calls in General-Purpose Computers
7.5 Chapter Summary
Problems
Bibliographic Notes
Chapter 8 Incomputable Problems
8.1 Problem Solving
8.1.1 Decision Problems and Other Kinds of Problems
8.1.2 Language of a Decision Problem
8.1.3 Subproblems of a Decision Problem
8.2 There Is an Incomputable Problem — Halting Problem
8.2.1 Consequences: The Basic Kinds of Decision Problems
8.2.2 Consequences: Complementary Sets and Decision Problems
8.2.3 Consequences: There Is an Incomputable Function
8.3 Some Other Incomputable Problems
8.3.1 Problems About Turing Machines
8.3.2 Post’s Correspondence Problem
8.3.3 Problems About Algorithms and Computer Programs
8.3.4 Problems About Programming Languages and Grammars
8.3.5 Problems About Computable Functions
8.3.6 Problems from Number Theory
8.3.7 Problems from Algebra
8.3.8 Problems from Analysis
8.3.9 Problems from Topology
8.3.10 Problems from Mathematical Logic
8.3.11 Problems About Games
8.4 Can We Outwit Incomputable Problems?
8.5 Chapter Summary
Problems
Bibliographic Notes
Chapter 9 Methods of Proving Incomputability
9.1 Proving by Diagonalization
9.1.1 Direct Diagonalization
9.1.2 Indirect Diagonalization
9.2 Proving by Reduction
9.2.1 Reductions in General
9.2.2 The m-Reduction
9.2.3 Undecidability and m-Reduction
9.2.4 The 1-Reduction
9.3 Proving by the Recursion Theorem
9.4 Proving by Rice’s Theorem
9.4.1 Rice’s Theorem for P.C. Functions
9.4.2 Rice’s Theorem for Index Sets
9.4.3 Rice’s Theorem for C.E. Sets
9.4.4 Consequences: Behavior of Abstract Computing Machines
9.5 Incomputability of Other Kinds of Problems
9.6 Chapter Summary
Problems
Bibliographic notes
Part III RELATIVE COMPUTABILITY
Chapter 10 Computation with External Help
10.1 Turing Machines with Oracles
10.1.1 Turing’s Idea of Oracular Help
10.1.2 The Oracle Turing Machine (o-TM)
10.1.3 Some Basic Properties of o-TMs
10.1.4 Coding and Enumeration of o-TMs
10.2 Computation with Oracles
10.2.1 Generalization of Classical Definitions
10.2.2 Convention: The Universe N and Single-Argument Functions
10.3 Other Ways to Make External Help Available
10.4 Relative Computability Thesis
10.5 Practical Consequences: o-TM with a Database or Network
10.6 Practical Consequences: Online and Offline Computation
10.7 Chapter Summary
Bibliographic Notes
Chapter 11 Degrees of Unsolvability
11.1 Turing Reduction
11.1.1 Turing Reduction of a Computational Problem
11.1.2 Some Basic Properties of the Turing Reduction
11.2 Turing Degrees
11.3 Chapter Summary
Problems
Bibliographic Notes
Chapter 12 The Turing Hierarchy of Unsolvability
12.1 The Perplexities of Unsolvability
12.2 The Turing Jump
12.2.1 Properties of the Turing Jump of a Set
12.3 Hierarchies of T-Degrees
12.3.1 The Jump Hierarchy
12.4 Chapter Summary
Problems
Bibliographic Notes
Chapter 13 The Class D of Degrees of Unsolvability
13.1 The Structure (D)
13.2 Some Basic Properties of
13.2.1 Cardinality of Degrees and of the Class D
13.2.2 The Class D as a Mathematical Structure
13.2.3 Intermediate T-Degrees
13.2.4 Cones
13.2.5 Minimal T-Degrees
13.3 Chapter Summary
Problems
Bibliographic Notes
Chapter 14 C.E. Degrees and the Priority Method
14.1 C.E. Turing Degrees
14.2 Post’s Problem
14.2.1 Post’s Attempt at a Solution to Post’s Problem
14.3 The Priority Method and Priority Arguments
14.3.1 The Priority Method in General
14.3.2 The Friedberg-Muchnik Solution to Post’s Problem
14.3.3 Priority Arguments
14.4 Some Properties of C.E. Degrees
14.5 Chapter Summary
Problems
Bibliographic notes
Chapter 15 The Arithmetical Hierarchy
15.1 Decidability of Relations
15.2 The Arithmetical Hierarchy
15.3 The Link with the Jump Hierarchy
15.4 Practical Consequences: Proving Incomputability
15.5 Chapter Summary
Problems
Bibliographic Notes
Part IV BACK TO THE ROOTS
Chapter 16 Computability (Church-Turing) Thesis Revisited
16.1 Introduction
16.2 The Intuitive Understanding of the Notion of a “Procedure”
16.3 Toward the Thesis
16.3.1 G¨odel
16.3.2 Church
16.3.3 Kleene
16.3.4 Rosser
16.3.5 Post
16.3.6 Turing
16.4 Church-Turing Thesis
16.4.1 Differences Between Church’s and Turing’s Theses
16.4.2 The Church-Turing Thesis
16.4.3 Justifications of the Church-Turing Thesis
16.4.4 Provability of the Church-Turing Thesis
16.5 R´esum´e and Warnings
16.6 New Questions About the Church-Turing Thesis
16.6.1 Original CTT
16.6.2 Algorithmic Versions of CTT
16.6.3 Complexity-Theoretic Versions of CTT
16.6.4 Physical Versions of CTT
16.6.5 Hypercomputing?
Bibliographic Notes
Chapter 17 Further Reading
Appendix A Mathematical Background
Propositional Calculus P
First-Order Logic L
Sets
Relations
Functions
Natural Numbers
Formal Languages
Appendix B Notation Index
Glossary
References
Index