BusyBeaver

Busy Beaver 4‑State, 2‑Symbol Explorer A multithreaded C++ project that brute‑forces all 4‑state, 2‑symbol Turing machine transition tables with exactly one halting transition. It discovers Busy Beaver candidates—especially the known 107‑step, 13‑one machine—and writes “interesting” halting machines to a file.

Table of Contents

1. Project Overview
2. Prerequisites
3. Build Instructions
4. Configuration & Modes 4.1 Dry‑Run Mode 4.2 Full‑Simulation Mode
5. Usage Examples
6. Code Structure
7. Performance & Scaling
8. Credits
9. License

1. Project Overview

This repository explores all 4‑state, 2‑symbol Turing machines that have exactly one halting transition. There are 8,589,934,592 ≈ 2^(3×8) possible tables in total. Each table is generated, pruned if invalid (more than one 'H'), and—if in full‑simulation mode—simulated to see if it halts. Machines that halt write their step count, number of 1’s on the tape, and transition table to halting_machines.txt.

Why 4‑State, 2‑Symbol?

The classic Busy Beaver record for 4 states, 2 symbols is known: it halts in 107 steps and writes 13 ones. Exhaustively generating all 4‑state tables verifies that result and finds any other halting machines. This code is intended as a template for anyone wanting to scale up to 5‑state (trade‑off: ~1.5×10^16 tables, requiring massive hardware).

2. Prerequisites

1. C++17‑capable compiler (tested with g++ 10.x on Linux x86_64).
2. POSIX Threads support (-pthread).
3. Make or any build system (optional; instructions assume manual g++).
4. 60 GB+ disk space (if you plan to save all halting tables, though only a handful that halt are actually interesting).
5. 8 GB+ RAM (for multithreading, but memory usage is modest beyond code and buffers).

3. Build Instructions

1. Clone this repository

git clone https://github.com/pollardd/busy‑beaver‑explorer.git cd busy‑beaver‑explorer

2. Compile with C++17 and pthread

g++ -std=c++17 -O2 -pthread busy_beaver_multithreaded.cpp -o busy_beaver -O2 enables optimizations. -pthread links POSIX threads. For debugging symbols, replace -O2 with -g -O0.

3. Verify the executable

ls -lh busy_beaver Should show a nonzero executable file.

4. Configuration & Modes

All configuration flags live at the top of busy_beaver_multithreaded.cpp. You can adjust:

debug_level (int)

0 = no debug output
1 = basic progress every reportEvery tables generated
2 = per‑machine dry‑run logging
3 = simulate a single known Busy Beaver (quick test)

dry_run (bool)

true = generate tables, check only against the known 107‑step Busy Beaver, exit immediately on match
false = generate → enqueue valid tables → simulate each table in multiple threads

reportEvery (int)

Controls how often (every N tables) to print “Total tables generated” stats.

TASK_QUEUE_MAX (size_t)

Maximum number of tasks buffered in the queue before blocking.

4.1 Dry‑Run Mode

In dry_run mode, the generator will: Recursively build every 4‑state, 2‑symbol transition table with exactly one 'H'. Skip all simulations; only check if the generated table matches the known 107‑step, 13‑one Busy Beaver. Exit immediately upon finding that table, printing its transition specification and halting stats. Print a final summary of (Total generated) / (Estimated total ≈ 8.59e9) plus counters for rejected (no halt), pruned (all self‑loops), and valid tables (none in dry‑run except the match). Dry‑run mode runs in just a few minutes on modern hardware, since no simulation is performed.

4.2 Full‑Simulation Mode

With dry_run = false, the program:

Generates all tables with exactly one 'H'.
Prunes any table with all self‑loops.
Enqueues valid tables into a bounded queue of size TASK_QUEUE_MAX.
Launches N = hardware_concurrency() worker threads.
Each worker pops a task, calls simulate_machine(), and increments counters.
Whenever a machine halts, output_transition_table(...) prints its ID, step count, ones written, and full transition map; it also appends to halting_machines.txt.
After all workers join, a final summary prints total generated, valid, pruned, and rejected counts, plus elapsed time.
Caution: Full simulation of 8.59 billion tables (≈ 4.29 billion halting candidates) can take several hours depending on CPU cores.  

5. Usage Examples

./busy_beaver

5.1 By default, debug_level = 1, dry_run = true.

You’ll see:

Streaming 4-state 2-symbol Turing machine transition tables... Progress: ID = 0
Progress: ID = 100000000
... Progress: ID = 10400000000
=== Interesting Machine #0 ===
Steps: 107
Ones: 13
Transition Table:
(A, 0) -> (1, R, B)
(A, 1) -> (0, L, A)
(B, 0) -> (1, L, A)
(B, 1) -> (0, L, C)
(C, 0) -> (1, R, H)
(C, 1) -> (1, L, D)
(D, 0) -> (1, R, D)
(D, 1) -> (0, R, A)

