Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-13T06:59:33.815Z Has data issue: false hasContentIssue false
  • English
  • Français

Relative Kolmogorov complexity and geometry

Published online by Cambridge University Press:  12 March 2014

Stephen Binns
Stephen Binns*
Affiliation:
Department of Mathematics and Statistics, King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We use the notions of effective dimension and Kolmogorov complexity to describe a geometry on the set of infinite binary sequences. Geometric concepts that we define and use include angle, projections and scalar multiplication. A question related to compressibility is addressed using these ideas.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 4 , December 2011 , pp. 1211 - 1239
Copyright
Copyright © Association for Symbolic Logic 2011

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]Downey, Rod and Greenberg, Noam, Turing degrees of reals of positive effective packing dimension, Information Processing Letters, vol. 108 (2008), pp. 198–203.CrossRefGoogle Scholar
[2]Downey, Rodney G and Hirschfeldt, Denis R, Algorithmic randomness and complexity, Springer, 2010.CrossRefGoogle Scholar
[3]Hitchcock, John M. and Athreya, Krishna B., Effective strong dimension, algorithmic information and computational complexity, SIAM Journal on Computing, vol. 37 (2007), no. 3, pp. 671–705.Google Scholar
[4]Lutz, Jack H., Gales and the constructive dimension of individual sequences, In Welzl, et al. [10], pp. 902–913.CrossRefGoogle Scholar
[5]Lutz, Jack H., The dimensions of individual strings and sequences, Information and Computation, vol. 187 (2003), pp. 49–79.CrossRefGoogle Scholar
[6]Lutz, Jack H., Effective fractal dimensions, Mathematical Logic Quarterly, vol. 51 (2005), pp. 62–72.CrossRefGoogle Scholar
[7]Mayordomo, Elvira, A Kolmogorov complexity characterization of constructive Hausdorff dimension, Information Processing Letters, vol. 84 (2002), no. 1, pp. 1–3.CrossRefGoogle Scholar
[8]Nies, André, Computability and randomness, Oxford University Press, 2009.CrossRefGoogle Scholar
[9]Reimann, Jan, Computability and fractal dimension, Ph.D. thesis, Ruprecht-Karls-Universität, Heidelberg, 2004.Google Scholar
[10]Welzl, E., Montanari, U., and Rolim, J. D. P. (editors), Proceedings of the 27th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, 1853, Springer, 2000.Google Scholar