Hostname: page-component-745bb68f8f-kw2vx Total loading time: 0 Render date: 2025-02-03T00:26:54.245Z Has data issue: false hasContentIssue false
  • English
  • Français

Randomness and Computability: Open Questions

Published online by Cambridge University Press:  15 January 2014

Joseph S. Miller  and
André Nies
Joseph S. Miller
Affiliation:
Department of Mathematics, University of Connecticut, U-3009, 196 Auditorium Road, Storrs, CT 06269-3009, USAE-mail: [email protected]
André Nies
Affiliation:
Department of Computer Science, Auckland University, Auckland, New ZealandE-mail: [email protected].
Get access Rights & Permissions [Opens in a new window]

Extract

It is time for a new paper about open questions in the currently very active area of randomness and computability. Ambos-Spies and Kučera presented such a paper in 1999 [1]. All the question in it have been solved, except for one: is KL-randomness different from Martin-Löf randomness? This question is discussed in Section 6.

Not all the questions are necessarily hard—some simply have not been tried seriously. When we think a question is a major one, and therefore likely to be hard, we indicate this by the symbol ▶, the criterion being that it is of considerable interest and has been tried by a number of researchers. Some questions are close contenders here; these are marked by ▷. With few exceptions, the questions are precise. They mostly have a yes/no answer. However, there are often more general questions of an intuitive or even philosophical nature behind. We give an outline, indicating the more general questions.

