1987 | OriginalPaper | Buchkapitel
Turing Reducibility and the Kleene Hierarchy
verfasst von : Prof. Dr. Klaus Weihrauch
Erschienen in: Computability
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This chapter will be concerned with a very general kind of reducibility called Turing reducibility, and a classification of the arithmetical sets by the Kleene hierarchy or arithmetical hierarchy. Finally truth-table reducibility which is weaker than many-one reducibility but stronger than Turing reducibility is introduced. As a main tool we shall apply the relativized recursion theory introduced in Chapter 2.10. We prove some very basic facts and a deeper theorem by Friedberg and Muchnik which says that there are two recursively enumerable sets which are incomparable w.r.t. Turing reducibility. Among the possibly nonrecursive sets the arithmetical sets are of particular interest. They can be classified w.r.t. the degree of noncomputability by the Kleene hierarchy. Truth-table reducibility is defined as a special case of Turing reducibility. An extensive study and comparison of all the reducibilities is beyond the scope of this book.