✅ Dry-run matched known 107-step Busy Beaver machine! The program exits immediately upon finding the known table.

5.2 Full‑Simulation (Discover All Halting Machines)

Edit busy_beaver_multithreaded.cpp: const bool dry_run = false; Build g++ -std=c++17 -O2 -pthread busy_beaver_multithreaded.cpp -o busy_beaver Run ./busy_beaver You will see progress logs (every 100 million tables by default), then lines like this for every halting machine meeting your criteria (e.g. onesWritten >= 10). Interesting machines are also output to a log file halting_machines.txt.

=== Interesting Machine #685822902 === Steps: 64 Ones: 10 Transition Table: (A, 0) -> (0, L, B) (A, 1) -> (1, R, C) (B, 0) -> (1, L, C) (B, 1) -> (1, L, A) (C, 0) -> (1, R, A) (C, 1) -> (0, R, D) (D, 0) -> (1, L, A) (D, 1) -> (1, L, H)

At the end of the run a Final Summary is output. === Final Summary === Total tables generated: 8589934592 / ~8589934592 Valid tables: X Pruned tables: Y Rejected tables: 4294967296 Elapsed time: HH hours MM minutes SS seconds

Valid tables = # of machines enqueued for simulation Pruned tables = eliminated due to all self‑loops Rejected tables = eliminated due to halting count ≠ 1 You should see the 107/13 Busy Beaver among the “Interesting Machine” outputs.

6. Code Strtucture

. ├── busy_beaver_multithreaded.cpp # Main source file ├── bounded_queue.hpp # Thread‑safe bounded queue implementation ├── halting_machines.txt # (Output) All halting machines meeting criteria ├── README.md # This documentation └── test_atomic_overflow.cpp # Unit test for 64‑bit atomics (included for reference)

busy_beaver_multithreaded.cpp

Global Constants & Flags

debug_level (0–3), dry_run (bool), TASK_QUEUE_MAX, etc.

Data Types

struct Action { int write; char move; char nextState; }

using TransitionTable = std::map<std::pair<char,int>,Action>;

using Task = std::pair<TransitionTable, uint64_t>;

Atomic Counters (64‑bit)

machineID, totalGenerated, rejectedCount, prunedCount, validTableCount, attemptedHaltingTables, done_generating.

Key Functions

uint64_t estimatedTotalTables(int nStates, int nSymbols)

    Prints & returns the total possible table count.

bool simulate_machine(const TransitionTable& table, uint64_t machineID)

    Allocates a fixed‑size tape, runs transitions until halting or exceeding bounds.

    Prints “Halting Machine” info if debug_level >= 0.

bool is_known_busy_beaver_machine(const TransitionTable& table)

    Compares only the eight transitions of the known 107/13 Busy Beaver.

void generate_tables(int idx, TransitionTable& table, uint64_t halts)

    Recursively assigns (write, move, nextState) to all (state, symbol) slots.

    Prunes subtrees when halts > 1 or all‑self‑loops.

    In dry_run, checks for known machine and exits early if found.

    Otherwise enqueues valid (table, machineID) pairs for worker threads.

void worker_thread_func()

    Continuously pops tasks from the BoundedQueue, simulates them, increments counters.

    Exits when done_generating && queue.empty().

void generate_and_process_tables_multithreaded()

    Initializes a fresh TransitionTable, calls generate_tables(0,…), then sets done_generating.

int main()

    Prints startup banner, allocates bounded_queue, spawns worker threads, calls generator, waits for workers, prints final summary.

bounded_queue.hpp

template<typename T> class BoundedQueue

    Internally uses std::queue<T>, std::mutex, and std::condition_variable.

    push(const T&) blocks when the queue size ≥ max_size_.

    pop(T&) blocks when the queue is empty.

    try_pop(T&) returns immediately with false if empty.

    empty() and size() are thread‑safe.

7. Performance & Scaling

4 Intel CPU cores (8 threads) ran ~5.7 billion table generations in ~2 min 40 sec (dry‑run).

Full simulation (enqueue → simulate each halting candidate) on the same hardware takes several hours.

To scale to 5‑state, 2‑symbol (≈ 1.5 × 10^16 tables), you’ll need:

    Many more CPU cores (dozens or hundreds).

    Possibly distributed computing across multiple nodes.

    Optimized C data structures (e.g. bit‑packed transitions instead of std::map).

8. Credits

### Project Lead, Testing, Validation and Debugging:
    Davo’s Shed
        Provided test cases, identified the pruning bug, verified Busy Beaver detection, and guided design improvements.

### Algorithm Designer and Debugging Assistant:
    ChatGPT (OpenAI)
        Developed the recursive generator, multithreaded simulation, and debugging logic.