×

Strengthening prompt simplicity. (English) Zbl 1247.03074

Summary: We introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a \(\leq _{\mathrm {wtt}}\) version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very close to the definition of superlow cuppability.
Further, we study the strongly prompt c.e. sets in the context of other notions related promptness, superlowness, and cupping. In particular, we show that every benign cost function has a strongly prompt set which obeys it, providing an analogue to the known result that every cost function with the limit condition has a prompt set which obeys it. We also study the effect that lowness properties have on the behaviour of a set under the join operator. In particular we construct an array noncomputable c.e. set whose join with every low c.e. set is low.

MSC:

03D25 Recursively (computably) enumerable sets and degrees
Full Text: DOI

References:

[1] An almost deep degree 66 pp 881– (2001)
[2] DOI: 10.1016/j.aim.2007.09.008 · Zbl 1134.03026 · doi:10.1016/j.aim.2007.09.008
[3] Lowness properties of r.e. sets (1982)
[4] DOI: 10.1090/S0002-9947-1984-0719661-8 · doi:10.1090/S0002-9947-1984-0719661-8
[5] Computability and randomness (2009) · Zbl 1169.03034
[6] Promptness does not imply superlow cuppability 74 pp 1264– (2009) · Zbl 1197.03044
[7] DOI: 10.1090/S0002-9947-1983-0704618-2 · doi:10.1090/S0002-9947-1983-0704618-2
[8] Proceedings of the twelfth Workshop on Logic, Language, Information and Computation (WoLLIC 2005) 143 pp 45– (2006)
[9] Computability, enumerability, unsolvability: Directions in recursion theory 224 pp 93– (1996)
[10] Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences pp 103– (2003)
[11] DOI: 10.1142/S0219061307000640 · Zbl 1149.03032 · doi:10.1142/S0219061307000640
[12] DOI: 10.1016/j.aim.2004.10.006 · Zbl 1141.03017 · doi:10.1016/j.aim.2004.10.006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.