Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
type: Item
instance of: scholarly article
title: Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
zbMATH Open document ID: 1273.03140
author: Yun Fan
author: Wolfgang Merkle
author: Klaus Ambos-Spies
author: Decheng Ding
published in: Theory of Computing Systems
publication date: 2013-04-15T00:00:00Z
review text: 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?
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D80
zbMATH DE Number: 6153893
zbMATH Keywords: computably Lipschitz degrees
zbMATH Keywords: maximal pairs
zbMATH Keywords: computably enumerable sets
reviewed by: Joseph S. Ullian
MaRDI profile type: Publication
full work available at URL: s00224-012-9424-1
OpenAlex ID: W1976148933
cites work: Cupping and noncapping in the r.e. weak truth table and turing degrees
cites work: New Computational Paradigms
cites work: Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees
cites work: The ibT degrees of computably enumerable sets are not dense
cites work: Structures of Some Strong Reducibilities
cites work: The computable Lipschitz degrees of computably enumerable sets are not dense
cites work: Algorithmic Randomness and Complexity
cites work: Q4779154
cites work: Randomness and reducibility
cites work: Q3197814
cites work: The method of the Yu–Ding Theorem and its application
cites work: Q5469464
cites work: Maximal pairs of c.e. reals in the computably Lipschitz degrees
cites work: Q4946099
cites work: Randomness and the linear degrees of computability
cites work: Q3819052
cites work: Computability Theory and Differential Geometry
cites work: There is no SW-complete c.e. real
DOI: 10.1007/S00224-012-9424-1
Recommended article: Maximal pairs of c.e. reals in the computably Lipschitz degrees
Recommended article: Random reals and Lipschitz continuity
Recommended article: Low upper bounds in the LR degrees
Recommended article: Q3406680
Recommended article: Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility
Recommended article: The computable Lipschitz degrees of computably enumerable sets are not dense
Recommended article: Non-low\(_2\)-ness and computable Lipschitz reducibility
Recommended article: Separations by random oracles and “Almost” classes for generalized reducibilities
Recommended article: Q5417040
Recommended article: Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees
description: scientific article; zbMATH DE number 6153893