Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees
Maximal Pairs of Computably Enumerable Sets in the Computably Lipschitz Degrees
复制标题
DOI：
10.1007/s00224-012-9424-1
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
K. Ambos-Spies;Decheng Ding;Yun Fan;W. Merkle
中科院分区：
文献类型：
--
作者：
K. Ambos-Spies;Decheng Ding;Yun Fan;W. Merkle
一个集合A是可计算的Lipschitz或cl-可约的，简而言之，到一个集合BifA是图灵可约的到B，通过一个具有使用函数的oracle图灵机，使得BifA由直到一个加性常数的单位函数限定，即，时间复杂度O（n）本文研究了可计算可列（c.e.） C1-度或最大对，简称，即，对c.e. c1-度，使得没有c.e.在这一对中的两个cl-度之上的cl-度。我们的主要结果如下。(1)一个c.e.图灵度包含c.e. cl-度是最大对的一半当且仅当这个图灵度包含一个最大对当且仅当这个图灵度是数组不可计算的。(2)所有弱真值表完备集的cl-度都是极大对的一半，而存在图灵完备集A，使得A的cl-度不是任何极大对的一半。事实上，任何高C. E。图灵度包含c.e.不是最大对的一半的cl度。(3)高于任何CE有一个极大对。(4)有一个极大对同时也是一个极小对。(5)有一对C. E。c1-度不是最大的，也不具有最小上界.此外，我们对c.e.总的来说，C1级。例如，我们给出了一个非常简单的证明，证明了不存在最大的c. e。cl度。
A setAis computably Lipschitz or cl-reducible, for short, to a setBifAis Turing reducible toBby an oracle Turing machine with use functionϕsuch thatϕis bounded by the identity function up to an additive constant, i.e.,ϕ(n)≤n+O(1). In this paper we study maximal pairs of computably enumerable (c.e.) cl-degrees or maximal pairs, for short, i.e., pairs of c.e. cl-degrees such that there is no c.e. cl-degree that is above both cl-degrees in this pair. Our main results are as follows. (1) A c.e. Turing degree contains a c.e. cl-degree that is half of a maximal pair if and only if this Turing degree contains a maximal pair if and only if this Turing degree is array noncomputable. (2) The cl-degrees of all weak truth-table complete sets are halves of maximal pairs while there is a Turing complete setAsuch that the cl-degree ofAis not half of any maximal pair. In fact, any high c.e. Turing degree contains a c.e. cl-degree that is not half of a maximal pair. (3) Above any c.e. cl-degree there is a maximal pair. (4) There is a maximal pair which at the same time is a minimal pair. (5) There is a pair of c.e. cl-degrees that is not maximal and does not possess a least upper bound.Moreover, we make some observations on the structure of the c.e. cl-degrees in general. For instance, we give a very simple proof of the fact that there are no maximal c.e. cl-degrees.