Busy beaver holdouts · proof files

Reading the Proofs

How to read the Lean and Coq files this project generates, without learning either language. You only need to read the statements. The computer has already checked the proofs.

The method: read statements, skip proofs

A proof file is a list of named facts. Each fact has a statement (what is claimed) and a proof (instructions that convince the checker). If the file compiles, every proof was accepted. So the proofs are for the machine, and the statements are for you.

/-- A comment for humans. Not checked. -/
theorem sweep_right (n : Nat) (L R : Tape) :
    steps (14 * n) ⟨…⟩ = some ⟨…⟩ := by
  have hn : … := by omega
  exact …

Lean Name in teal. Statement highlighted, between the : and the :=. Everything after := by is the proof, up to the next theorem or def.

(** A comment for humans. Not checked. *)
Lemma oentry : forall a b c,
  fO a (b + 6) (c + 2) -->+ fS1 (a + 1) (b + 6) c.
Proof.
  intros a b c. … lia.
Qed.

Coq Statement between the : and the first full stop. The proof sits between Proof. and Qed. The word Qed means the checker accepted it.

  1. Read the comment at the top of the file. Every generated file opens with a plain-English summary of what it contains and which script wrote it.
  2. Jump to the last theorem. It is the headline: nonhalting : ¬ HaltsFromBlank in Lean, nonhalt : ~ halts tm c0 in Coq. Both say the machine never halts from blank tape.
  3. Check the machine is the right one. Compare the twelve rows of the transition table near the top with the machine's text name. This is the one place a human must look.
  4. Read statements on the way up, as far as you are curious. Lines starting with def or Definition introduce vocabulary. Lines starting with theorem, Lemma or Theorem are facts.
  5. Look at how much was assumed. One command lists every unproved assumption behind a theorem. The section What to trust shows how to read its answer.

Tape notation, and a decoder

In comments and on the explainer pages, a tape is written the usual bbchallenge way: 0^inf B> 0 0 (01)^a 0 0 0 1 0^inf. The head is in state B and is reading the cell just right of B>. (01)^a is the word 01 repeated a times. 0^inf is blank tape to the edge.

In the proof files the same tape is spelled out as data, which is harder on the eye. Three things to know:

  • A cell is false / true in Lean and S0 / S1 in Coq, for 0 and 1.
  • A configuration is three parts: left of the head, right of the head (starting with the cell being read), and the state.
  • The left part is listed nearest cell first, so it reads backwards compared with the tape. The decoder below turns it the right way round.

Counts such as ⟨7, [0, 3]⟩ or mkLin 7 [0; 3] mean 7 + 0·(first variable) + 3·(second variable). With variables k and j that is 3j + 7.

As a tape
In the project's comment notation

The decoder understands the four spellings used in the project: Lean streams (cons, app, rep, blank), Lean templates (.b for one cell, .r for a run), Coq templates (TB, TR, mkMC) and anything in angle brackets ⟨left, right, .State⟩. In Lean's Tables.lean, ft is short for the word 01.

Five real excerpts, line by line

These are copied from the files for the two machines proved so far, bbchallenge ids 36670 and 113677. Pick an excerpt, then click any block of code to see what it says in plain words. Very long lines are cut with an ellipsis.

Symbol and keyword lookup

Type a symbol, a keyword or a plain word such as "every" or "halt". Lean spelling is on the left, Coq spelling in the middle.

LeanCoqRead it as

What to trust, and how much

Every claim on a proof-status page carries one of five tags. They say what stands behind the claim.

TagWhat checked itHow it looks in a fileWhat you are trusting
kernelThe proof assistant's kernel, a small program whose only job is to recheck every step.Lean ordinary proofs, rfl, omega, decide +kernel
Coq everything in tools/coq/busycoq/, including vm_compute
The kernel, and that the statement says what you think it says.
nativeLean compiled the check to machine code and ran it. Much faster, used when the kernel runs out of memory.Lean native_decideThe above, plus Lean's compiler. Still far stronger than our own code.
trustedA C or Python program in the repository, run exhaustively. No proof assistant involved.Files under c/ and py/That our program has no bug.
heuristicSampling, curve fitting, a pattern seen in a long run.Prose in the README and status page onlyNothing firm. It is a lead, not a result.
openNobody knows yet.

The three computing words

WordSystemMeaningTag
decide +kernelLeanThe statement is a yes/no question a program can answer. The kernel runs that program itself, step by step, and sees the answer is yes.kernel
native_decideLeanSame question, but the program is compiled and run at full speed outside the kernel. The kernel accepts the answer on the compiler's word.native
vm_computeCoqCoq's fast evaluator. It is part of Coq's kernel, so it counts like decide +kernel, yet it is fast enough for the long runs. This is why the Coq versions need nothing at the native level.kernel

Reading the list of assumptions

Lean's #print axioms nonhalting and Coq's Print Assumptions nonhalt list everything a theorem rests on that was not proved. This is the single most useful line of output.

