Tabular degrees in \(\alpha\)-recursion theory (Q1184713): Difference between revisions

This paper develops the foundations of a theory of truth-table reducibilities in the setting of \(\alpha\)-recursion. A generalization of \(tt\)-reducibility and several generalizations of weak-\(tt\)-reducibility are given and their properties explored. Most of the main results deal with regular sets. For example, for each of the reducibilities given, any degree containing a regular set is composed exclusively of regular sets; thus Sacks' regular set theorem does not carry over to these truth-table degrees.