Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-24T13:14:09.228Z Has data issue: false hasContentIssue false
  • English
  • Français

Calibrating Randomness

Published online by Cambridge University Press:  15 January 2014

Rod Downey ,
Denis R. Hirschfeldt ,
André Nies  and
Sebastiaan A. Terwijn
Rod Downey
Affiliation:
School of Mathematical and Computing Sciences, Victoria University, PO Box 600, Wellington, New ZealandE-mail: [email protected]
Denis R. Hirschfeldt
Affiliation:
Department of Mathematics, University of Chicago, Chicago, IL 60637, USAE-mail: [email protected]
André Nies
Affiliation:
Department of Computer Science, Auckland University, Auckland, New ZealandE-mail: [email protected]
Sebastiaan A. Terwijn
Affiliation:
Institute of Discrete Mathematics and Geometry, Technical University of Vienna, Wiedner Hauptstrasse 8-10 / E104, A-1040 Vienna, AustriaE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

We report on some recent work centered on attempts to understand when one set is more random than another. We look at various methods of calibration by initial segment complexity, such as those introduced by Solovay [125], Downey, Hirschfeldt, and Nies [39], Downey, Hirschfeldt, and LaForte [36], and Downey [31]; as well as other methods such as lowness notions of Kučera and Terwijn [71], Terwijn and Zambella [133], Nies [101, 100], and Downey, Griffiths, and Reid [34]; higher level randomness notions going back to the work of Kurtz [73], Kautz [61], and Solovay [125]; and other calibrations of randomness based on definitions along the lines of Schnorr [117].

