Intends to lay a common basis for the different branches of recursion theory. Leads from the very basic theory to modern concepts of computability. Consists of three consecutive parts: 1. Basic Concepts of Computability. 2. Traditional Recursion Theory. 3. Unified Type 2 theory of constructivity and computability on Baire's space including a general theory of representations.
Author(s): Klaus Weihrauch
Series: EATCS Monographs on Theoretical Computer Science 9
Publisher: Springer
Year: 1987
Language: English
Pages: 526
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs
Front Matter....Pages I-X
Prerequisites and Notation....Pages 1-3
Front Matter....Pages 4-4
Flowcharts and Machines....Pages 5-23
Register Machines and Register Computability....Pages 24-41
Primitive Recursive and μ-Recursive Functions....Pages 42-52
WHILE-Programs and WHILE-Computability....Pages 53-58
Tape Machines....Pages 59-69
Stack Machines....Pages 70-78
Comparison of Number and Word Functions, Church’s Thesis....Pages 79-92
Recursive and Recursively Enumerable Sets....Pages 93-102
The Standard Numbering φ of P (1) ....Pages 103-122
Some Unsolvable Problems....Pages 123-136
Front Matter....Pages 137-137
The Basic Concepts of Computability Theory....Pages 138-143
Numberings....Pages 144-158
Recursive and Recursively Enumerable Sets (Continued)....Pages 159-176
Many-one and One-one Reducibility....Pages 177-190
The Recursion Theorem....Pages 191-204
Creative, Productive, Complete Sets....Pages 205-215
Effective Numberings....Pages 216-226
Ordinal Trees and Computable Ordinals....Pages 227-247
Some Applications to Logic....Pages 248-264
Front Matter....Pages 137-137
Oracle Machines and Relativized Recursion Theory....Pages 265-278
Turing Reducibility and the Kleene Hierarchy....Pages 279-305
Computational Complexity....Pages 306-319
Front Matter....Pages 320-321
Type 2 Computability Models....Pages 322-344
Recursion Theory on Baire’s Space....Pages 345-366
Representations....Pages 367-383
Effective Representations....Pages 384-403
Complete Partial Orders....Pages 404-432
Type 1 Computability Type 2 Computability....Pages 433-452
Solving Domain Equations....Pages 453-478
Applications to Analysis....Pages 479-499
Back Matter....Pages 500-517
