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

A note on busy beavers and other creatures

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

Consider Turing machines that read and write the symbols 1 and 0 on a one-dimensional tape that is infinite in both directions, and halt when started on a tape containing all O's. Rado'sbusy beaver function ones(n) is the maximum number of 1's such a machine, withn states, may leave on its tape when it halts. The function ones(n) is noncomputable; in fact, it grows faster than any computable function.

Other functions with a similar nature can also be defined. The function time(n) is the maximum number of moves such a machine may make before halting. The function num(n) is the largest number of 1's such a machine may leave on its tape in the form of a single run; and the function space(n) is the maximum number of tape squares such a machine may scan before it halts.

This paper establishes a variety of bounds on these functions in terms of each other; for example, time(n) ≤ (2n − 1) × ones(3n + 3). In general, we compare the growth rates of such functions, and discuss the problem of characterizing their growth behavior in a more precise way than that given by Rado.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Brady, Allen H. (1983). The determination of the value of Rado's noncomputable function ∑(k) for four-state Turing machines.Mathematics of Computation, Vol. 40, No. 162, pp. 647–665.

    Article  MATH  MathSciNet  Google Scholar 

  2. Julstrom, Bryant A. (1992). A bound on the shift function in terms of the Busy Beaver function.SIGACT News, Vol. 23, No. 3 (Summer), pp. 100–106.

    Article  Google Scholar 

  3. Julstrom, Bryant A. (1993). Noncomputability and the Busy Beaver problem (UMAP Unit 728).The UMAP Journal, Vol. 14, No. 1, pp. 39–74.

    Google Scholar 

  4. Lin, Shen, and Tibor Rado (1965). Computer studies of Turing machine problems.Journal of the Association for Computing Machinery, Vol. 12, pp. 196–212.

    MATH  MathSciNet  Google Scholar 

  5. Marxen, Heiner, and Jürgen Buntrock (1990). Attacking the Busy Beaver Problem 5.Bulletin of the European Association for Theoretical Computer Science, Vol. 40, pp. 247–251.

    MATH  Google Scholar 

  6. Rado, Tibor (1962). On non-computable functions.The Bell System Technical Journal, Vol. 41, pp. 877–884.

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Tel Aviv University, Tel Aviv, Israel

    A. M. Ben-Amram & U. Zwick

  2. Department of Computer Science, St. Cloud State University, 56301, St. Cloud, MN, USA

    B. A. Julstrom

Authors
  1. A. M. Ben-Amram
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. A. Julstrom
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. U. Zwick
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ben-Amram, A.M., Julstrom, B.A. & Zwick, U. A note on busy beavers and other creatures. Math. Systems Theory 29, 375–386 (1996). https://doi.org/10.1007/BF01192693

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01192693

Keywords

Search

Navigation