Format:
Online-Ressource
ISBN:
9783642110726
Series Statement:
C.I.M.E. Summer Schools 79
Content:
S. Homer: Admissible recursion theory.- B.E. Jacobs: Computational complexity and recursion theory.- D. Normann: A survey of set recursion.- G.E. Sacks: Priority arguments in Higgler recursion.- R.I. Soare: Construction in the recursively enumerable degrees.- W. Maass: Recursively invariant recursion theory
Note:
Description based upon print version of record
,
Recursion Theory and Computational Complexity; Copyright Page; Contents; Admissible Recursion Theory; Introduction; 1. Post's Problem for a-Recursion Theory; 2. The Construction and Proof; 3. The Splitting Theorem; 4. Applications; Bibliography; Computational Complexity and Recursion Theory; 0. Introduction; 1. Abstract Computational Complexity Measures; 2. Blum-Rabin, Compression and Speedup Theorems; 3. Complexity Classes; 4. Speedable and Nonapeedable Sets; 5. Generalizations; References; A Survey of Set Hecursion; Priority Arguments in Higher Recursion Theory
,
1. Regularity of a-R.E. Degrees2. Existence of Hyperregular Sets; 3. Recursion on Inadmissible ordinals; 4. Week Admissibility and Priority Arguments; 5. Kleene Recursion in 3E; 6. Post's Problem and Regularity for 3F; References; Constructions in the Recursively Enumerable Degrees; Introduction; Lecture 1. Simple sets, fixed pointd, and a completeness criterion for r. e. sets; Lecture 2. The finite injury priority method; Lecture 3. The infinite injury priority method; Lecture 4. The minimal pair method; Lecture 5. Embedding distributive lattices in the r.e. degrees
,
Lecture 6. The non-diamond theoremLecture 7. The Renaissance in classical Recursion theory, the Sacks density theorem, and beyond; References; Recursively Invariant beta-Recursion Theory (Preliminary Survey); Literature;
Language:
English
Keywords:
Electronic books
