Skip to content

Latest commit

 

History

History
65 lines (47 loc) · 2.46 KB

README.md

File metadata and controls

65 lines (47 loc) · 2.46 KB

BB's Busy Beaver

Build Status

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.

Dependencies

Instructions

$ make get-deps
$ make -j8
$ make test
$ ./busy_beaver -h

About

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:

  1. Micro machine: represents the tape as individual bits and implements direct step-by-step evaluation of the Turing machine.

  2. Macro machine: represents the tape as a run-length-encoded sequence of macro symbols (sequences of macro_nbit bits on the tape) and implements accelerated simulation capable of updating whole runs at a time.

  3. 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.