Infinite Time Busy Beavers - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2017

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.
No file

Dates and versions

lirmm-02096207 , version 1 (11-04-2019)

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More