Turing machines deciders, part I

The bbchallenge Collaboration, Justin Blanchard, Konrad Deka, Nathan Fenner, Tony Guilfoyle, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, Pascal Michel, Mateusz Naściszewski, Tristan Stérin · 2025

Read Turing machines deciders, part I by The bbchallenge Collaboration, Justin Blanchard, Konrad Deka, Nathan Fenner, Tony Guilfoyle, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, Pascal Michel, Mateusz Naściszewski, Tristan Stérin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20563.txt.

Description

The bbchallenge Collaboration and ten named co-authors present the first part of a catalog of decider programs for five-state Turing machines. Their 2025 paper belongs to the Busy Beaver effort, which set out to prove that a certain step count, 47,176,870, is the longest any five-state machine can run before halting. The conjecture was proved in July 2024 with a formal Coq proof.

A decider is a program that rules on one machine, answering halt, never-halt, or unknown. Each decider in this volume hunts one style of non-halting behavior, such as loops that grow forever. These particular tools were built before the formal proof and mostly were not used in it. The team publish them as useful techniques for analyzing Turing machines in their own right. A second part covers the deciders the proof did use.

Catalog record

CREATORThe bbchallenge Collaboration, Justin Blanchard, Konrad Deka, Nathan Fenner, Tony Guilfoyle, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, Pascal Michel, Mateusz Naściszewski, Tristan Stérin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE140 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20563

Browse the full library · About the Tower of Babel