Computability

Inhaltsverzeichnis

• Prerequisites and Notation.
• 1: Basic Concepts of Computability.
• 1.1 Flowcharts and Machines.
• 1.2 Register Machines and Register Computability.
• 1.3 Primitive Recursive and ?-Recursive Functions.
• 1.4 WHILE-Programs and WHILE-Computability.
• 1.5 Tape Machines.
• 1.6 Stack Machines.
• 1.7 Comparison of Number and Word Functions, Church’s Thesis.
• 1.8 Recursive and Recursively Enumerable Sets.
• 1.9 The Standard Numbering ? of P(1).
• 1.10 Some Unsolvable Problems.
• 2: Type 1 Recursion Theory.
• 2.1 The Basic Concepts of Computability Theory.
• 2.2 Numberings.
• 2.3 Recursive and Recursively Enumerable Sets (Continued).
• 2.4 Many-one and One-one Reducibility.
• 2.5 The Recursion Theorem.
• 2.6 Creative, Productive, Complete Sets.
• 2.7 Effective Numberings.
• 2.8 Ordinal Trees and Computable Ordinals.
• 2.9 Some Applications to Logic.
• 2.10 Oracle Machines and Relativized Recursion Theory.
• 2.11 Turing Reducibility and the Kleene Hierarchy.
• 2.12 Computational Complexity.
• 3: Type 2 Theory of Constructivity and Computability.
• 3.1 Type 2 Computability Models.
• 3.2 Recursion Theory on Baire’s Space.
• 3.3 Representations.
• 3.4 Effective Representations.
• 3.5 Complete Partial Orders.
• 3.6 Type 1 Computability and Type 2 Computability.
• 3.7 Solving Domain Equations.
• 3.8 Applications to Analysis.
• Index of Notations.