Maximal pairs of computably enumerable sets in the computably Lipschitz degrees (Q1946505)

From MaRDI portal
Revision as of 16:03, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
scientific article

    Statements

    Maximal pairs of computably enumerable sets in the computably Lipschitz degrees (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    15 April 2013
    0 references
    Call \(A\) cl-reducible to \(B\) (computably Lipschitz reducible to \(B\)) if there are an oracle Turing machine \(M\), a use function for \(M\), and a constant \(k\) such that, for any \(n\), \(M[B]\) can determine whether or not \(n\in A\) by a computation using at most \(n+k\) steps. The relation was introduced in [\textit{R. G. Downey}, \textit{D. R. Hirschfeldt} and \textit{G. Laforte}, J. Comput. Syst. Sci. 68, No. 1, 96--114 (2004; Zbl 1072.03024)] as ``strong weak truth-table reducibility'', intended to be an instrument for measuring randomness of real numbers. It generates the cl-degrees. They are known not to be an upper semilattice [\textit{L. Yu} and \textit{D. Ding}, J. Symb. Log. 69, No. 4, 1163--1170 (2004; Zbl 1070.03028)]. The present paper studies \textit{maximal pairs} of c.e. cl-degrees, pairs with no c.e. cl-degree as common upper bound. Its main theorems: (1) A c.e. cl-degree that contains half of a maximal pair contains a maximal pair; (2) There is a Turing-complete set whose c.e. cl-degree is not half of a maximal pair, and ``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 that is also a minimal pair; (5) There is a pair of c.e. cl-degrees that has an upper bound but no least upper bound. Some open problems are given: (i) Characterize those c.e. Turing degrees (if there are any) in which only sets that are halves of maximal pairs are c.e.; (ii) What c.e. cl-degrees are the greatest lower bound of a maximal pair?
    0 references
    computably Lipschitz degrees
    0 references
    maximal pairs
    0 references
    computably enumerable sets
    0 references

    Identifiers