Friedman's "Long Finite Sequences: The End of the Busy Beaver Contest

arXiv2303.02855MaRDI QIDQ6428484FDOQ6428484

Authors: Michael Vielhaber, Mónica del Pilar Canales Chacón, Sergio Jara Ceballos 

Publication date: 5 March 2023

Abstract: Harvey Friedman gives a comparatively short description of an ``unimaginably large number $n(3)$ , beyond, e.g. the values ${\displaystyle }$ A(7,184)< A({7198},158386) < n(3)${\displaystyle }$ of Ackermann's function - but finite. We implement Friedman's combinatorial problem about subwords of words over a 3-letter alphabet on a family of Turing machines, which, starting on empty tape, run (more than) $n(3)$ steps, and then halt. Examples include a (44,8) (symbol,state count) machine as well as a (276,2) and a (2,1840) one. In total, there are at most 37022 non-trivial pairs $(n,m)$ with Busy Beaver values $tBB(n,m)<A(7198,158386).$ We give algorithms to map any $(|Q|,|E|)$ TM to another, where we can choose freely either $|Q^{\prime }|geq2$ or $|E^{\prime }|geq2$ (the case $|Q^{\prime }|=2$ for empty initial tape is the tricky one). Given the size of $n(3)$ and the fact that these TMs are not {it holdouts}, but assured to stop, Friedman's combinatorial problem provides a definite upper bound on what might ever be possible to achieve in the Busy Beaver contest. We also treat $n(4)>A^{(A(187196))}(1)$.

This page was built for publication: Friedman's "Long Finite Sequences: The End of the Busy Beaver Contest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428484)