Computably Enumerable Sets in the Solovay and the Strong Weak Truth Table Degrees
Computably Enumerable Sets in the Solovay and the Strong Weak Truth Table Degrees
复制标题
DOI：
10.1007/11494645_2
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
George Barmpalias
中科院分区：
文献类型：
--
作者：
George Barmpalias
强弱真值表归约是由唐尼、赫希费尔特和拉福特提出的，作为相对随机性的度量，可以替代索洛维归约。它也自然地出现在经典可计算性理论的证明中，以及Soare、Nabutovsky和Weinberger最近关于可计算性在微分几何中的应用的工作中。Yu和Ding的相关度结构仅限于c.e. reals没有最大元素，要求最大元素。我们用c.e.的例子来回答这个问题。集.使用一个双重非一致的参数，我们表明，有没有最大元素的c.e.的sw度。集.我们注意到，这同样适用于c. e.的Solovay度。集.
The strong weak truth table reducibility was suggested by Downey, Hirschfeldt, and LaForte as a measure of relative randomness, alternative to the Solovay reducibility. It also occurs naturally in proofs in classical computability theory as well as in the recent work of Soare, Nabutovsky and Weinberger on applications of computability to differential geometry. Yu and Ding showed that the relevant degree structure restricted to the c.e. reals has no greatest element, and asked for maximal elements. We answer this question for the case of c.e. sets. Using a doubly non-uniform argument we show that there are no maximal elements in the sw degrees of the c.e. sets. We note that the same holds for the Solovay degrees of c.e. sets.