×

zbMATH — the first resource for mathematics

Jump inversions inside effectively closed sets and applications to randomness. (English) Zbl 1248.03065
In the paper under review, the authors study inversions of the jump operator on \(\Pi^0_1\) classes, combined with certain basis theorems.
It is proved that:
1)
For any non-empty \(\Pi^0_1\)-class \(P\) without computable members and set \(C\geq_T \emptyset''\) there is a \(\mathrm{GL}_1\) member \(A\in P\) which forms a minimal pair with \(\emptyset'\) and \(A'\equiv_T C\).
2)
Given \(C\geq_T \emptyset''\) and a \(\Pi^0_1\) class \(P\) of positive measure, there is a path \(A\oplus B\) of \(P\) which forms a minimal pair with \(\emptyset'\) such that \(A'\equiv_T A\oplus \emptyset'\equiv_T C\) and \(B'\equiv_T B\oplus \emptyset'\equiv_T C\).
3)
If \(C\geq_T \emptyset'\) is \(\emptyset'\)-hyperimmune and \(P\) is a special non-empty \(\Pi^0_1\)-class, then there is a \(\mathrm{GL}_1\) member \(A\in P\) which forms a minimal pair with \(\emptyset'\) and \( A'\equiv_T C\).
They also apply these results to study randomness. It is proved that van Lambalgen’s theorem fails for weak 2-randomness and there are weakly 2-random reals that are array non-computable.
Reviewer: Liang Yu (Nanjing)

MSC:
03D32 Algorithmic randomness and dimension
03D28 Other Turing degree structures
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1002/malq.19660120125 · Zbl 0181.30504 · doi:10.1002/malq.19660120125
[2] DOI: 10.1016/S0019-9958(86)80004-3 · Zbl 0628.03024 · doi:10.1016/S0019-9958(86)80004-3
[3] DOI: 10.1007/BFb0016275 · doi:10.1007/BFb0016275
[4] DOI: 10.1007/BFb0076224 · doi:10.1007/BFb0076224
[5] Transactions of the American Mathematical Society 173 pp 33– (1972) · Zbl 0247.00014
[6] DOI: 10.1002/malq.19970430412 · doi:10.1002/malq.19970430412
[7] DOI: 10.1002/malq.19930390153 · Zbl 0799.03048 · doi:10.1002/malq.19930390153
[8] Probabilities over rich languages, testing and randomness 47 pp 495– (1982)
[9] DOI: 10.2178/bsl/1154698740 · Zbl 1169.03033 · doi:10.2178/bsl/1154698740
[10] Lowness and null sets 71 pp 1044– (2006)
[11] DOI: 10.1090/S0002-9939-05-07901-3 · Zbl 1085.03032 · doi:10.1090/S0002-9939-05-07901-3
[12] Computability, enumerability, unsolvability: Directions in recursion theory 224 pp 93– (1996)
[13] DOI: 10.1016/j.apal.2005.06.011 · Zbl 1097.03041 · doi:10.1016/j.apal.2005.06.011
[14] Algorithmic randomness and complexity (2010) · Zbl 1221.68005
[15] Information Processing Letters 108 pp 198– (2008)
[16] Minimal degrees and the jump operator 38 pp 249– (1973) · Zbl 0309.02048
[17] DOI: 10.1016/S0049-237X(99)80018-4 · doi:10.1016/S0049-237X(99)80018-4
[18] DOI: 10.1090/S0002-9939-06-08541-8 · Zbl 1110.03027 · doi:10.1090/S0002-9939-06-08541-8
[19] Handbook of recursive mathematics – Volume 2, Recursive algebra, analysis and combinatorics pp 623– (1998)
[20] Decidability of the ”almost all” theory of degrees 37 pp 501– (1972) · Zbl 0287.02029
[21] Logic colloquium ’02 27 pp 342– (2006)
[22] A criterion for completeness of degrees of unsolvability 22 pp 159– (1957)
[23] Recursively enumerable sets and degrees (1987)
[24] DOI: 10.2307/1970028 · Zbl 0119.25105 · doi:10.2307/1970028
[25] Degrees of unsolvability 55 (1963) · Zbl 0143.25302
[26] The upper semilattice of degrees below 0’ is complemented 46 pp 705– (1981) · Zbl 0517.03015
[27] Randomness, relativizalion and Turing degrees 70 pp 515– (2005)
[28] Computability and randomness (2009) · Zbl 1169.03034
[29] DOI: 10.1007/11750321_72 · doi:10.1007/11750321_72
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.