×

Busy beaver competition and Collatz-like problems. (English) Zbl 0779.03009

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)

MSC:

03D10 Turing machines and related notions
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
11B99 Sequences and sets
PDFBibTeX XMLCite
Full Text: DOI

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.