Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Verifying Systems of Resource-Bounded Agents Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Busy Beavers and Kolmogorov Complexity

Author : Mikhail Andreev

Published in: Pursuit of the Universal

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The idea to find the “maximal number that can be named” can be traced back to Archimedes (see his Psammit [1]). From the viewpoint of computation theory the natural question is “which number can be described by at most n bits”? This question led to the definition of the so-called “busy beaver” numbers (introduced by T. Rado). In this note we consider different versions of the busy beaver-like notions defined in terms of Kolmogorov complexity. We show that these versions differ depending on the version of complexity used (plain, prefix, or a priori complexities) and find out how these notions are related, providing matching lower and upper bounds.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Computable Reductions and Reverse Mathematics
next chapter The Domino Problem for Self-similar Structures
Footnotes
1
One can define prefix complexity in different ways, using prefix-free decompressors (no element of the domain is a prefix of another element of the domain) or prefix-stable decompressors (if D(x) is defined, then \(D(y)=D(x)\) for every y that has prefix x). The argument works only for prefix-free decompressors; the problem with the prefix-stable ones is that computation time of a prefix-stable decompressor is not a prefix-stable function. It would be interesting to know whether the result remains true for prefix-stable decompressors.
 
2
One may also speak about semicomputability for sequences that have terms \(+\infty \) and/or \(-\infty \); in this case we allow the values of the function \(y(\cdot ,\cdot )\) to be infinite.
 
3
Technically speaking, Bob is obliged to react only if the Alice’s tail is strictly greater than \(2^{-n+a_n+d}\). But this leads only to a constant factor that is not important, so we ignore this problem.
 
Literature
1.
Archimedes: The Sand Reckoner. In: Heath, T.L. (ed.) The Works of Archimedes. Dover, New York (1953)
2.
3.
4.
Li, M., Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, New York (2008). (1st edn. (1993); 2nd edn. (1997), xxiii+790pp. ISBN 978-0-387-49820-1CrossRefMATH
5.
6.
Shen, A.: Around Kolmogorov complexity: basic notions and results. In: Vovk, V., Papadopoulos, H., Gammerman, A. (eds.) Measures of Complexity: Festschrift for Alexey Chervonenkis, pp. 75–116. Springer, Cham (2015). http://​arxiv.​org/​pdf/​1504.​04955
7.
Metadata
Title
Busy Beavers and Kolmogorov Complexity
Author
Mikhail Andreev
Copyright Year
2016
Book
Pursuit of the Universal

Print ISBN: 978-3-319-40188-1

Electronic ISBN: 978-3-319-40189-8

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-40189-8_20

Premium Partner

    Image Credits