These notions have complex interrelationships, and connections to classical notions from computability theory such as relative computability and enumerability. Computability figures in obvious ways in definitions of effective randomness, but there are also applications of notions related to randomness in computability theory. For instance, an exciting by-product of the program we describe is a more-or-less natural requirement-free solution to Post's Problem, much along the lines of the Dekker deficiency set.

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 12 , Issue 3 , September 2006 , pp. 411 - 491
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] Ambos-Spies, K., Merkle, W., Reimann, J., and Stephan, F., Hausdorff dimension in exponential time, Computational Complexity, 2001, IEEE Computer Society, 2001, pp. 210–217.Google Scholar
[3] Antunes, L. and Fortnow, L., Sophistication revisited, Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30–July 4, 2003 (Baeten, J. C. M., Lenstra, J. K., Parrow, J., and Woeginger, G. J., editors), Lecture Notes in Computer Science, vol. 2719, Springer-Verlag, 2003, pp. 267–277.Google Scholar
[4] Athreya, K. B., Hitchcock, J. M., Lutz, J. H., and Mayordomo, E., Effective strong dimension in algorithmic information and computational complexity, SIAM Journal on Computing, to appear, extended abstract in Proceedings of the Twenty-First Symposiumon Theoretical Aspects of Computer Science (Montpellier, France, March 25–27, 2004) , Springer-Verlag, 2004, pp. 632–643.Google Scholar
[5] Barmpalias, G., Computably enumerable sets in the Solovay and the strong weak truth table degrees, New Computational Paradigms: First Conference on Computability in Europe, CiE 2005, Amsterdam,The Netherlands, June 8–12, 2005 (Cooper, S. B., Löwe, B., and Torenvliet, L., editors), Lecture Notes in Computer Science, vol. 3526, Springer-Verlag, 2005, pp. 8–17.Google Scholar
[6] Barmpalias, G. and Lewis, A. E. M., A c.e. real that cannot be sw-computed by any Ω number, Notre Dame Journal of Formal Logic, to appear.Google Scholar
[7] Barzdins, J. M., Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set, Soviet Mathematics – Doklady, vol. 9 (1968), pp. 1251–1254.Google Scholar
[8] Becher, V. and Chaitin, G., Another example of higher order randomness, Fundamenta Informaticae, vol. 51 (2002), pp. 325–338.Google Scholar
[9] Becher, V., Daicz, S., and Chaitin, G., A highly random number, Combinatorics, Computability and Logic (Constanţa, 2001) (Calude, C. S., Dinneen, M. J., and Sburlan, S., editors), Discrete Mathematics and Theoretical Computer Science, Springer-Verlag, 2001, pp. 55–68.Google Scholar
[10] Becher, V. and Grigorieff, S., Random reals and possibly infinite computations part I: randomness in ∅′, The Journal of Symbolic Logic, vol. 70 (2005), pp. 891–913.Google Scholar
[11] Bedregal, B. R. C. and Nies, A., Lowness properties of reals and hyper-immunity, WoLLIC 2003, Electronic Notes in Theoretical Computer Science, vol. 84, Elsevier, 2003, http://www1.elsevier.com/gej-ng/31/29/23/142/23/show/Products/notes/index.htt#001.Google Scholar
[12] Beigel, R., Buhrman, H., Fejer, P., Fortnow, L., Grabowski, P., Longpré, L., Muchnik, A., Stephan, F., and Torenvliet, L., Enumerations of the Kolmogorov function, Electronic Colloquium on Computational Complexity, TR04-015, 2004, http://eccc.uni-trier.de/eccc-reports/2004/TR04-015/.Google Scholar
[13] Cai, J.-Y. and Hartmanis, J., On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, Journal of Computer and System Sciences, vol. 49 (1994), pp. 605–619.Google Scholar
[14] Calude, C. S., Information and randomness, an algorithmic perspective, Springer-Verlag, 1994, second edition, 2002.Google Scholar
[15] Calude, C. S. and Coles, R. J., Program-size complexity of initial segments and domination reducibility, Jewels are forever (Karhumäki, J., Maurer, H., Păun, G., and Rozenberg, G., editors), Springer-Verlag, 1999, pp. 225–237.Google Scholar
[16] Calude, C. S., Coles, R., Hertling, P. H., and Khoussainov, B., Degree-theoretic aspects of computably enumerable reals, Models and computability (Cooper, S. B. and Truss, J. K., editors), London Mathematical Society Lecture Note Series, vol. 259, Cambridge University Press, 1999, pp. 23–39.Google Scholar
[17] Calude, C. S., Hertling, P.H., Khoussainov, B., and Wang, Y., Recursively enumerable reals and Chaitin Ω numbers, Theoretical Computer Science, vol. 255 (2001), pp. 125–149, extended abstract in STACS 98 , Lecture Notes in Computer Science, 1373, Springer-Verlag, Berlin, 1998, pp. 596–606.Google Scholar
[18] Calude, C. S. and Nies, A., Chaitin Ω numbers and strong reducibilities, Journal of Universal Computer Science, vol. 3 (1998), pp. 1162–1166.Google Scholar
[19] Calude, C. S., Staiger, L., and Terwijn, S. A., On partial randomness, Annals of Pure and Applied Logic, vol. 138 (2006), no. 1–3, pp. 20–30.Google Scholar
[20] Chaitin, G. J., Atheory of program size formally identical to information theory, Journal of the ACM, vol. 22 (1975), pp. 329–340.Google Scholar
[21] Chaitin, G. J., Algorithmic information theory, IBM Journal of Research and Development, vol. 21 (1977), pp. 350–359, 496.Google Scholar
[22] Chaitin, G. J., Algorithmic information theory, Cambridge University Press, 1987.Google Scholar
[23] Chaitin, G. J., Incompleteness theorems for random reals, Advances in Applied Mathematics, vol. 8 (1987), pp. 119–146.Google Scholar
[24] Chernov, A. V., Muchnik, An. A., Romashchenko, A. E., Shen, A., and Vereshchagin, N. K., Upper semi-lattice of binary strings with the relation “x is simple conditional to y”, Theoretical Computer Science, vol. 271 (2002), pp. 69–95.Google Scholar
[25] Cholak, P., Coles, R., Downey, R., and Herrmann, E., Automorphisms of the lattice of classes: perfect thin classes and a.n.c. degrees, Transactions of the American Mathematical Society, vol. 353 (2001), pp. 4899–4924.Google Scholar
[26] Csima, B. F., Applications of computability theory to prime models and differential geometry, Ph.D. Dissertation, The University of Chicago, 2003.Google Scholar
[27] 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
[28] Davie, G., Characterising the Martin-Löf random sequences using computably enumerable sets of measure one, Information Processing Letters, vol. 92 (2004), pp. 157–160.Google Scholar
[29] de Leeuw, K., Moore, E. F., Shannon, C. F., and Shapiro, N., Computability by probabilistic machines, Automata studies, Annals of Mathematics Studies, vol. 34, Princeton University Press, 1956, pp. 183–212.Google Scholar
[30] 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
[31] Downey, R., Some computability-theoretic aspects of reals and randomness, The Notre Dame Lectures (Cholak, P., editor), Lecture Notes in Logic, vol. 18, Association for Symbolic Logic, 2005, pp. 97–148.Google Scholar
[32] Downey, R. and Griffiths, E., Schnorr randomness, The Journal of Symbolic Logic, vol. 69 (2004), pp. 533–554.Google Scholar
[33] Downey, R., Griffiths, E., and LaForte, G., On Schnorr and computable randomness, martingales, and machines, Mathematical Logic Quarterly, vol. 50 (2004), pp. 613–627.Google Scholar
[34] Downey, R., Griffiths, E., and Reid, S., On Kurtz randomness, Theoretical Computer Science, vol. 321 (2004), pp. 249–270.CrossRefGoogle Scholar
[35] Downey, R. and Hirschfeldt, D. R., Algorithmic randomness and complexity, Springer-Verlag, to appear.Google Scholar
[36] Downey, R., Hirschfeldt, D. R., and LaForte, G., Randomness and reducibility, Journal of Computer and System Sciences, vol. 68 (2004), pp. 96–114, extended abstract in Mathematical Foundations of Computer Science 2001 (J. Sgall, A. Pultr, and P. Kolman, editors), Lecture Notes in Computer Science, 2136, Springer-Verlag, 2001, pp. 316–327.Google Scholar
[37] Downey, R., Hirschfeldt, D. R., and LaForte, G., Undecidability of the structure of the Solovay degrees of c.e. reals, to appear.Google Scholar
[38] 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.Google Scholar
[39] Downey, R., Hirschfeldt, D.R., and Nies, A., Randomness, computability, and density, SIAM Journal on Computing, vol. 31 (2002), pp. 1169–1183, extended abstract in STACS 2001 Proceedings (A. Ferreira and H. Reichel, editors), Lecture Notes in Computer Science, vol. 2010, Springer-Verlag, 2001, pp. 195–201.Google Scholar
[40] Downey, R., Hirschfeldt, D. R., Nies, A., and Stephan, F., Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences (Downey, R., Decheng, D., Ping, T. S., Hui, Q.Y., and Yasugi, M., editors), Singapore University Press and World Scientific, 2003, extended abstract in Electronic Notes in Theoretical Computer Science , vol. 66 (2002), no. 1, pp. 103–131.Google Scholar
[41] Downey, R., Jockusch, C., and Stob, M., Array nonrecursive sets and multiple permitting arguments, Recursion Theory Week (Oberwolfach, 1989) (Ambos-Spies, K., Müller, G. H., and Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, 1990, pp. 141–174.Google Scholar
[42] Downey, R., Jockusch, C., and Stob, M., Array nonrecursive degrees and genericity, Computability, enumerability, unsolvability (Cooper, S. B., Slaman, T. A., and Wainer, S. S., editors), London Mathematical Society Lecture Notes Series, vol. 224, Cambridge University Press, 1996, pp. 93–104.Google Scholar
[43] Downey, R. and Miller, J. S., A basis theorem for classes of positive measure and jump inversion for random reals, Proceedings of the American Mathematical Society, vol. 134 (2006), pp. 283–288.CrossRefGoogle Scholar
[44] Downey, R., Miller, J. S., and Reimann, J., Finite randomness, in preparation.Google Scholar
[45] Falconer, K., Fractal Geometry. Mathematical Foundations and Applications, Wiley & Sons, 1990.Google Scholar
[46] Gács, P., On the symmetry of algorithmic information, Soviet Mathematics – Doklady, vol. 15 (1974), pp. 1477–1480.Google Scholar
[47] Gács, P., Every sequence is reducible to a random one, Information and Control, vol. 70 (1986), pp. 186–192.CrossRefGoogle Scholar
[48] Gaifman, H. and Snir, M., Probabilities over rich languages, The Journal of Symbolic Logic, vol. 47 (1982), pp. 495–548.Google Scholar
[49] Hausdorff, F., Dimension und äuβeres Maβ, Mathematische Annalen, vol. 79 (1919), pp. 157–179.Google Scholar
[50] Hirschfeldt, D.R., Nies, A., and Stephan, F., Using random sets as oracles, to appear.Google Scholar
[51] Hitchcock, J. M., Lutz, J. H., and Terwijn, S. A., The arithmetical complexity of dimension and randomness, ACM Transactions on Computational Logic, in press.Google Scholar
[52] Hjorth, G. and Nies, A., Randomness in effective descriptive set theory, to appear.Google Scholar
[53] Ishmukhametov, S., Weak recursive degrees and a problem of Spector, Recursion theory and complexity (Arslanov, M. and Lempp, S., editors), de Gruyter, Berlin, 1999, pp. 81–88.CrossRefGoogle Scholar
[54] Jockusch, C. G. Jr., The degrees of bi-immune sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 15 (1969), pp. 135–140.CrossRefGoogle Scholar
[55] Jockusch, C. G. Jr., Three easy constructions of recursively enumerable sets, Logic Year 1979–80 (Proceedings of Seminars and Conferences in Mathematical Logic, University of Connecticut, Storrs, Conn., 1979/80) (Lerman, M., Schmerl, J. H., and Soare, R. I., editors), Lecture Notes in Mathematics, vol. 859, Springer-Verlag, 1981, pp. 83–91.Google Scholar
[56] Jockusch, C. G., Jr., Lerman, M., Soare, R. I., and Solovay, R., Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion, The Journal of Symbolic Logic, vol. 54 (1989), pp. 1288–1323.Google Scholar
[57] Jockusch, C. G. Jr., and Shore, R. A., Pseudo-jump operators I: the r.e. case, Transactions of the American Mathematical Society, vol. 275 (1983), pp. 599–609.Google Scholar
[58] Jockusch, C. G. Jr., and Soare, R. I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[59] Kamae, T., Subsequences of normal sequences, Israel Journal of Mathematics, vol. 16 (1973), pp. 121–149.Google Scholar
[60] Katseff, H. P., Complexity dips in random infinite binary sequences, Information and Control, vol. 38 (1978), pp. 258–263.Google Scholar
[61] Kautz, S. M., Degrees of random sets, PhD Dissertation, Cornell University, 1991.Google Scholar
[62] Kechris, A. S. and Moschovakis, Y. (editors), Cabal Seminar 76–77, Lecture Notes in Mathematics, vol. 689, Springer-Verlag, 1978.Google Scholar
[63] 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, preliminary results in [11].Google Scholar
[64] Ko, K.-I, On the notion of infinite pseudorandom sequences, Theoretical Computer Science, vol. 48 (1986), pp. 9–33.Google Scholar
[65] Kolmogorov, A. N., Three approaches to the quantitative definition of information, Problems of Information Transmission (Problemy Peredachi Informatsii), vol. 1 (1965), pp. 1–7.Google Scholar
[66] Kraft, L.G., Adevice for quantizing, grouping, and coding amplitude modulated pulses, M.Sc. Thesis, MIT, 1949.Google Scholar
[67] Kučera, A., Measure, -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.Google Scholar
[68] Kučera, A., On the use of diagonally nonrecursive functions, Logic Colloquium '87 (Ebbinghaus, H.-D., editor), Studies in Logic and the Foundations of Mathematics, vol. 129, North-Holland, 1989, pp. 219–239.Google Scholar
[69] Kučera, A., On relative randomness, Annals of Pure and Applied Logic, vol. 63 (1993), pp. 61–67.Google Scholar
[70] Kučera, A. and Slaman, T.A., Randomness and recursive enumerability, SIAM Journal on Computing, vol. 31 (2001), pp. 199–211.Google Scholar
[71] Kučera, A. and Terwijn, S. A., Lowness for the class of random sets, The Journal of Symbolic Logic, vol. 64 (1999), pp. 1396–1402.Google Scholar
[72] Kummer, M., Kolmogorov complexity and instance complexity of recursively enumerable sets, SIAM Journal on Computing, vol. 25 (1996), pp. 1123–1143.Google Scholar
[73] Kurtz, S. A., Randomness and genericity in the degrees of unsolvability, PhD Dissertation, University of Illinois, 1981.Google Scholar
[74] Levin, L. A., Some theorems on the algorithmic approach to probability theory and information theory, Dissertation in Mathematics, Moscow, 1971.Google Scholar
[75] Levin, L. A., On the notion of a random sequence, Soviet Mathematics – Doklady, vol. 14 (1973), pp. 1413–1416.Google Scholar
[76] Levin, L. A., Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Problems of Information Transmission, vol. 10 (1974), pp. 206–210.Google Scholar
[77] Lewis, A. E. M. and Barmpalias, G., Randomness and the Lipschitz degrees of computability, to appear.Google Scholar
[78] Li, M. and Vitányi, P., An introduction to Kolmogorov complexity and its applications, 2nd ed., Springer-Verlag, 1997.Google Scholar
[79] Loveland, D., A variant of the Kolmogorov concept of complexity, Information and Control, vol. 15 (1969), pp. 510–526.Google Scholar
[80] Lutz, J.H., Category and measure in complexity classes, SIAM Journal on Computing, vol. 19 (1990), pp. 1100–1131.Google Scholar
[81] Lutz, J.H., Almost everywhere high nonuniform complexity, Journal of Computer and System Sciences, vol. 44 (1992), pp. 220–258.Google Scholar
[82] Lutz, J.H., Dimension in complexity classes, SIAM Journal on Computing, vol. 32 (2003), pp. 1236–1259, extended abstract in 15th Annual IEEE Conference on Computational Complexity (Florence, 2000) (F. Titsworth, editor), IEEE Computer Society, Los Alamitos, CA, 2000, pp. 158–169).Google Scholar
[83] Lutz, J.H., The dimensions of individual strings and sequences, Information and Computation, vol. 187 (2003), pp. 49–79, preliminary version: Gales and the constructive dimension of individual sequences, in Proceedings of the 27th International Colloquium on Automata, Languages, and Programming , (U. Montanari, J.D.P. Rolim, and E. Welzl, editors), Springer-Verlag, 2000, pp. 902–913.Google Scholar
[84] Lutz, J.H., Effective fractal dimensions, Mathematical Logic Quarterly, vol. 51 (2005), pp. 62–72.Google Scholar
[85] Martin-Löf, P., The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602–619.Google Scholar
[86] Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, Information Processing Letters, vol. 84 (2002), pp. 1–3.Google Scholar
[87] Merkle, W., The complexity of stochastic sequences, Journal of Computer and System Sciences, to appear, preliminary version in Conference on Computational Complexity 2003 , IEEE Computer Society Press, 2003, pp. 230–235.Google Scholar
[88] Merkle, W. and Mihailović, N., On the construction of effective random sets, The Journal of Symbolic Logic, vol. 69 (2004), pp. 862–878, preliminary version in Mathematical Foundations of Computer Science, 2002 (K. Diks and W. Rytter, editors), Lecture Notes in Computer Science, vol. 2420, Springer-Verlag, 2002, pp. 568–580.Google Scholar
[89] Merkle, W., Mihailović, N., and Slaman, T., Some results on effective randomness, Theory of Computing Systems, to appear, preliminary version in International Colloquium on Automata, Languages and Programming 2004 , Lecture Notes in Computer Science, vol. 3142, Springer-Verlag, 2004, pp. 983–995.Google Scholar
[90] 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, preliminary version in STACS 2005, Lecture Notes in Computer Science, vol. 3404, Springer-Verlag, 2005, pp. 422–433.Google Scholar
[91] Miller, J. S., Every 2-random real is Kolmogorov random, The Journal of Symbolic Logic, vol. 69 (2004), pp. 907–913.Google Scholar
[92] Miller, J. S., The K-degrees, low for K degrees, and weakly low for K oracles, in preparation.Google Scholar
[93] Miller, J. S. and Nies, A., Randomness and computability: open questions, this Bulletin, vol. 12 (2006), no. 3, pp. 390–410.Google Scholar
[94] Miller, J. S. and Yu, L., On initial segment complexity and degrees of randomness, Transactions of the American Mathematical Society, to appear.Google Scholar
[95] Miller, J. S. and Yu, L., Oscillation in the initial segment complexity of random reals, to appear.Google Scholar
[96] Miller, W. and Martin, D. A., The degrees of hyperimmune sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 159–166.Google Scholar
[97] Muchnik, A. A., Semenov, A. L., and Uspensky, V. A., Mathematical metaphysics of randomness, Theoretical Computer Science, vol. 207 (1998), pp. 263–317.Google Scholar
[98] Nabutovsky, A. and Weinberger, S., The fractal nature of Riem/Diff I, Geometriae Dedicata, vol. 101 (2003), pp. 1–54.Google Scholar
[99] Nies, A., Effectively dense Boolean algebras and their applications, Transactions of the American Mathematical Society, vol. 352 (2000), pp. 4989–5012.CrossRefGoogle Scholar
[100] Nies, A., Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), pp. 274–305.Google Scholar
[101] 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
[102] Nies, A., Computability and randomness , to appear.Google Scholar
[103] Nies, A., Eliminating concepts, to appear in the proceedings of the Program on Computational Prospects of Infinity, Singapore, 2005, available at http://www.cs.auckland.ac.nz/~nies.Google Scholar
[104] Nies, A., Low for random sets: the story, preprint, available at http://www.cs.auckland.ac.nz/~nies.Google Scholar
[105] Nies, A., Stephan, F., and Terwijn, S. A., Randomness, relativization, and Turing degrees, The Journal of Symbolic Logic, vol. 70 (2005), pp. 515–535.Google Scholar
[106] Odifreddi, P. G., Classical recursion theory, vol. 1, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland, 1989.Google Scholar
[107] Odifreddi, P. G., Classical recursion theory, vol. 2, Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland, 1999.Google Scholar
[108] Oxtoby, J. C., Measure and category, 2nd ed., Springer-Verlag, 1980.Google Scholar
[109] Raisonnier, J., A mathematical proof of S. Shelah's theorem on the measure problem and related results, Israel Journal of Mathematics, vol. 48 (1984), pp. 48–56.Google Scholar
[110] Reid, S., The classes of algorithmically random reals, Masters Thesis, Victoria University of Wellington, 2003.Google Scholar
[111] Reimann, J., Computability and fractal dimension, PhD Dissertation, University of Heidelberg, 2004.Google Scholar
[112] Reimann, J. and Stephan, F., On hierarchies of randomness tests, transparencies for a talk by Stephan at the 9th Asian Logic Conference, available at http://www.math.uni-heidelberg.de/logic/reimann/lectures.html.Google Scholar
[113] Ryabko, B. Y., Coding of combinatorial sources and Hausdorff dimension, Doklady Akademii Nauk SSSR, vol. 277 (1984), pp. 1066–1070.Google Scholar
[114] Ryabko, B. Y., Noise-free coding of combinatorial sources, Hausdorff dimension and Kolmogorov complexity, Problems of Information Transmission (Problemy Peredachi Informatsii), vol. 22 (1986), pp. 16–26.Google Scholar
[115] Sacks, G. E., Degrees of unsolvability, Annals of Mathematics Studies, vol. 55, Princeton University Press, 1963.Google Scholar
[116] Schnorr, C.-P., A unified approach to the definition of a random sequence, Mathematical Systems Theory, vol. 5 (1971), pp. 246–258.Google Scholar
[117] Schnorr, C.-P., Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, vol. 218, Springer-Verlag, 1971.Google Scholar
[118] Schnorr, C.-P., Process complexity and effective random tests, Journal of Computer and System Sciences, vol. 7 (1973), pp. 376–388.Google Scholar
[119] Shannon, C. E., The mathematical theory of communication, Bell System Technical Journal, vol. 27 (1948), pp. 379–423, 623–656.Google Scholar
[120] Silver, J. H., Counting the number of equivalence classes of Borel and coanalytic equivalence relations, Annals of Mathematical Logic, vol. 18 (1980), pp. 1–28.Google Scholar
[121] Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, 1987.Google Scholar
[122] Soare, R. I., Computability theory and differential geometry, this Bulletin, vol. 10 (2004), pp. 457–486.Google Scholar
[123] Solomonoff, R. J., A preliminary report on a general theory of inductive inference, Technical Report ZTB-138, Zator Company, Cambridge, Mass., 11 1960.Google Scholar
[124] Solovay, R., A model of set theory in which every set of reals is Lebesgue measurable, Annals of Mathematics, vol. 92 (1970), pp. 1–56.Google Scholar
[125] Solovay, R., Draft of a paper (or series of papers) on Chaitin's work, unpublished manuscript, 05 1975, IBM Thomas J. Watson Research Center, New York, 215 pp.Google Scholar
[126] Staiger, L., Kolmogorov complexity and Hausdorff dimension, Information and Computation, vol. 103 (1993), pp. 159–194.Google Scholar
[127] Staiger, L., A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory of Computing Systems, vol. 31 (1998), pp. 215–229.Google Scholar
[128] Staiger, L., Constructive dimension equals Kolmogorov complexity, Information Processing Letters, vol. 93 (2005), pp. 149–153, preliminary version: Research Report CDMTCS-210, University of Auckland, January 2003.Google Scholar
[129] Stephan, F., Martin-Löf random and PA-complete sets, Forschungsbericht Mathematische Logik, vol. 58/2002, Universität Heidelberg, 2002.Google Scholar
[130] Tadaki, K., A generalization of Chaitin's halting probability Ω and halting self-similar sets, Hokkaido Mathematical Journal, vol. 31 (2002), pp. 219–253.Google Scholar
[131] Terwijn, S. A., Computability and measure, PhD Dissertation, University of Amsterdam/ILLC, 1998.Google Scholar
[132] Terwijn, S. A., Complexity and randomness, Rendiconti del Seminario Matematico di Torino, vol. 62, 2004, preliminary version: Research Report CDMTCS-212, University of Auckland, March 2003, pp. 1–38.Google Scholar
[133] Terwijn, S.A. and Zambella, D., Computational randomness and lowness, The Journal of Symbolic Logic, vol. 66 (2001), pp. 1199–1205.Google Scholar
[134] van Lambalgen, M., Random sequences, PhD Dissertation, University of Amsterdam, 1987.Google Scholar
[135] van Lambalgen, M., The axiomatization of randomness, The Journal of Symbolic Logic, vol. 55 (1990), pp. 1143–1167.Google Scholar
[136] Ville, J., étude Critique de la Notion de Collectif, Gauthier-Villars, 1939.Google Scholar
[137] von Mises, R., Grundlagen der Wahrscheinlichkeitsrechnung, Mathematische Zeitschrift, vol. 5 (1919), pp. 52–99.Google Scholar
[138] Wang, Y., Randomness and complexity, PhD Dissertation, University of Heidelberg, 1996.Google Scholar
[139] Wang, Y., A separation of two randomness concepts, Information Processing Letters, vol. 69 (1999), pp. 115–118.CrossRefGoogle Scholar
[140] Yu, L., When van Lambalgen's Theorem fails, Proceedings of the American Mathematical Society, to appear.Google Scholar
[141] Yu, L. and Ding, D., There are 2ℵ 0 many H-degrees in the random reals, Proceedings of the American Mathematical Society, vol. 132 (2004), pp. 2461–2464.Google Scholar
[142] Yu, L. and Ding, D., There is no sw-complete c.e. real, The Journal of Symbolic Logic, vol. 69 (2004), pp. 1163–1170.Google Scholar
[143] Yu, L., Ding, D., and Downey, R., The Kolmogorov complexity of random reals, Annals of Pure and Applied Logic, vol. 129 (2004), pp. 163–180.Google Scholar
[144] Zambella, D., On sequences with simple initial segments, ILLC technical reportML-1990-05, University of Amsterdam, 1990.Google Scholar
[145] Zvonkin, A. K. and Levin, L. A., The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Mathematical Surveys, vol. 25 (1970), pp. 83–124.Google Scholar