Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Approximate Uncomputability of the Kolmogorov Complexity Function

  • Conference paper
  • First Online:
Computing with Foresight and Industry (CiE 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11558))

Included in the following conference series:

Abstract

Kolmogorov complexity C(x) of a string x is the length of its shortest possible description. It is well known that C(x) is not computable. Moreover, any computable lower estimate of C(x) is bounded by a constant. We study the following question: suppose that we want to compute C with some precision and some amount of errors. For which parameters is it possible? Our main result is the following: the error must be at least an inverse exponential function of the precision. It gives two striking implications. Firstly, no computable function approximate Kolmogorov complexity much better than the length function does. Secondly, time-bounded Kolmogorov complexity is sufficiently far from unbounded Kolmogorov complexity for any particular computable time bound.

The reported study was funded by RFBR according to the research project 18-31-00428.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Bauwens, B., Makhlin, A., Vereshchagin, N., Zimand, M.: Short lists with short programs in short time. In: 2013 IEEE Conference on Computational Complexity (CCC), pp. 98–108. IEEE (2013)

    Google Scholar 

  2. Beigel, R., et al.: Enumerations of the Kolmogorov function. J. Symb. Log. 71(2), 501–528 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Fenner, S., Fortnow, L.: Compression complexity. arXiv preprint arXiv:1702.04779 (2017)

  4. Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Probl. Inf. Transm. 1(1), 1–7 (1965)

    MathSciNet  Google Scholar 

  5. Kummer, M.: On the complexity of random strings. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 25–36. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-60922-9_3

    Chapter  Google Scholar 

  6. Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications. Texts in Computer Science, 3rd edn. Springer, New York (2008). https://doi.org/10.1007/978-0-387-49820-1

    Book  MATH  Google Scholar 

  7. Nies, A.: Computability and Randomness, vol. 51. OUP Oxford (2009)

    Google Scholar 

  8. Shen, A., Uspensky, V.A., Vereshchagin, N.: Kolmogorov Complexity and Algorithmic Randomness, vol. 220. American Mathematical Society (2017)

    Google Scholar 

  9. Solomonoff, R.J.: A formal theory of inductive inference. Part I. Inf. control 7(1), 1–22 (1964)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We want to thank Alexei Milovanov and Alexander Shen for their support and advice during the work on this paper. We want to thank three anonymous referees for their useful comments about the text and the attendants of a seminar in LIRMM for their attention and questions.

Author information

Authors and Affiliations

  1. Moscow Institute of Physics and Technology, Dolgoprudny, Russia

    Ruslan Ishkuvatov & Daniil Musatov

  2. LIRMM CNRS & University of Montpellier, Montpellier, France

    Ruslan Ishkuvatov

  3. Russian Presidential Academy of National Economy and Public Administration, Moscow, Russia

    Daniil Musatov

  4. Caucasus Mathematical Center at Adyghe State University, Maykop, Russia

    Daniil Musatov

Authors
  1. Ruslan Ishkuvatov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniil Musatov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniil Musatov .

Editor information

Editors and Affiliations

  1. Christian Albrechts University of Kiel, Kiel, Germany

    Florin Manea

  2. Durham University, Durham, UK

    Barnaby Martin

  3. Durham University, Durham, UK

    Daniël Paulusma

  4. Università degli Studi di Milano, Milan, Italy

    Giuseppe Primiero

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ishkuvatov, R., Musatov, D. (2019). On Approximate Uncomputability of the Kolmogorov Complexity Function. In: Manea, F., Martin, B., Paulusma, D., Primiero, G. (eds) Computing with Foresight and Industry. CiE 2019. Lecture Notes in Computer Science(), vol 11558. Springer, Cham. https://doi.org/10.1007/978-3-030-22996-2_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-22996-2_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-22995-5

  • Online ISBN: 978-3-030-22996-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation