Busy Beaver Machines and the Observant Otter Heuristic

Harland, J.

The busy beaver problem is to find the maximum number of non-zero characters that can be printed by an n-state Turing machine of a particular type. A critical step in the solution of this problem is to determine whether or not a given n-state Turing machine halts on a blank input. Given the enormous output sizes that can be produced by some small machines, it becomes critical to have appropriate methods for dealing with the exponential behaviour of both terminating and non-terminating machines. In this paper, we investigate a heuristic which can be used to greatly accelerate execution of this class of machines. This heuristic, which we call the observant otter, is based on the detection of patterns earlier in the execution trace. We describe our implementation of this method and report various experimental results based on it, including showing how it can be used to evaluate all known �monster� machines, including some whose naive execution would take around 1036,534 steps.

Cite as: Harland, J. (2013). Busy Beaver Machines and the Observant Otter Heuristic. In Proc. Theory of Computing 2013 (CATS 2013) Adelaide, Australia. CRPIT, 141. Wirth, A. Eds., ACS. 53-52

(from crpit.com) (local if available)