Recursion Theory Week: Proceedings of a Conference held in Oberwolfach, FRG, March 19–25, 1989

Klaus Ambos-Spies, Steven Homer, Dongping Yang (auth.), Klaus Ambos-Spies, Gert H. Müller, Gerald E. Sacks (eds.)3540527729, 9783540527725, 0387527729

These proceedings contain research and survey papers from many subfields of recursion theory, with emphasis on degree theory, in particular the development of frameworks for current techniques in this field. Other topics covered include computational complexity theory, generalized recursion theory, proof theoretic questions in recursion theory, and recursive mathematics.

---

Table of contents :
Honest polynomial reductions and exptally sets….Pages 1-22
On the structure of degrees below O′….Pages 23-32
Positive solutions to Post’s problem….Pages 33-40
The metamathematics of Fraïssé’s order type conjecture….Pages 41-56
Enumeration reducibility, nondeterministic computations and relative computability of partial functions….Pages 57-110
Notes on the O‴ priority method with special attention to density results….Pages 111-140
Array nonrecursive sets and multiple permitting arguments….Pages 141-173
Superbranching degrees….Pages 175-186
A direct construction of a minimal recursively enumerable truth-table degree….Pages 187-204
Σ 2 -induction and the construction of a high degree….Pages 205-221
Undecidability and initial segments of the wtt-degrees ≤0′….Pages 223-244
Randomness and generalizations of fixed point free functions….Pages 245-254
Recursive enumeration without repetition revisited….Pages 255-275
Priority arguments using iterated trees of strategies….Pages 277-296
On the relationship between the complexity, the degree, and the extension of a computable set….Pages 297-322
Polynomially isolated sets….Pages 323-362
A characterization of effective topological spaces….Pages 363-387