Recursion Theory Week: Proceedings of a Conference Held in Oberwolfach, Frg, March 19-25, 1989 (Lecture Notes in Mathematics)

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. 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 K. Ambos-spies, G.h. Müller, And G.e. Sacks (eds.). Includes Bibliographical References.