On the strongly bounded Turing degrees of the computably enumerable sets
K Ambos-Spies - Computability and Complexity: Essays Dedicated to …, 2016 - Springer
K Ambos-Spies
Computability and Complexity: Essays Dedicated to Rodney G. Downey on the …, 2016•SpringerWe introduce and discuss some techniques designed for the study of the strongly bounded
Turing degrees of the computably enumerable sets, ie, of the computable Lipschitz degrees
and of the identity bounded Turing degrees of ce sets. In particular we introduce some tools
which allow the transfer of certain facts on the weak truth-table degrees to these degree
structures. Using this approach we show that the first order theories of the partial orderings
(R _ cl, ≤) and (R _ ibT, ≤) of the ce cl-and ibT-degrees are not ℵ _0-categorical and …
Turing degrees of the computably enumerable sets, ie, of the computable Lipschitz degrees
and of the identity bounded Turing degrees of ce sets. In particular we introduce some tools
which allow the transfer of certain facts on the weak truth-table degrees to these degree
structures. Using this approach we show that the first order theories of the partial orderings
(R _ cl, ≤) and (R _ ibT, ≤) of the ce cl-and ibT-degrees are not ℵ _0-categorical and …
Abstract
We introduce and discuss some techniques designed for the study of the strongly bounded Turing degrees of the computably enumerable sets, i.e., of the computable Lipschitz degrees and of the identity bounded Turing degrees of c.e. sets. In particular we introduce some tools which allow the transfer of certain facts on the weak truth-table degrees to these degree structures. Using this approach we show that the first order theories of the partial orderings and of the c.e. - and -degrees are not -categorical and undecidable. Moreover, various other results on the structure of the partial orderings and are obtained along these lines.
Springer
顯示最佳搜尋結果。 查看所有結果