# bbsearch
**Repository Path**: loader3229/bbsearch
## Basic Information
- **Project Name**: bbsearch
- **Description**: A Busy Beaver core landmark searcher — a depth-first search over a given Turing machine core (core), looking for the maximum landmark configuration that core can produce.
- **Primary Language**: C++
- **License**: GPL-3.0
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No
## Statistics
- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-11-16
- **Last Updated**: 2026-11-16
## Categories & Tags
**Categories**: Uncategorized
**Tags**: None
## README
# bbsearch
A Busy Beaver **core** landmark searcher — a depth-first search over a given Turing machine core (core), looking for the **maximum landmark configuration** that core can produce.
This is a **single-file C++ command-line tool**. Core data comes from loader3229's Busy Beaver core list ([bbcores_new.txt](bbcores_new.txt)); the program reads the cores from that list at run time (currently 48), and can search them one at a time or all at once.
## Features
- **48 cores**: covering the `f_ω`, `f_(ω+1)` … `f_(ω*2+1)`, `f_(ω^2)`, `f_(ω^2+1)`, `f_(ω^2+2)`, `f_(ω^2+3)`, `f_(ω^ω)`, `f_(ω^ω+1)`, `f_(ε0)` families, with 3–17 states and 3–7 symbols
- **Core table comes from the list file**: the program reads [bbcores_new.txt](bbcores_new.txt) at run time (each core is a `name` / `cfg` / `slot` / `core` four-line block); `--cores-file` changes the path; there is no built-in copy in the code
- **New cores can be added by hand**: discovering a Turing machine core that is not in the list yet is enough — append its four-line block to `bbcores_new.txt` and `bbsearch` searches that core's landmark configuration on the next run, with no recompilation
- **Three landmark structures**: the tool recognises `0^inf 3^(2m+1) 2^k
1^n ` (`KIND_BCFG`), `0^inf 3^n 0^inf` (`KIND_THREE`) and `0^inf 1^m ` (`KIND_ONES`, the head cell is the first cell of the right-hand first segment) automatically
- **Per-core importance order**: every core has its own counter precedence order (compared lexicographically), e.g. `fw3_4` is `p > k > n > m`
- **DFS + Zobrist hash cycle detection**: expands every machine containing that core over a blank tape, branching on FREE cells to fill the table
- **Two start modes**: `--start blank` (default, blank tape `0^inf A> 0^inf`) and `--start cfg` (start from the documented input configuration, for cores without a construction phase)
- **Landmark spec overridable at run time**: `--left5 / --right / --slots / --noblank` let you try another landmark guess without recompiling
> This is a **simulation search, not a proof**. The tool reports "the maximum landmark configuration found within the given search budget"; it does not establish a mathematical conclusion.
## Quick start
> **Platform note**: the commands below are written in the Linux/macOS form (`./bbsearch`). On Windows the compiler produces `bbsearch.exe`, so use `.\bbsearch.exe` (or `./bbsearch.exe`) in PowerShell. The build command itself is identical on both platforms.
### Build
Requires any C++11 compiler (`g++` is used below); there are no third-party dependencies.
```bash
cd /path/to/bbsearch
g++ -O3 -march=native -std=c++11 -o bbsearch bbsearch.cpp
```
`-march=native` is an optimisation flag and can be dropped on machines where it is unsupported.
### List all cores
```bash
cd /path/to/bbsearch
./bbsearch --cores
```
Each output line lists, in order: core name, number of states, number of symbols, landmark template, counter importance order.
### Search a single core
```bash
cd /path/to/bbsearch
./bbsearch --core fw1_6 --states 3 --cap 50000 --budget 3e9
```
### Search all cores
```bash
cd /path/to/bbsearch
./bbsearch --all --cap 200000 --budget 3e9 --log all.log
```
### Start from the input configuration for cores without a construction phase
```bash
cd /path/to/bbsearch
./bbsearch --core dfw_4 --start cfg --states 4 --startstate B --k 16 --n 3
```
## Configuration
The tool has **no configuration file**; everything is controlled by command-line options. The full option reference is in [docs/cli-reference.md](docs/cli-reference.md).
The most commonly used options:
| Option | Default | Meaning |
|---|---|---|
| `--core NAME` | `fw1_6` | Select a core by name, or by index |
| `--states N` | The core's own fixed state count | Total machine states (3–25) |
| `--symbols N` | The core's own symbol count | Alphabet size (2–10); extra columns beyond the core's symbols are filled by the DFS |
| `--cap N` | `50000` | Step limit for a single run |
| `--budget N` | `0` (unlimited) | Total step budget for this run |
| `--start blank\|cfg` | `blank` | Start mode |
| `--startstate A..Y` | Depends on the mode | The state the machine starts in |
| `--k --n --m --p --q --r --r5` | `16 3 0 1 1 1 1` | Counter values for the input configuration in `cfg` mode |
## Adding a new core
The core table is **data, not code**: if you come across a Turing machine core that the list does not contain yet, you can add it yourself. No recompilation is needed — `bbsearch` reads the list at run time and picks the new core up immediately.
A core is a four-line block in [bbcores_new.txt](bbcores_new.txt):
```
name fwp22_5
cfg ACG> 3^m 4^n 0^k 4^1
slot k>=1 n>=2 m>=1
core
```
| Line | Meaning |
|---|---|
| `name` | The core's name, as passed to `--core` |
| `cfg` | The landmark shape; the letters before `>` are the states the head may be in (`ACG>` = `A`, `C` or `G`) |
| `slot` | The counters in importance order (left = most important), with optional minima such as `n>=2` |
| `core` | The transition rows, one per state, separated by `_`; every row is exactly `3 × nsym` characters (write, move `L`/`R`, next state) and `---` marks a FREE cell |
Afterwards run `./bbsearch --cores` and check that the row count grew by one and that the landmark template and the importance column are correct, then search the new core:
```bash
./bbsearch --core --cap 20000 --budget 2e7
```
A landmark that lies deep in the construction phase needs a larger `--budget` / `--cap`; `no landmark configuration was reached` only means the search stopped too early, not that the core cannot produce the shape. How to write each of the three landmark shapes, and the self-check script for the transition rows, are described in [docs/getting-started.md](docs/getting-started.md).
## Documentation
- [docs/index.md](docs/index.md) — documentation index
- [docs/architecture.md](docs/architecture.md) — internal structure and algorithms
- [docs/getting-started.md](docs/getting-started.md) — local development guide
- [docs/cli-reference.md](docs/cli-reference.md) — command-line option reference
- [docs/cores.md](docs/cores.md) — landmarks and measured reachability of the 48 cores
- [docs/faq-troubleshooting.md](docs/faq-troubleshooting.md) — common problems and troubleshooting
The rulebook for AI collaborators is in [AGENTS.md](AGENTS.md).
## Contributing
This project has no automated tests. After changing the core table or a landmark spec, run at least:
```bash
./bbsearch --cores
```
(on Windows: `.\bbsearch.exe --cores`)
and confirm that the number of output lines matches the number of cores and that the landmark templates and importance orders are correct; then run an actual search on the core you changed.
## License
Released under the GNU General Public License v3.0 — see [LICENSE.md](LICENSE.md).
## Acknowledgements
The core data and landmark descriptions come from loader3229's Busy Beaver core list (`bbcores_new.txt`), whose core table is based on work such as Pavel Kropitz's `f_ω` core and Racheline's `double f_ω` core. For mathematical background, see Michel's analysis of "cores in Busy Beaver champion machines".