On initial segment complexity and degrees of randomness
HTML articles powered by AMS MathViewer
- by Joseph S. Miller and Liang Yu PDF
- Trans. Amer. Math. Soc. 360 (2008), 3193-3210 Request permission
Abstract:
One approach to understanding the fine structure of initial segment complexity was introduced by Downey, Hirschfeldt and LaForte. They define $X\leq _K Y$ to mean that $(\forall n)\; K(X\upharpoonright n)\leq K(Y\upharpoonright n)+O(1)$. The equivalence classes under this relation are the $K$-degrees. We prove that if $X\oplus Y$ is $1$-random, then $X$ and $Y$ have no upper bound in the $K$-degrees (hence, no join). We also prove that $n$-randomness is closed upward in the $K$-degrees. Our main tool is another structure intended to measure the degree of randomness of real numbers: the $\textit {vL}$-degrees. Unlike the $K$-degrees, many basic properties of the $\textit {vL}$-degrees are easy to prove. We show that $X\leq _K Y$ implies $X\leq _{\textit {vL}} Y$, so some results can be transferred. The reverse implication is proved to fail. The same analysis is also done for $\leq _C$, the analogue of $\leq _K$ for plain Kolmogorov complexity. Two other interesting results are included. First, we prove that for any $Z\in 2^\omega$, a $1$-random real computable from a $1$-$Z$-random real is automatically $1$-$Z$-random. Second, we give a plain Kolmogorov complexity characterization of $1$-randomness. This characterization is related to our proof that $X\leq _C Y$ implies $X\leq _{\textit {vL}} Y$.References
- Gregory J. Chaitin, On the length of programs for computing finite binary sequences: statistical considerations, J. Assoc. Comput. Mach. 16 (1969), 145–159. MR 237121, DOI 10.1145/321495.321506
- Gregory J. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach. 22 (1975), 329–340. MR 411829, DOI 10.1145/321892.321894
- G. J. Chaitin, Incompleteness theorems for random reals, Adv. in Appl. Math. 8 (1987), no. 2, 119–146. MR 886921, DOI 10.1016/0196-8858(87)90010-8
- Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt, and Joseph S. Miller, Every 1-generic computes a properly 1-generic, J. Symbolic Logic 71 (2006), no. 4, 1385–1393. MR 2275865, DOI 10.2178/jsl/1164060461
- R. Downey and D. Hirschfeldt, Algorithmic randomness and complexity, Springer-Verlag, Berlin, To appear.
- Rod G. Downey, Denis R. Hirschfeldt, and Geoff LaForte, Randomness and reducibility, Mathematical foundations of computer science, 2001 (Mariánské Láznĕ), Lecture Notes in Comput. Sci., vol. 2136, Springer, Berlin, 2001, pp. 316–327. MR 1907022, DOI 10.1007/3-540-44683-4_{2}8
- Rod G. Downey, Denis R. Hirschfeldt, and Geoff LaForte, Randomness and reducibility, J. Comput. System Sci. 68 (2004), no. 1, 96–114. MR 2030512, DOI 10.1016/j.jcss.2003.07.004
- Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin’s halting probability, J. Math. Log. 5 (2005), no. 2, 167–192. MR 2188515, DOI 10.1142/S0219061305000468
- Péter Gács, Exact expressions for some randomness tests, Z. Math. Logik Grundlagen Math. 26 (1980), no. 5, 385–394. MR 589329, DOI 10.1002/malq.19800262502
- Péter Gács, Every sequence is reducible to a random one, Inform. and Control 70 (1986), no. 2-3, 186–192. MR 859105, DOI 10.1016/S0019-9958(86)80004-3
- A. N. Kolmogorov, Three approaches to the quantitative definition of information, Internat. J. Comput. Math. 2 (1968), 157–168. MR 243922, DOI 10.1080/00207166808803030
- Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
- Antonín Kučera and Sebastiaan A. Terwijn, Lowness for the class of random sets, J. Symbolic Logic 64 (1999), no. 4, 1396–1402. MR 1780059, DOI 10.2307/2586785
- S. Kurtz, Randomness and genericity in the degrees of unsolvability, Ph.D. Dissertation, University of Illinois, Urbana, 1981.
- Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
- L. A. Levin, Laws on the conservation (zero increase) of information, and questions on the foundations of probability theory, Problemy Peredači Informacii 10 (1974), no. 3, 30–35 (Russian). MR 0469513
- L. A. Levin, The concept of a random sequence, Dokl. Akad. Nauk SSSR 212 (1973), 548–550 (Russian). MR 0366096
- Ming Li and Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993. MR 1238938, DOI 10.1007/978-1-4757-3860-5
- Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602–619. MR 223179
- Per Martin-Löf, Complexity oscillations in infinite binary sequences, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 19 (1971), 225–230. MR 451322, DOI 10.1007/BF00534110
- Joseph S. Miller, Every 2-random real is Kolmogorov random, J. Symbolic Logic 69 (2004), no. 3, 907–913. MR 2078929, DOI 10.2178/jsl/1096901774
- Joseph S. Miller and Liang Yu, Oscillation in the initial segment complexity of random reals, In preparation.
- André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. MR 2166184, DOI 10.1016/j.aim.2004.10.006
- André Nies, Frank Stephan, and Sebastiaan A. Terwijn, Randomness, relativization and Turing degrees, J. Symbolic Logic 70 (2005), no. 2, 515–535. MR 2140044, DOI 10.2178/jsl/1120224726
- John C. Oxtoby, Measure and category, 2nd ed., Graduate Texts in Mathematics, vol. 2, Springer-Verlag, New York-Berlin, 1980. A survey of the analogies between topological and measure spaces. MR 584443
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- R. J. Solomonoff, A formal theory of inductive inference, Information and Control 7 (1964), 1–22, 224–254.
- Robert M. Solovay, Draft of paper (or series of papers) on Chaitin’s work, (1975), Unpublished notes, 215 pages.
- M. van Lambalgen, Random sequences, Ph.D. Dissertation, University of Amsterdam, 1987.
- Michiel van Lambalgen, The axiomatization of randomness, J. Symbolic Logic 55 (1990), no. 3, 1143–1167. MR 1071321, DOI 10.2307/2274480
- Liang Yu and Decheng Ding, There are $2^{\aleph _0}$ many $H$-degrees in the random reals, Proc. Amer. Math. Soc. 132 (2004), no. 8, 2461–2464. MR 2052426, DOI 10.1090/S0002-9939-04-07417-9
- Liang Yu, Decheng Ding, and Rodney Downey, The Kolmogorov complexity of random reals, Ann. Pure Appl. Logic 129 (2004), no. 1-3, 163–180. MR 2078364, DOI 10.1016/j.apal.2004.01.006
- A. K. Zvonkin and L. A. Levin, The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms, Uspehi Mat. Nauk 25 (1970), no. 6(156), 85–127 (Russian). MR 0307889
Additional Information
- Joseph S. Miller
- Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269-3009
- MR Author ID: 735102
- Email: joseph.miller@math.uconn.edu
- Liang Yu
- Affiliation: Department of Mathematics, National University of Singapore, Singapore 117543
- MR Author ID: 725077
- Email: yuliang.nju@gmail.com
- Received by editor(s): May 30, 2006
- Published electronically: January 10, 2008
- Additional Notes: The first author was partially supported by the Marsden Fund of New Zealand and by an NSF VIGRE postdoctoral fellowship at Indiana University
The second author was supported by a postdoctoral fellowship from the New Zealand Institute for Mathematics and its Applications, NSF of China No.10471060 and No.10420130638, and by No.R-146-000-054-123 of Singapore: Computability Theory and Algorithmic Randomness. Both authors were supported by the Institute for Mathematical Sciences, National University of Singapore, during the Computational Aspects of Infinity program in 2005. - © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 360 (2008), 3193-3210
- MSC (2000): Primary 68Q30, 03D30, 03D28
- DOI: https://doi.org/10.1090/S0002-9947-08-04395-X
- MathSciNet review: 2379793