The theories of the t , tt and wtt r . E . Degrees : undecidability and beyond
Richard A. Shore · 1993
We discuss the structure of the recursively enumerable sets under three reducibilities: Turing, truth-table and weak truth-table. Weak truth-table reducibility requires that the questions asked of the oracle be effectively bounded. Truth-table reducibility also demands such a bound on the the length of the computations. We survey what is known about the algebraic structure and the complexity of the decision procedure for each of the associated degree structures. Each of these structures is an upper semilattice with least and greatest element. Typical algebraic questions include the existence of infima, distributivity, embeddings of partial orderings or lattices and extension of embedding problems such as density. We explain how the algebraic information is used to decide fragments of the theories and then to prove their undecidability (and more). Finally, we discuss some results and open problems concerning automorphisms, definability and the complexity of the decision problems for these degree structures.