HackerPapers

arXiv:1703.05170cs.CC

Busy beavers and Kolmogorov complexity

Mikhail Andreev

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

The idea to find the "maximal number that can be named" can be traced back to Archimedes (see his Psammit). 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.

arXiv comments
10 pages, CIE2016
Journal reference
DOI
Subjects
cs.CCComputational Complexity

On Hacker News

Linked by 1 identifiable commenter in 2 comments across 2 threads, from May 2024 to Jul 2024.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. With fifth busy beaver, researchers approach computation's limits 1 comment

    • > There are many variants of the original busy beaver problem, and some Busy Beaver Challenge contributors plan to keep working on these. One such variant is a functional busy beaver defined in terms of the lambda calculus [1]. Since it measures program size in bits rather than…

      trompView on HNParent context

  2. BB(3, 4) > Ack(14) 1 comment

    • Yes, for a busy beaver properly defined in information theoretic terms, like BBλ2 [1], one can prove that its champions must be incompressible up to some constant. Mikhail Andreev's article "Busy Beavers and Kolmogorov complexity" [2] explores these connections. [1]…

      trompView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.