# 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.

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