Efficient simulator of busy beaver Turing machines, capable of evaluating the best known 6-state machine (that halts after 7.412e36534 steps) in less than a minute on a single modern CPU core.
This is a C++11 implementation of the techniques described in Alex Holkner, 2004.
An AWK implementation by Heiner Marxen from 2006 can be found here.
A history of busy beaver machines can be found here.
A discussion of recent progress in evaluating all 5-state machines can be found here.
$ make get-deps
$ make -j8
$ make test
$ ./busy_beaver -h
This implementation currently only supports single-tape, 2-symbol
(binary), <=6-state machines. There is also a limitation that
macro_nbit <= 60.
The code implements 3 types of simulators, each building on the previous one:
-
Micro machine: represents the tape as individual bits and implements direct step-by-step evaluation of the Turing machine.
-
Macro machine: represents the tape as a run-length-encoded sequence of macro symbols (sequences of
macro_nbitbits on the tape) and implements accelerated simulation capable of updating whole runs at a time. -
Proof machine: identifies patterns in the history of the macro-machine simulation, attempts to prove that they will continue a certain number of times, and then applies them to skip the simulation ahead.
The macro machine implemented here does not currently support tail/back-context.
The simulation speed varies widely between different busy beaver
programs. While the best known 6-state machine can be readily
simulated to completion, some other machines simulate very slowly and
completing them is impractical (even though they may be known to halt
in fewer steps). The speed (and tape compression) can also depend
strongly on the choice of macro_nbit.