iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/BF01409968
Busy beaver competition and Collatz-like problems | Archive for Mathematical Logic Skip to main content
Springer Nature Link
Log in

Busy beaver competition and Collatz-like problems

  • Published:
Archive for Mathematical Logic Aims and scope Submit manuscript

Summary

The Busy Beaver Competition is held by Turing machines. The better ones halt taking much time or leaving many marks, when starting from a blank tape. In order to understand the behavior of some Turing machines that were once record holders in the five-state Busy Beaver Competition, we analyze their halting problem on all inputs. We prove that the halting problem for these machines amounts to a well-known problem of number theory, that of the behavior of the repeated iteration of Collatz-like functions, that is functions defined by cases according to congruence classes.

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, A.H.: The determination of the value of Rado's noncomputable function Σ(k) for fourstate Turing machines. Math. Comput.40, 647–665 (1983)

    Google Scholar 

  2. Brady, A.H.: The busy beaver game and the meaning of life. In: Herken, R. (ed.) The universal Turing machine, pp. 259–277. Oxford Oxford University Press 1988

    Google Scholar 

  3. Conway, J.H.: Unpredictable iterations. In: Proceeding 1972 Number Theory Conference, pp. 49–52. Boulder, Colorado: University of Colorado 1972

    Google Scholar 

  4. Dewdney, A.K.: Computer recreations. Scientific American251 (2), 10–17 (1984)

    Google Scholar 

  5. Dewdney, A.K.: Computer recreations. Scientific American251 (5), 27 (1984)

    Google Scholar 

  6. Dewdney, A.K.: Computer recreations. Scientific American252 (4), 16 (1985)

    Google Scholar 

  7. Green, M.W.: A lower bound on Rado's sigma function for binary Turing machines. In: Proceeding 5th IEEE Symposium on Switching Circuit and Logical Design, pp. 91–94. New York: IEEE 1964

    Google Scholar 

  8. Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, MA: Addison-Wesley 1979

    Google Scholar 

  9. Lagarias, J.C.: The 3x+1 problem and its generalizations. Am. Math. Mon.92, 3–23 (1985)

    Google Scholar 

  10. Lin, S., Rado, T.: Computer studies of Turing machines problems. J. ACM12, 196–212 (1965)

    Google Scholar 

  11. Machlin, R., Stout, Q.F.: The complex behavior of simple machines. Physica D42, 85–98 (1990)

    Google Scholar 

  12. Mahler, K.: An unsolved problem on the powers of 3/2. J. Aust. Math. Soc.8, 313–321 (1968)

    Google Scholar 

  13. Marxen, H., Buntrock, J.: Attacking the Busy Beaver 5. Bull. EATCS40, 247–251 (1990)

    Google Scholar 

  14. Michel, P.: Étude de machines de Turing et complexité algorithmique. Thèse Université Paris 7 1992

  15. Oberschelp, A., Schmidt-Göttsch, K., Todt, G.: Castor quadruplorum. Arch. Math. Logic27, 35–44 (1988)

    Google Scholar 

  16. Pavlotskaya, L.M.: Solvability of the halting problem for certain classes of Turing machines. Math. Notes13, 537–541 (1973)

    Google Scholar 

  17. Rado, T.: On non computable functions. Bell Syst. Tech. J.41, 877–884 (1962)

    Google Scholar 

  18. Robinson, R.M.: Minsky's small universal Turing machine. Int. J. Math.2, 551–562 (1991)

    Google Scholar 

  19. Robinson, R.M.: Personal communication

  20. Rogozhin, Yu. V.: Seven universal Turing machines. Mat. Issled.69, 76–90 (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. 59 rue du Cardinal Lemoine, F-75005, Paris, France

    Pascal Michel

Authors
  1. Pascal Michel
    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

Michel, P. Busy beaver competition and Collatz-like problems. Arch Math Logic 32, 351–367 (1993). https://doi.org/10.1007/BF01409968

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation