Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2025-01-05T20:51:52.078Z Has data issue: false hasContentIssue false
  • English
  • Français

Randomness, relativization and Turing degrees

Published online by Cambridge University Press:  12 March 2014

André Nies ,
Frank Stephan  and
Sebastiaan A. Terwijn
André Nies
Affiliation:
Department of Computer Science, University of Auckland, 38 Princes ST, New Zealand, E-mail: [email protected]
Frank Stephan
Affiliation:
Departments of Computer Science and Mathematics, National University of Singapore, 3 Science Drive 2, Singapore 117543, Republic of Singapore, E-mail: [email protected]
Sebastiaan A. Terwijn
Affiliation:
Institute of Discrete Mathematics and Geometry, Technische Universität Wien, Wiedner Hauptstrasse 8–10/E104, A-1040 Vienna, Austria, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅(n − 1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ ∣x∣ − c. The ‘only if’ direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity.

Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those l-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω. sets coincide with the r.e. K-trivial ones.

Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 70 , Issue 2 , June 2005 , pp. 515 - 535
Copyright
Copyright © Association for Symbolic Logic 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Ambos-Spies, Klaus and Kučera, Antonín. Randomness in computability theory, Computability theory: Current trends and open problems (Cholak, P. et al., editors). Contemporary Mathematics, vol. 257, American Mathematical Society, 2000, pp. 1–14.Google Scholar
[2] Chaitin, Gregory J., A theory of program size formally identical to information theory, Journal of the Association for Computing Machinery, vol. 22 (1975), pp. 329–340.Google Scholar
[3] Dailey, Robert P., Complexity and randomness, Computational complexity (Rustin, R., editor), Algorithmics Press, 1971, pp. 113–122.Google Scholar
[4] Demuth, Osvald and Kučera, Antonín. Remarks on l-genericity, semigenericity and related concepts. Commentationes Mathematicae Universitatis Carolinae. vol. 28 (1987), pp. 85–94.Google Scholar
[5] Ding, Decheng, Downey, Rod, and Yu, Liang, The complexity of the random reals, to appear.Google Scholar
[6] Downey, Rod and Griffiths, Evan, personal communication, Wellington, 03 28, 2003.Google Scholar
[7] Downey, Rod G., Hirschfeldt, Denis R., Nies, André, and Stephan, Frank, Trivial reals. Proceedings of the 7th and 8th Asian Logic Conferences (7th Conference: Hsi-Tou, Taiwan 6–10 06 1999, 8th Conference: Chongqing, China 29 August–2 September 2002), World Scientific, 2003, pp. 103–131.Google Scholar
[8] Gaifmann, Haim and Snir, Marc, Probabilities over rich languages, this Journal, vol. 47 (1982), pp. 495–548.Google Scholar
[9] Jockusch, Carl G. Jr., Lerman, Manuel, Soare, Robert I., and Solovay, Robert M., Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion, this Journal, vol. 54 (1989), no. 4, pp. 1288–1323.Google Scholar
[10] Kautz, Steven M., Degrees of random sets, Ph.D. thesis, Cornell University, 08 1991.Google Scholar
[11] Kučera, Antonín, Measure, Π1 0-classes and complete extensions of PA, Recursion theory week (Ebbinghaus, H.-D., Müller, G. H., and Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1141, Springer-Verlag, 1985, pp. 245–259.CrossRefGoogle Scholar
[12] Kučera, Antonín, On relative randomness, Annals of Pure and Applied Logic, vol, 63 (1993), pp. 61–67.Google Scholar
[13] Kučera, Antonín and Slaman, Theodore A., Randomness and recursive enumerability, SIAM Journal on Computing, vol. 31 (2001), pp. 199–211.Google Scholar
[14] Kučera, Antonín and Terwijn, Sebastiaan A., Lowness for the class of random sets, this Journal, vol. 64 (1999), no. 4, pp. 1396–1402.Google Scholar
[15] Li, Ming and Vitányi, Paul, An introduction to Kolmogorov complexity and its applications, first ed., Springer-Verlag, 1993, second edition 1997.Google Scholar
[16] Loveland, Donald W., On minimal program complexity measures, Proceedings of the 1st ACM Symposium on Theory of Computing, 1969, pp. 61–66.Google Scholar
[17] Martin-Löf, Per, The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602–619.Google Scholar
[18] Martin-Löf, Per, Complexity oscillations in infinite binary sequences, Zeitschrift für Wahrscheinlichkeits-theorie und verwandte Gebiete, vol. 19 (1971), pp. 225–230.Google Scholar
[19] Merkle, Wolfgang and Mihailović, Nenad. On the construction of effective random sets, Mathematical foundations of computer science, Lecture Notes in Computer Science, vol. 2420, Springer-Verlag, 2002, pp. 568–580.Google Scholar
[20] Miller, Joseph S., Every 2-random real is Kolmogorov random, this Journal, vol. 69 (2004), no. 3. pp. 907–913.Google Scholar
[21] Nies, André, Lowness properties and randomness, to appear.Google Scholar
[22] Nies, André, Each Low(CR) set is computable, manuscript, 01 2003.Google Scholar
[23] Odifreddi, Piergiorgio G., Classical recursion theory, vol. 1, North-Holland, 1989, vol. 2, Elsevier, 1999.Google Scholar
[24] Schnorr, Claus-Peter, A unified approach to the definition of random sequences, Mathematical Systems Theory, vol. 5 (1971), pp. 246–258.Google Scholar
[25] Schnorr, Claus-Peter, Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, vol. 218, Springer-Verlag, 1971.Google Scholar
[26] Scott, Dana, Algebras of sets binumerable in complete extensions of arithmetic, Proceedings of Symposia in Pure and Applied Mathematics, vol. 5 (1962), pp. 117–121.Google Scholar
[27] Soare, Robert I., Recursively enumerable sets and degrees. Springer-Verlag, Heidelberg, 1987.Google Scholar
[28] Solovay, Robert M., Draft of a paper (or series of papers) on Chaitin's work, manuscript, IBM Thomas J. Watson Research Center, New York, 05 1975.Google Scholar
[29] Stephan, Frank, Martin-Löf random and PA-complete sets, Forschungsberichte Mathematische Logik 58, Universität Heidelberg. 2002.Google Scholar
[30] Terwijn, Sebastiaan A., Computability and measure, Ph.D. thesis. University of Amsterdam/ILLC, 1998.Google Scholar
[31] Terwijn, Sebastiaan A., Complexity and randomness, Report CDMTCS-212, The University of Auckland, 03 2003, http://www.logic.at/people/terwijn/auckland.ps. Google Scholar
[32] Terwijn, Sebastiaan A. and Zambella, Domenico, Computational randomness and lowness, this Journal, vol. 66 (2001), no. 3, pp. 1199–1205.Google Scholar
[33] van Lambalgen, Michiel, The axiomatization of randomness, this Journal, vol. 55 (1990), no. 3, pp. 1143–1167.Google Scholar
[34] Wang, Yongge, Randomness and complexity, Ph.D. thesis, University of Heidelberg, 1996.Google Scholar