Holkner. Acceleration Techniques for Busy Beaver Candidates ACCELERATION TECHNIQUES FOR BUSY BEAVER CANDIDATES

ABSTRACT: A busy beaver is a Turing machine of N states which, given a blank tape, halts with an equal or higher number of printed symbols than all other machines of N states. Candidates for this class of Turing machine cannot realistically be run on a traditional simulator due to their high demands on memory and time. This paper describes some techniques that can be used to run these machines to completion with limited memory, in a reasonable amount of time, and without human intervention. These techniques include using k-macro tape representation and arcs, and automatic inductive proof generation and utilization