arXiv preprint ·
Analysing Busy Beaver Machines (Or How to Find Ossified Ocelots)
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The busy beaver problem involves working with machines which can produce very large numbers, both for the output of certain Turing machines and for the number of steps taken to execute them. Given that these numbers can involve thousands of digits, it is crucial to have a means of proving properties of the relevant machines which allow manipulation of such large numbers. In this paper we introduce the notion of \textit{shape computations} as a means of isolating key properties that allow efficient execution of the relevant Turing machines based on verifiable properties of state transitions. In particular, this notion allows us to provide an analytical result which demonstrates the quadratic relationship between the size of the output and the number of steps required to generate it. We have also developed an initial implementation of our approach, and we provide empirical evaluation of it on a suite of 240 example machines.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Formal Languages & Automata
Copying along Arithmetic Progressions Cannot Simulate Interleaving with Polylogarithmic Loss
Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$
Differentiable Exact Learning
Stochastic Games with Distributional Entropy Objectives
Tensorized Automata: Algebraically Informed Representation Learning for Sequential Decision Making
Get the few papers worth your time in Formal Languages & Automata every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.