×

Benign cost functions and lowness properties. (English) Zbl 1221.03036

In this paper the following interesting results are proved: 4.5mm
1.
A c.e. set \(A\) is strongly jump-traceable if and only if it obeys all benign cost functions.
2.
For any benign cost function \(c\), there is a c.e. set \(A\) which obeys \(c\) and is not strongly jump-traceable.
3.
Every strongly jump-traceable c.e. set is computable from any LR-hard random set.
4.
If a c.e. set is strongly jump-traceable, then it is computable from any \(\omega\) -c.e. random set.

MSC:

03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] DOI: 10.1002/malq.200710012 · Zbl 1123.03040
[2] DOI: 10.1002/malq.200710013 · Zbl 1123.03041
[3] DOI: 10.1142/9789812705815_0005
[4] Promptness does not imply superlow cuppability 74 pp 1264– (2009) · Zbl 1197.03044
[5] An almost deep degree 66 pp 881– (2001)
[6] DOI: 10.1016/j.aim.2007.09.008 · Zbl 1134.03026
[7] Enumerations of the Kolmogorov function 71 pp 501– (2006)
[8] DOI: 10.1090/S0002-9947-1984-0719661-8
[9] Computability and randomness (2009) · Zbl 1169.03034
[10] Logic Colloquium ’02 27 pp 261– (2006)
[11] DOI: 10.1016/j.aim.2004.10.006 · Zbl 1141.03017
[12] Proceedings of the London Mathematical Society
[13] DOI: 10.1016/j.apal.2007.11.014 · Zbl 1140.03017
[14] DOI: 10.2178/bsl/1154698740 · Zbl 1169.03033
[15] Lowness for the class of random sets 64 pp 1396– (1999) · Zbl 0954.68080
[16] Recursion theory and complexity (Kazan, 1997) 2 pp 81– (1999) · Zbl 0865.00036
[17] DOI: 10.1112/jlms/jdm041 · Zbl 1128.03036
[18] Computational randomness and lowness 66 pp 1199– (2001) · Zbl 0990.03033
[19] DOI: 10.1016/j.apal.2007.11.002 · Zbl 1137.03025
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.