Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-27T19:50:57.740Z Has data issue: false hasContentIssue false
  • English
  • Français

MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY

Published online by Cambridge University Press:  17 April 2014

W. M. PHILLIP HUDELSON
W. M. PHILLIP HUDELSON*
Affiliation:
301 GRANT STREET, SUITE 2600, PITTSBURGH, PA 15219, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

By the complexity of a finite sequence of 0’s and 1’s we mean the Kolmogorov complexity, that is the length of the shortest input to a universal recursive function which returns the given sequence as output. By initial segment complexity of an infinite sequence of 0’s and 1’s we mean the asymptotic behavior of the complexity of its finite initial segments. In this paper, we construct infinite sequences of 0’s and 1’s with given recursive lower bounds on initial segment complexity which do not compute any infinite sequences of 0’s and 1’s with a significantly larger recursive lower bound on initial segment complexity. This improves several known results about randomness extraction and separates many natural degrees in the lattice of Muchnik degrees.

Keywords

Partial randomnessalgorithmic randomnessKolmogorov complexityMartin-Löf randomnesseffective Hausdorff dimension
Type
Articles
Information
The Journal of Symbolic Logic , Volume 79 , Issue 1 , March 2014 , pp. 20 - 44
Copyright
Copyright © Association for Symbolic Logic 2014 

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

Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Lempp, Steffen, and Slaman, Theodore A., Comparing DNR and WWKL, this Journal, vol. 69 (2004), no. 4, pp. 1089–1104.Google Scholar
Binns, Stephen, ${\rm{\Pi }}_1^0 $ classes with complex elements, this Journal, vol. 73 (2008) pp. 1341–1353.Google Scholar
Calude, Cristian S., Staiger, Ludwig, and Terwijn, Sebastiaan A., On partial randomness. Annals of Pure and Applied Logic, vol. 138 (2006), no. 1, pp. 20–30.CrossRefGoogle Scholar
Chaitin, Gregory J., Algorithmic information theory, vol. 1. Cambridge University Press, 2004.Google Scholar
Downey, Rodney G. and Hirschfeldt, Denis R., Algorithmic Randomness and Complexity. Springer, 2010.CrossRefGoogle Scholar
Greenberg, Noam and Miller, Joseph S., Diagonally non-recursive functions and effective Hausdorff dimension. Bulletin of the London Mathematical Society, vol. 43 (2011), no. 4, pp. 636–654.Google Scholar
Phillip Hudelson, W.M., Kolmogorov Complexity and Partial Randomness. Ph.D. dissertation, Pennsylvania State University, 2013.Google Scholar
Kjos-Hanssen, Bjørn, Merkle, Wolfgang, and Stephan, Frank, Kolmogorov complexity and the recursion theorem. Transactions of the American Mathematical Society, vol. 363 (2011), no. 10, pp. 5465–5480.Google Scholar
Kumabe, Masahiro and Lewis, Andrew E. M., A fixed-point-free minimal degree. Journal of the London Mathematical Society, vol. 80 (2009), no. 3, pp. 785–797.Google Scholar
Li, Ming and Vitányi, Paul, An Introduction to Kolmogorov Complexity and its Applications: Third Edition. Springer, 2008.CrossRefGoogle Scholar
Medvedev, Yuri T., Degrees of difficulty of the mass problem. Doklady Akademii Nauk SSSR (NS), vol. 104 (1955), pp. 501–504. In Russian.Google Scholar
Miller, Joseph S., Extracting information is hard: A Turing degree of non-integral effective Hausdorff dimension. Advances in Mathematics, vol. 226 (2011), no. 1, pp. 373–384.Google Scholar
Muchnik, Albert A., On strong and weak reducibilities of algorithmic problems. Sibirskii Matematicheskii Zhurnal, vol. 4 (1963), pp. 1328–1341. In Russian.Google Scholar
Nies, André, Computability and Randomness. Oxford University Press, 2009.CrossRefGoogle Scholar
Reimann, Jan, Computability and Fractal Dimension. Ph.D. dissertation, Ruprecht-Karls-Universität Heidelberg, 2004.Google Scholar
Reimann, Jan and Stephan, Frank, Hierarchies of randomness tests . In Mathematical Logic in Asia: Proceedings of the 9th Asian Logic Conference. (Goncharov, S. S., Downey, R, and Ono, H., editors). World Scientific Publishing, Hackensack, NJ, pp. 215–232, 2006.CrossRefGoogle Scholar
Simpson, Stephen G., Mass problems and randomness. Bulletin of Symbolic Logic, vol. 11 (2005), no. 1, pp. 1–27.CrossRefGoogle Scholar
Simpson, Stephen G., An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society, vol. 75 (2007), pp. 287–297.Google Scholar
Simpson, Stephen G., Mass problems and measure-theoretic regularity. Bulletin of Symbolic Logic, vol. 15 (2009), pp. 385–409.CrossRefGoogle Scholar
Tadaki, Kohtaro, A generalization of Chaitin’s halting probability Ω and halting self-similar sets. Hokkaido Mathematical Journal, vol. 31 (2002), no. 1, pp. 219–253.Google Scholar
Uspensky, V.A. and Shen, A., Relations between varieties of Kolmogorov complexities. Theory of Computing Systems, vol. 29 (1996), pp. 271–292.Google Scholar
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), no. 6, p. 83.Google Scholar