All sets will be sets of natural numbers, unless otherwise stated. These sets are identified with infinite strings over {0, 1}. Other terms used in the literature are sequence and real.

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 12 , Issue 3 , September 2006 , pp. 390 - 410
Copyright
Copyright © Association for Symbolic Logic 2006

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, K. and Kučera, A., Randomness in computability theory, Computability Theory and its Applications (Boulder, CO, 1999) (Cholak, P. A., Lempp, S., Lerman, M., and Shore, R. A., editors), Contemporary Mathematics, vol. 257, American Mathematical Society, 2000, pp. 1–14.CrossRefGoogle Scholar
[2] Becher, V., Figueira, S., Grigorieff, S., and Miller, J. S., Randomness and halting probabilities, to appear.Google Scholar
[3] Calude, C. S. and Nies, A., Chaitin Ω numbers and strong reducibilities, Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science (Auckland, 1997), vol. 3, 1997, pp. 1162–1166, (electronic).Google Scholar
[4] Cholak, P., Groszek, M., and Slaman, T., An almost deep degree, The Journal of Symbolic Logic, vol. 66 (2001), no. 2, pp. 881–901.CrossRefGoogle Scholar
[5] Csima, B. F. and Montalbán, A., A minimal pair of K-degrees, Proceedings of the American Mathematical Society, vol. 134 (2006), pp. 1499–1502.Google Scholar
[6] Demuth, O., Remarks on the structure of tt-degrees based on constructive measure theory, Commentationes Mathematicae Universitatis Carolinae, vol. 29 (1988), pp. 233–247.Google Scholar
[7] Downeyand, R. Hirschfeldt, D.R., Algorithmic randomness and complexity, Springer-Verlag, to appear.Google Scholar
[8] Downey, R., Hirschfeldt, D. R., and LaForte, G., Randomness and reducibility, Journal of Computer and System Sciences, vol. 68 (2004), no. 1, pp. 96–114.Google Scholar
[9] Downey, R., Hirschfeldt, D. R., Miller, J. S., and Nies, A., Relativizing Chaitin's halting probability, Journal of Mathematical Logic, vol. 5 (2005), pp. 167–192.CrossRefGoogle Scholar
[10] Downey, R., Hirschfeldt, D. R., Nies, A., and Stephan, F., Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore University Press, 2003, pp. 103–131.Google Scholar
[11] Downey, R., Hirschfeldt, D. R., Nies, A., and Terwijn, S., Calibrating randomness, this Bulletin, vol. 12 (2006), no. 3, pp. 411–491.Google Scholar
[12] Downey, R., Nies, A., Weber, R., and Yu, L., Lowness properties and null sets, The Journal of Symbolic Logic, vol. 71, no. 3, pp. 1044–1052.Google Scholar
[13] Figueira, S., Nies, A., and Stephan, F., Lowness properties and approximations of the jump, Annals of Pure and Applied Logic, to appear.Google Scholar
[14] Figueira, S., Stephan, F., and Wu, G., Randomness and universal machines, to appear.Google Scholar
[15] Gács, P., Every sequence is reducible to a random one, Information and Control, vol. 70 (1986), pp. 186–192.CrossRefGoogle Scholar
[16] Hirschfeldt, D.R., Nies, A., and Stephan, F., Using random sets as oracles, to appear.Google Scholar
[17] Hjorth, G. and Nies, A., Randomness in effective descriptive set theory, to appear.Google Scholar
[18] Kautz, S., Degrees of random sets, Ph.D. Dissertation, Cornell University, 1991.Google Scholar
[19] Kjos-Hanssen, B., Merkle, W., and Stephan, F., Kolmogorov complexity and the recursion theorem, to appear.Google Scholar
[20] Kjos-Hanssen, B., Nies, A., and Stephan, F., Lowness for the class of Schnorr random reals, SIAM Journal on Computing, vol. 35 (2006), no. 3, pp. 647–657.Google Scholar
[21] Kučera, A., Measure, -classes and complete extensions of PA, Recursion Theory Week (Oberwolfach, 1984) (Ambos-Spies, K., Müller, G. H., and Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1141, Springer, 1985, pp. 245–259.CrossRefGoogle Scholar
[22] Kučera, A., An alternative, priority-free, solution to Post's problem, Mathematical Foundations of Computer Science, 1986 (Bratislava, 1986), Lecture Notes in Computer Science, vol. 233, Springer, 1986, pp. 493–500.Google Scholar
[23] Kučera, A., On the role of 0′ in recursion theory, Logic Colloquium '86 (Hull, 1986), Studies in Logic and the Foundations of Mathematics, vol. 124, North-Holland, 1988, pp. 133–141.Google Scholar
[24] Kučera, A., On relative randomness, Annals of Pure and Applied Logic, vol. 63 (1993), pp. 61–67.CrossRefGoogle Scholar
[25] Kurtz, S., Randomness and genericity in the degrees of unsolvability, Ph.D. Dissertation, University of Illinois, Urbana, 1981.Google Scholar
[26] Lerman, M., Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, 1983.CrossRefGoogle Scholar
[27] Lutz, J. H., Gales and the constructive dimension of individual sequences, Automata, Languages and Programming (Geneva, 2000), Lecture Notes in Computer Science, vol. 1853, Springer, 2000, pp. 902–913.CrossRefGoogle Scholar
[28] Martin-Löf, P., On the notion of randomness, Intuitionism and Proof Theory, North-Holland, 1970, pp. 73–78.Google Scholar
[29] Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, Information Processing Letters, vol. 84 (2002), no. 1, pp. 1–3.Google Scholar
[30] Merkle, W., The complexity of stochastic sequences, Conference on Computational Complexity 2003 (Aarhus, Denmark), vol. 64, 2003, pp. 230–235.Google Scholar
[31] Merkle, W., Miller, J.S., Nies, A., Reimann, J., and Stephan, F., Kolmogorov-Loveland randomness and stochasticity, Annals of Pure and Applied Logic, vol. 138 (2006), no. 1–3, pp. 183–210.Google Scholar
[32] Miller, J. S., Every 2-random real is Kolmogorov random, The Journal of Symbolic Logic, vol. 69 (2004), pp. 907–913.CrossRefGoogle Scholar
[33] Miller, J. S., The K-degrees, low for K degrees, and weakly low for K oracles, in preparation.Google Scholar
[34] Miller, J. S. and Yu, L., On initial segment complexity and degrees of randomness, Transactions of the American Mathematical Society, to appear.Google Scholar
[35] Miller, J. S., Oscillation in the initial segment complexity of random reals, in preparation.Google Scholar
[36] Muchnik, A. A., Semenov, A. L., and Uspensky, V. A., Mathematical metaphysics of randomness, Theoretical Computer Science, vol. 207 (1998), no. 2, pp. 263–317.Google Scholar
[37] Nies, A., Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), pp. 274–305.CrossRefGoogle Scholar
[38] Nies, A., Reals which compute little, Logic Colloquium '02 (Chatzidakis, Z., Koepke, P., and Pohlers, W., editors), Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, 2006, pp. 261–275.Google Scholar
[39] Nies, A., Computability and randomness, Oxford Logic Guides, Oxford University Press, to appear.Google Scholar
[40] Nies, A., Eliminating concepts, Proceedings of the IMS workshop on computational prospects of infinity, to appear.Google Scholar
[41] Nies, A., Non-cupping and randomness, Proceedings of the American Mathematical Society, to appear, available at http://cs.auckland.ac.nz/nies/papers.Google Scholar
[42] Nies, A., Low for random sets: the story, preprint; available at http://www.cs.auckland.ac.nz/nies/papers/.Google Scholar
[43] Nies, A. and Reimann, J., A lower cone in the wtt degrees of non-integral effective dimension, Proceedings of the IMS workshop on computational prospects of infinity, to appear.Google Scholar
[44] Nies, A., Stephan, F., and Terwijn, S. A., Randomness, relativization and Turing degrees, The Journal of Symbolic Logic, vol. 70 (2005), no. 2, pp. 515–535.Google Scholar
[45] Reimann, J., Computability and fractal dimension, Doctoral dissertation, Universität Heidelberg, 2004, Available at http://math.uni-heidelberg.de/logic/reimann/publications/phdthesis.pdf.Google Scholar
[46] Ryabko, B. Y., Coding of combinatorial sources and Hausdorff dimension, Doklady Akademii Nauk SSSR, vol. 277 (1984), no. 5, pp. 1066–1070.Google Scholar
[47] Sacks, G., Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, 1990.CrossRefGoogle Scholar
[48] Shore, R. A., The theory of the degrees below 0′, Journal of the London Mathematical Society (2), vol. 24, pp. 1981–1.Google Scholar
[49] Solovay, R., Handwritten manuscript related to Chaitin's work, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages, 1975.Google Scholar
[50] Staiger, L., Constructive dimension equals Kolmogorov complexity, Information Processing Letters, vol. 93 (2005), no. 3, pp. 149–153.CrossRefGoogle Scholar
[51] Stephan, F., Martin-Löf random sets and PA-complete sets, Logic Colloquium '02 (Chatzidakis, Z., Koepke, P., and Pohlers, W., editors), Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, 2006, pp. 342–348.Google Scholar
[52] Stephan, F. and Yu, L., Lowness for weakly 1-generic and Kurtz random, to appear.Google Scholar
[53] Terwijn, S. A. and Zambella, D., Algorithmic randomness and lowness, The Journal of Symbolic Logic, vol. 66 (2001), no. 3, pp. 1199–1205.Google Scholar
[54] van Lambalgen, M., The axiomatization of randomness, The Journal of Symbolic Logic, vol. 55 (1990), no. 3, pp. 1143–1167.Google Scholar
[55] Yu, L., Lowness for genericity, Archive for Mathematical Logic, to appear.Google Scholar