zbMATH — the first resource for mathematics

Randomness, relativization and Turing degrees. (English) Zbl 1090.03013
The paper at hand makes a substantial contribution to our understanding of the relationship between the Turing degree of a real and its relative randomness. Let \(K\) denote prefix-free Kolmogorov complexity and let \(C\) denote plain complexity. By old work of Kolmogorov, Martin-Löf, Levin and Chaitin, we know that the highest plain complexity a string \(\sigma\) can have is \(C(\sigma)=^+ | \sigma| \) where the \(=^+\) denotes equality up to some absolute additive constant. The highest prefix-free complexity is \(K(\sigma)=^+ | \sigma| +K(| \sigma| ).\) On the other hand, no real \(\alpha\) can have \(C(\alpha\upharpoonright n)=^+ n\) for all \(n\), and the best that is possible is that for a real \(C(\alpha\upharpoonright n)=^+ n\) for infinitely many \(n\) (such reals are called Kolmogorov random), this being implied by \(K(\alpha\upharpoonright n)\) being maximal for infinitely many \(n\) (this being called strongly Chaitin random). The authors use an ingenious method based around the low basis theorem to show that Kolmogorov random reals coincide with the 2-random reals; where a real is called 2-random iff it avoids all \(\Sigma_2^0\) classes of measure effectively converging to 0. One direction had been independently proven by J. S. Miller [J. Symb. Log. 69, 907–913 (2004; Zbl 1090.03012), reviewed above]. The authors then investigate reals that are low for Chaitin’s halting probability \(\Omega\). This means that \(\Omega\) is 1-\(A\)-random. The nicest result is to show that if \(A\) is a c.e. low for \(\omega\) set then \(A\) is \(K\)-trivial. This uses a “KC”-set construction which is surprisingly easy. Finally, in the last section, the authors investigate the relationship between jump classes and restricted kinds of randomness. They show that outside the high degrees, Schnorr randomness and Martin-Löf randomness coincide, and within each high degree Schnorr, computable and Martin-Löf randomness may be separated. This argument is rather delicate.

03D80 Applications of computability and recursion theory
03D28 Other Turing degree structures
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI
[1] Every 2-random real is Kolmogorov random 69 pp 907– (2004)
[2] Classical recursion theory, vol. 1 2 (1989)
[3] Probabilities over rich languages 47 pp 495– (1982)
[4] Proceedings of the 7th and 8th Asian Logic Conferences pp 103– (1999)
[5] Commentationes Mathematicae Universitatis Carolinae 28 pp 85– (1987)
[6] Computational complexity pp 113– (1971)
[7] The axiomatization of randomness 55 pp 1143– (1990)
[8] DOI: 10.1145/321892.321894 · Zbl 0309.68045 · doi:10.1145/321892.321894
[9] Computational randomness and lowness 66 pp 1199– (2001) · Zbl 0990.03033
[10] Mathematical foundations of computer science 2420 pp 568– (2002)
[11] DOI: 10.1007/BF00534110 · Zbl 0212.23103 · doi:10.1007/BF00534110
[12] DOI: 10.1016/S0019-9958(66)80018-9 · Zbl 0244.62008 · doi:10.1016/S0019-9958(66)80018-9
[13] Proceedings of the 1st ACM Symposium on Theory of Computing pp 61– (1969)
[14] Computability theory: Current trends and open problems 257 pp 1– (2000)
[15] An introduction to Kolmogorov complexity and its applications (1997) · Zbl 0866.68051
[16] Lowness for the class of random sets 64 pp 1396– (1999) · Zbl 0954.68080
[17] DOI: 10.1137/S0097539799357441 · Zbl 0992.68079 · doi:10.1137/S0097539799357441
[18] DOI: 10.1016/0168-0072(93)90209-V · Zbl 0788.68068 · doi:10.1016/0168-0072(93)90209-V
[19] DOI: 10.1007/BFb0076224 · doi:10.1007/BFb0076224
[20] Martin-Löf random and PA-complete sets (2002)
[21] Draft of a paper (or series of papers) on Chaitin’s work (1975)
[22] Recursively enumerable sets and degrees (1987)
[23] DOI: 10.1090/pspum/005/0141595 · doi:10.1090/pspum/005/0141595
[24] Zufälligkeit und Wahrscheinlichkeit 218 (1971)
[25] DOI: 10.1007/BF01694181 · Zbl 0227.62005 · doi:10.1007/BF01694181
[26] Recursively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion 54 pp 1288– (1989) · Zbl 0708.03020
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.