Infinite Time Busy Beavers

Abstract : 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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02096207
Contributor : Bruno Durand <>
Submitted on : Thursday, April 11, 2019 - 10:51:23 AM
Last modification on : Monday, January 20, 2020 - 12:14:07 PM

Identifiers

Citation

Oscar Defrain, Bruno Durand, Grégory Lafitte. Infinite Time Busy Beavers. CiE: Conference on Computability in Europe, Jun 2017, Turku, Finland. pp.221-233, ⟨10.1007/978-3-319-58741-7_22⟩. ⟨lirmm-02096207⟩

Share

Metrics

Record views

96