Michel, Pascal Busy beaver competition and Collatz-like problems. (English) Zbl 0779.03009 Arch. Math. Logic 32, No. 5, 351-367 (1993). 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. Reviewer: P.Michel (Paris) Cited in 11 Documents MSC: 03D10 Turing machines and related notions 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 11B99 Sequences and sets Keywords:Busy Beaver Competition; Turing machines; halting problem; repeated iteration of Collatz-like functions PDFBibTeX XMLCite \textit{P. Michel}, Arch. Math. Logic 32, No. 5, 351--367 (1993; Zbl 0779.03009) Full Text: DOI Online Encyclopedia of Integer Sequences: Busy Beaver problem: a(n) = maximal number of steps that an n-state Turing machine can make on an initially blank tape before eventually halting. If n is divisible by 3, a(n) = n; otherwise n = 3k + r with r in {1, 2} and a(n) = a(5k + r + 3). a(n) = -1 if no multiple of three will be ever reached by iterating A353314. 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) · Zbl 0518.03013 [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 · Zbl 0685.68054 [3] Conway, J.H.: Unpredictable iterations. In: Proceeding 1972 Number Theory Conference, pp. 49-52. Boulder, Colorado: University of Colorado 1972 · Zbl 0337.10041 [4] Dewdney, A.K.: Computer recreations. Scientific American251 (2), 10-17 (1984) [5] Dewdney, A.K.: Computer recreations. Scientific American251 (5), 27 (1984) · doi:10.1038/scientificamerican1284-27 [6] Dewdney, A.K.: Computer recreations. Scientific American252 (4), 16 (1985) [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 [8] Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, MA: Addison-Wesley 1979 · Zbl 0426.68001 [9] Lagarias, J.C.: The 3x+1 problem and its generalizations. Am. Math. Mon.92, 3-23 (1985) · Zbl 0566.10007 · doi:10.2307/2322189 [10] Lin, S., Rado, T.: Computer studies of Turing machines problems. J. ACM12, 196-212 (1965) · Zbl 0137.01002 · doi:10.1145/321264.321270 [11] Machlin, R., Stout, Q.F.: The complex behavior of simple machines. Physica D42, 85-98 (1990) · doi:10.1016/0167-2789(90)90068-Z [12] Mahler, K.: An unsolved problem on the powers of 3/2. J. Aust. Math. Soc.8, 313-321 (1968) · Zbl 0155.09501 · doi:10.1017/S1446788700005371 [13] Marxen, H., Buntrock, J.: Attacking the Busy Beaver 5. Bull. EATCS40, 247-251 (1990) · Zbl 0744.68043 [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) · Zbl 0646.03034 · doi:10.1007/BF01625831 [16] Pavlotskaya, L.M.: Solvability of the halting problem for certain classes of Turing machines. Math. Notes13, 537-541 (1973) · Zbl 0284.02017 [17] Rado, T.: On non computable functions. Bell Syst. Tech. J.41, 877-884 (1962) [18] Robinson, R.M.: Minsky’s small universal Turing machine. Int. J. Math.2, 551-562 (1991) · Zbl 0792.68040 · doi:10.1142/S0129167X91000302 [19] Robinson, R.M.: Personal communication [20] Rogozhin, Yu. V.: Seven universal Turing machines. Mat. Issled.69, 76-90 (1982) · Zbl 0515.03020 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.