Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-27T18:24:35.877Z Has data issue: false hasContentIssue false
  • English
  • Français

Algorithmic Randomness and Measures of Complexity

Published online by Cambridge University Press:  05 September 2014

George Barmpalias
George Barmpalias*
Affiliation:
State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, P.O. BOX 8718, China E-mail: [email protected], URL: http://www.barmpalias.net
Get access Rights & Permissions [Opens in a new window]

Abstract

We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 19 , Issue 3 , September 2013 , pp. 318 - 350
Copyright
Copyright © Association for Symbolic Logic 2013

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, Ding, Decheng, Fan, Yun, and Merkle, Wolfgang, Maximal pairs of computably enumerable sets in the computable-Lipschitz degrees, Theory of Computing Systems, vol. 52 (2013), no. 1, pp. 2–27.CrossRefGoogle Scholar
[2] Baartse, Martijn and Barmpalias, George, On the gap between trivial and nontrivial initial segment prefix-free complexity, Theory of Computing Systems, vol. 52 (2013), no. 1, pp. 28–47.CrossRefGoogle Scholar
[3] Barmpalias, George, Computably enumerable sets in the Solovay and the strong weak truth table degrees, Computability in Europe (Cooper, S. Barry, Löwe, Benedikt, and Torenvliet, Leen, editors), Lecture Notes in Computer Science, vol. 3526, Springer, 2005, pp. 8–17.Google Scholar
[4] Barmpalias, George, Elementary differences between the degrees of unsolvability and the degrees of compressibility, Annals of Pure and Applied Logic, vol. 161 (2010), no. 7, pp. 923–934.CrossRefGoogle Scholar
[5] Barmpalias, George, Relative randomness and cardinality, Notre Dame Journal of Formal Logic, vol. 51 (2010), no. 2.Google Scholar
[6] Barmpalias, George, On strings with trivial Kolmogorov complexity, International Journal of Software and Informatics, vol. 5 (2011), no. 4, pp. 609–623.Google Scholar
[7] Barmpalias, George, Compactness arguments with effectively closed sets for the study of relative randomness, Journal of Logic and Computation, vol. 22 (2012), no. 4, pp. 679–691.Google Scholar
[8] Barmpalias, George, Tracing and domination in the Turing degrees, Annals of Pure and Applied Logic, vol. 163 (2012), no. 5, pp. 500–505.Google Scholar
[9] Barmpalias, George, Universal computably enumerable sets and initial segment prefix-free complexity, Information and Computation , in press.Google Scholar
[10] Barmpalias, George and Downey, Rodney G., Exact pairs for the ideal of the K- trivial sequences in the Turing degrees, preprint, 2012.Google Scholar
[11] Barmpalias, George, Downey, Rodney G., and Greenberg, Noam, Working with strong reducibilities above totally ω-c.e. and array computable degrees, Transactions of the American Mathematical Society, vol. 362 (2010), no. 2, pp. 777–813.CrossRefGoogle Scholar
[12] Barmpalias, George, Hölzl, Rupert, Lewis, Andrew E. M., and Merkle, Wolfgang, Analogues of Chaitin's Ω in the computably enumerable sets, Information Processing Letters, vol. 113 (2013), no. 5–6, pp. 171–178.Google Scholar
[13] Barmpalias, George and Lewis, Andrew E.M., Ac.e. real that cannot be sw-computed by any omega number, Notre Dame Journal of Formal Logic, vol. 47 (2006), no. 2, pp. 197–209.Google Scholar
[14] Barmpalias, George and Lewis, Andrew E.M., The ibT degrees of computably enumerable sets are not dense, Annals of Pure and Applied Logic, vol. 141 (2006), no. 1–2, pp. 51–60.Google Scholar
[15] Barmpalias, George and Lewis, Andrew E.M., Random reals and Lipschitz continuity, Mathematical Structures in Computer Science, vol. 16 (2006), no. 5, pp. 737–749.Google Scholar
[16] Barmpalias, George and Lewis, Andrew E.M., Randomness and the linear degrees of computability, Annals of Pure and Applied Logic, vol. 145 (2007), no. 3, pp. 252–257.Google Scholar
[17] Barmpalias, George and Lewis, Andrew E.M., Chaitin's halting probability and the compression of strings using oracles, Proceedings of the Royal Society A , vol. 467 (2011), pp. 2912–2926.Google Scholar
[18] Barmpalias, George, Lewis, Andrew E. M., and Ng, Keng Meng, The importance of Π1 0 classes in effective randomness, The Journal of Symbolic Logic, vol. 75 (2010), no. 1, pp. 387–400.Google Scholar
[19] Barmpalias, George, Lewis, Andrew E. M., and Soskova, Mariya, Randomness, lowness and degrees, The Journal of Symbolic Logic, vol. 73 (2008), no. 2, pp. 559–577.CrossRefGoogle Scholar
[20] Barmpalias, George, Lewis, Andrew E. M., and Stephan, Frank, Π1 0 classes, LR degrees and Turing degrees, Annals of Pure and Applied Logic, vol. 156 (2008), no. 1, pp. 21–38.Google Scholar
[21] Barmpalias, George and Li, Angsheng, Kolmogorov complexity and computably enumerable sets, Annals of Pure and Applied Logic , (in press).Google Scholar
[22] Barmpalias, George, Miller, Joseph S., and Nies, André, Randomness notions and partial relativization, Israel Journal of Mathematics, vol. 191 (2012), no. 2, pp. 791–816.CrossRefGoogle Scholar
[23] Barmpalias, George and Nies, André, Upper bounds on ideals in the computably enumerable Turing degrees, Annals of Pure and Applied Logic, vol. 162 (2011), no. 6, pp. 465–473.Google Scholar
[24] Barmpalias, George and Sterkenburg, Tom F., On the number of infinite sequences with trivial initial segment complexity, Theoretical Computer Science, vol. 412 (2011), no. 52, pp. 7133–7146.CrossRefGoogle Scholar
[25] Barmpalias, George and Vlek, C. S., Kolmogorov complexity of initial segments of sequences and arithmetical definability, Theoretical Computer Science, vol. 412 (2011), no. 41, pp. 5656–5667.Google Scholar
[26] Bienvenu, Laurent and Downey, Rod, Kolmogorov complexity and Solovay functions, Symposium on Theoretical Aspects of Computer Science 2009, Dagstuhl Seminar Proceedings LIPIcs 3, 2009, pp. 147–158.Google Scholar
[27] Bienvenu, Laurent, Merkle, Wolfgang, and Nies, André, Solovay functions and K-triviality, Symposium on Theoretical Aspects of Computer Science 2011, Leibniz International Proceedings in Informatics 9, 2011, pp. 452–463.Google Scholar
[28] Bienvenu, Laurent, Miller, Joseph S., Hölzl, Rupert, and Nies, André, Denjoy, Demuth and density, in preparation, 2012.Google Scholar
[29] Calude, C., Hertling, P., Khoussainov, B., and Wang, Y., Recursively enumerable reals and Chaitin Ω numbers, Theoretical Computer Science, vol. 255 (2001), no. 1–2, pp. 125–149.CrossRefGoogle Scholar
[30] Chaitin, Gregory J., A theory of programsize formally identical to information theory, Journal of the ACM, vol. 22 (1975), pp. 329–340.Google Scholar
[31] Chaitin, Gregory J., Information-theoretical characterizations of recursive infinite strings, Theoretical Computer Science, vol. 2 (1976), pp. 45–48.Google Scholar
[32] Csima, Barbara F. and Montalbán, Antonio, A minimal pair of K-degrees, Proceedings of the American Mathematical Society, vol. 134 (2006), no. 5, pp. 1499–1502, (electronic).CrossRefGoogle Scholar
[33] Day, Adam R., The computable Lipschitz degrees of computably enumerable sets are not dense, Annals of Pure and Applied Logic, vol. 161 (2010), no. 12, pp. 1588–1602.Google Scholar
[34] Day, Adam R. and Miller, Joseph S., private communication, 08 2012.Google Scholar
[35] Diamondstone, David, Low upper bounds in the LR degrees, Annals of Pure and Applied Logic, vol. 163 (2012), no. 3, pp. 314–320.Google Scholar
[36] Ding, Decheng, Downey, Rodney G., and Yu, Liang, The Kolmogorov complexity of random reals, Annals of Pure and Applied Logic, vol. 129 (2004), no. 1–3, pp. 163–180.Google Scholar
[37] Ding, Decheng and Yu, Liang, There is no sw-complete c.e. real, The Journal of Symbolic Logic, vol. 69 (2004), no. 4, pp. 1163–1170.Google Scholar
[38] Downey, Rodney G. and Hirschfeldt, Denis R., Algorithmic randomness and complexity, Springer, 2010.Google Scholar
[39] Downey, Rodney G., Hirschfeldt, Denis R., and LaForte, Geoff, Randomness and reducibility, Journal of Computer and System Sciences, vol. 68 (2004), no. 1, pp. 96–114.Google Scholar
[40] Downey, Rodney G., Hirschfeldt, Denis R., and LaForte, Geoffrey, Randomness and reducibility, Mathematical Foundations of Computer Science 2001 (Sgall, J. et al., editors), Lecture Notes in Computer Science, vol. 2136, Springer, 2001, pp. 316–327.CrossRefGoogle Scholar
[41] Downey, Rodney G., Undecidability of the structure of the Solovay degrees of c.e. reals, Journal of Computer and System Sciences, vol. 73 (2007), no. 5, pp. 769–787.CrossRefGoogle Scholar
[42] Downey, Rodney G., Hirschfeldt, Denis R., and Nies, André, Randomness, computability, and density, SIAM Journal on Computing, vol. 31 (2002), no. 4, pp. 1169–1183.Google Scholar
[43] Downey, Rodney G., Hirschfeldt, Denis R., Nies, André, and Stephan, Frank, Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences (Downey, Rod et al., editors), Singapore University Press, Singapore, 2003, pp. 103–131.Google Scholar
[44] Downey, Rodney G., Nies, Denis R. Hirschfeldt André, and Terwijn, Sebastiaan A., Calibrating randomness, this Bulletin, vol. 12 (2006), no. 3, pp. 411–491.Google Scholar
[45] Fan, Yun and Lu, Hong, Some properties of sw-reducibility, Nanjing University. Journal. Mathematical Biquarterly, vol. 22 (2005), pp. 244–252.Google Scholar
[46] Gács, Péter, Every sequence is reducible to a random one, Information and Control, vol. 70 (1986), no. 2.3, pp. 186–192.Google Scholar
[47] Goncharov, S. S., Downey, R. G., and Ono, H. (editors), Proceedings of the 9th Asian logic conference, World Scientific Publishing Company, Singapore, 2006.Google Scholar
[48] Hirschfeldt, Denis R., Nies, André, and Stephan, Frank, Using random sets as oracles, Journal of the London Mathematical Society. Second Series, vol. 75 (2007), no. 3, pp. 610–622.Google Scholar
[49] Hölzl, Rupert, Kräling, Thorsten, and Merkle, Wolfgang, Time-bounded Kolmogorov complexity and Solovay functions, Mathematical foundations of computer science, 2009, Lecture Notes in Computer Science, vol. 5734, Springer, 2009, pp. 392–402.Google Scholar
[50] Jockusch, Carl G. Jr., and Soare, Robert I., Degrees of members of Π1 0 classes, Pacific Journal of Mathematics, vol. 40 (1972), pp. 605–616.Google Scholar
[51] Kjos-Hanssen, Bjørn, Merkle, Wolfgang, and Stephan, Frank, Kolmogorov complexity and the recursion theorem, Symposium on theoretical aspects of computer science, 2006, pp. 149–161.Google Scholar
[52] Kjos-Hanssen, Bjørn, Kolmogorov complexity and the recursion theorem, Transactions of the American Mathematical Society, vol. 363 (2011).Google Scholar
[53] Kjos-Hanssen, Bjørn, Miller, Joseph S., and Solomon, Reed, Lowness notions, measure and domination, Journal of the London Mathematical Society, (2012), in press.Google Scholar
[54] Kleene, S. C. and Post, E., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics. Second Series , vol. 59 (1954), pp. 379–407.Google Scholar
[55] Kolmogorov, Andrey N., Three approaches to the definition of the concept “quantity of information”, Problemy Peredači Informacii, vol. 1 (1965), no. 1, pp. 3–11.Google Scholar
[56] Kučera, Antonín, Measure, Π1 0-classes and complete extensions of PA, Recursion theory week, Lecture Notes in Mathematics, vol. 1141, Springer, Berlin, 1985, pp. 245–259.Google Scholar
[57] Kučera, Antonín and Slaman, Theodore, Randomness and recursive enumerability, SIAM Journal on Computing, vol. 31 (2001), no. 1, pp. 199–211.Google Scholar
[58] Kučera, Antonín and Slaman, Theodore, Low upper bounds of ideals, The Journal of Symbolic Logic, vol. 74 (2009), no. 2, pp. 517–534.Google Scholar
[59] Kummer, Martin, Kolmogorov complexity and instance complexity of recursively enumerable sets, SIAM Journal on Computing, vol. 25 (1996), no. 6, pp. 1123–1143.CrossRefGoogle Scholar
[60] Lachlan, Alistair H., The priority method I, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 13 (1967), pp. 1–10.Google Scholar
[61] Lathrop, James I. and Lutz, Jack H., Recursive computational depth, Information and Computation, vol. 153 (1999), no. 1, pp. 139–172.Google Scholar
[62] Levin, L. A., The concept of a random sequence, Doklady Akademii Nauk. SSSR, vol. 212 (1973), pp. 548–550.Google Scholar
[63] Li, Ming and Vitányi, Paul, An introduction to Kolmogorov complexity and its applications, second ed., Graduate Texts in Computer Science, Springer, 1997.Google Scholar
[64] Martin-Löf, Per, The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602–619.CrossRefGoogle Scholar
[65] Merkle, Wolfgang and Stephan, Frank, On C-degrees, H-degrees and T-degrees, IEEE Conference on Computational Complexity, 2007, IEEE Computer Society, Los Alamitos, CA, USA, 2007, pp. 60–69.Google Scholar
[66] Miller, Joseph S., Every 2-randomreal is Kolmogorov random, The Journal of Symbolic Logic, vol. 69 (2004), pp. 907–913.Google Scholar
[67] Miller, Joseph S., The K-degrees, low for K degrees, and weakly low for K sets, Notre Dame Journal of Formal Logic, vol. 50 (2010), no. 4, pp. 381–391.Google Scholar
[68] Miller, Joseph S. and Nies, André, Randomness and computability: open questions, this Bulletin, vol. 12 (2006), no. 3, pp. 390–410.Google Scholar
[69] Miller, Joseph S. and Yu, Liang, On initial segment complexity and degrees of randomness, Transactions of the American Mathematical Society, vol. 360 (2008), no. 6, pp. 3193–3210.CrossRefGoogle Scholar
[70] Miller, Joseph S. and Yu, Liang, Oscillation in the initial segment complexity of random reals, Advances in Mathematics, vol. 226 (2011), no. 6, pp. 4816–4840.Google Scholar
[71] Muchnik, Andrei A. and Positselsky, Semen Ye., Kolmogorov entropy in the context of computability theory, Theoretical Computer Science, vol. 271 (2002), no. 1–2, pp. 15–35.CrossRefGoogle Scholar
[72] Nies, André, Lowness properties and randomness, Advances in Mathematics, vol. 197 (2005), no. 1, pp. 274–305.CrossRefGoogle Scholar
[73] Nies, André, Computability and randomness, Oxford University Press, 2009.Google Scholar
[74] Nies, André, Stephan, Frank, and Terwijn, Sebastiaan A., Randomness, relativization and Turing degrees, The Journal of Symbolic Logic, vol. 70 (2005), no. 2, pp. 515–535.Google Scholar
[75] Odifreddi, Piergiorgio, Classical recursion theory, vol. I, North-Holland, 1989.Google Scholar
[76] Raichev, Alexander and Stephan, Frank, A minimal rK-degree, In Goncharov et al. [47], pp. 261–270.Google Scholar
[77] Reimann, Jan and Stephan, Frank, Hierarchies of randomness tests, In Goncharov, et al.[47], pp. 215–232.Google Scholar
[78] Sacks, Gerald E., On the degrees less than 0′, Annals of Mathematics. Second Series, vol. 77 (1963), pp. 211–231.Google Scholar
[79] Sacks, Gerald E., The recursively enumerable degrees are dense, Annals of Mathematics. Second Series , vol. 80 (1964), pp. 300–312.Google Scholar
[80] Sgall, Jiri, Pultr, Ales, and Kolman, Petr (editors), Mathematical Foundations of Computer Science 2001, Lecture Notes in Computer Science, vol. 2136, Springer, 2001.Google Scholar
[81] Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer, 1987, A study of computable functions and computably generated sets.Google Scholar
[82] Solomonoff, Ray J., A formal theory of inductive inference. I, Information and Control, vol. 7 (1964), pp. 1–22.Google Scholar
[83] Solovay, R., Handwritten manuscript related to Chaitin's work, 1975, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages.Google Scholar
[84] Sterkenburg, Tom, Sequences with trivial initial segment complexity, MSc dissertation, University of Amsterdam, 02 2011.Google Scholar
[85] Turing, Alan M., Systems of logic based on ordinals, Proceedings of the London Mathematical Society. Third Series , vol. 45 (1939), pp. 161–228.Google Scholar