It printsSystemMeaning
Closed under the global contextCoqNo assumptions at all. The best possible answer. All five Coq proofs in this repository print this (see tools/coq/busycoq/build.log and the coq/build.log of the three other machines).
propext, Quot.sound, Classical.choiceLeanLean's three standard axioms, used by nearly all Lean mathematics. Seeing only these means kernel level. The Lean proof of 113677 lists exactly these.
Lean.ofReduceBool, Lean.trustCompilerLeanThe mark left by native_decide. The Lean proof of 36670 lists these, for its start run and its 62 end-of-epoch runs.
sorryAxLeanA hole. Some proof was skipped with sorry. The theorem is not proved. This must never appear.
a named Axiom, or anything AdmittedCoqSame: something was assumed, not proved. This must never appear.

Where the five proved machines stand

MachineLeanCoq (busycoq)
36670
1RB0LF_1LC0LA_1RA0RD_---1RE_1LA1RC_0LB0RC
kernel for the tables and the 62 rounds, native for the start and the 62 ends of an epoch. About 5 minutes.kernel throughout, no axioms. 79 seconds.
113677
1RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB
kernel throughout. Standard axioms only.kernel throughout, no axioms. About 3 minutes over three files.
65826
1RB0RC_0RC1RC_0LD0RA_1LE0LF_0LA1LC_---1LA
kernel for the symbolic executor's soundness, native for the two long replays and the twelve cycle rules.kernel throughout, no axioms. Under a minute.
11019
1RB0RD_1RC0LF_1LA0LB_---1RE_1LB1RA_0LC0RA
kernel for the executor's soundness, native for the 1,144 rounds, the arrival and the six cycle rules.kernel throughout, no axioms. A few minutes over eight chunks.
32641
1RB0RC_1LA0LD_1RB0RD_1LE0RF_0LB0RB_1RC---
kernel for the block simulator's correctness, native for the long fixed computations.kernel throughout, no axioms. Sixteen chunks; times are in its coq/README.md.

The worked examples on this page come from the first two machines. The other three were proved later, in the same two systems; their Coq files live next to their Lean files, in holdouts/<machine>/coq/, each with its own README and build script. The holdout map lists where every machine stands.

What still needs a human

  • The transition table. If a row were mistyped, the proof would be about a different machine. Twelve entries to compare. The Lean table is generated from the text name by leangen.py, but checking it by eye takes a minute.
  • The meaning of "step" and "halts". In Lean these are our own definitions, about thirty lines in tools/lean/TM/Basic.lean. In Coq they are busycoq's, written by someone else for the bbchallenge BB(5) effort. A proof against definitions we did not write is the stronger evidence, which is why the Coq versions exist.
  • Comments are not checked. A comment can drift from the statement under it. When they disagree, the statement is what was proved. The decoder above lets you compare a template with its comment.

What you do not need to trust: the Python generators, the tables of numbers they write, or the symbolic checker auto. A wrong number makes a check return false and the build fail. The checker comes with a soundness theorem (auto_reach in Lean, auto_sound and rules_sound in Coq) proving that an answer of true means the real machine makes that run.

Three words to search for. sorry, Admitted and axiom. Each marks something assumed without proof. A search on 12 November 2026 of the first two machines' Lean folders and all of tools/coq/busycoq/ found none.

File map and naming habits

holdouts/<machine name>/ README.md what it does, what is proved, what is open status.json the claims and their tags; the status page is built from it lean/ Machine.lean states and transition table (generated) Blank.lean when it halts; first 10⁴ and 10⁷ steps (generated) Rules.lean shift rules: crossing a repeated word in one go … files special to this machine; the last one holds the main theorem check.sh recompiles everything, in order py/ scripts that found the patterns and wrote the Lean files c/ fast simulators
tools/coq/busycoq/ README.md what is proved and how to build build.sh compiles everything against busycoq build.log the last clean build, with times lib/ BB62.v six states, two symbols SymRun.v the symbolic runner and its soundness proof SymForms.v templates and rules between them H36670/ one file: tables, checks, final theorem H113677/ _Rules, then _Table, then the final theorem gen/ the scripts that wrote the .v files holdouts/<machine name>/coq/ README.md the Coq proofs of 65826, 11019 and 32641 build_H….sh compiles that machine's files
Name patternWhat it tells you
H36670, H113677H for holdout, then the machine's bbchallenge id. Everything inside is about that one machine.
…_okA computation returned true. rounds_ok, ends_ok, start_ok, tables_ok.
…_sound, auto_reachA checker can be believed: if it says true, the machine really does it.
sweep_…, cycle, …_iterA rule: from this tape shape the machine reaches that one. _iter is the rule repeated k times.
halt_C, halt_routeA situation that leads to a halt. Used to know what must be avoided.
f… (fO, fS1, fT2)Coq: a tape form with its counts as arguments. The Lean files call the same forms O, S1, T2.
GoodThe invariant: the set of tape shapes the machine stays inside forever.
good_step, mv_…, step_…From any Good tape the machine reaches another Good tape after at least one step.
nonhalting, nonhaltThe final theorem.
(b + 6) in a statementA way to say "when this count is at least 6". Writing the count as b + 6 with b free covers 6, 7, 8 and so on.
fuel, 3000, Nat.pow 2 18The most moves a checker may use before giving up. Running out gives false, never a wrong true.

Step counts. Lean statements give exact step counts: steps (14 * n) c = some c' means exactly 14n steps. Coq statements only say "reaches": -->+ is one or more steps, -->* is zero or more. In Lean, a machine that halts on its next step has step c = none; bbchallenge counts that halting move as one more step.