Infinite Time Busy Beavers - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

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.
Fichier non déposé

Dates et versions

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

Identifiants

Citer

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⟩
119 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More