Infinite Time Busy Beavers
Résumé
In 1962, Hungarian mathematician Tibor Radó introduced in [8] the busy beaver competition for Turing machines: in a class of machines, find one which halts after the greatest number of steps when started on the empty input. In this paper, we generalise the busy beaver competition to the infinite time Turing machines (ITTMs) introduced in [6] by Hamkins and Lewis in 2000. We introduce two busy beaver functions on ITTMs and show both theoretical and experimental results on these functions. We give in particular a comprehensive study, with champions for the busy beaver competition, of the classes of ITTMs with one or two states (in addition to the halt and limit states). The computation power of ITTMs is humongous and thus makes the experimental study of this generalisation of Radó’s competition and functions a daunting challenge. We end this paper with a characterisation of the power of those machines when the use of the tape is restricted in various ways.