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.
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.
nonhalting : ¬ HaltsFromBlank in Lean, nonhalt : ~ halts tm c0 in Coq. Both say the machine never halts from blank tape.def or Definition introduce vocabulary. Lines starting with theorem, Lemma or Theorem are facts.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:
false / true in Lean and S0 / S1 in Coq, for 0 and 1.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.
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.
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.
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.
| Lean | Coq | Read it as |
|---|
Every claim on a proof-status page carries one of five tags. They say what stands behind the claim.
| Tag | What checked it | How it looks in a file | What you are trusting |
|---|---|---|---|
| kernel | The proof assistant's kernel, a small program whose only job is to recheck every step. | Lean ordinary proofs, rfl, omega, decide +kernelCoq everything in tools/coq/busycoq/, including vm_compute | The kernel, and that the statement says what you think it says. |
| native | Lean compiled the check to machine code and ran it. Much faster, used when the kernel runs out of memory. | Lean native_decide | The above, plus Lean's compiler. Still far stronger than our own code. |
| trusted | A C or Python program in the repository, run exhaustively. No proof assistant involved. | Files under c/ and py/ | That our program has no bug. |
| heuristic | Sampling, curve fitting, a pattern seen in a long run. | Prose in the README and status page only | Nothing firm. It is a lead, not a result. |
| open | Nobody knows yet. |
| Word | System | Meaning | Tag |
|---|---|---|---|
| decide +kernel | Lean | The 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_decide | Lean | Same 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_compute | Coq | Coq'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 |
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 prints | System | Meaning |
|---|---|---|
| Closed under the global context | Coq | No 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.choice | Lean | Lean'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.trustCompiler | Lean | The mark left by native_decide. The Lean proof of 36670 lists these, for its start run and its 62 end-of-epoch runs. |
| sorryAx | Lean | A hole. Some proof was skipped with sorry. The theorem is not proved. This must never appear. |
| a named Axiom, or anything Admitted | Coq | Same: something was assumed, not proved. This must never appear. |
| Machine | Lean | Coq (busycoq) |
|---|---|---|
366701RB0LF_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. |
1136771RB0LE_1RC---_1RD1RE_1LA0RF_0RC0LA_0LC0RB | kernel throughout. Standard axioms only. | kernel throughout, no axioms. About 3 minutes over three files. |
658261RB0RC_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. |
110191RB0RD_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. |
326411RB0RC_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.
leangen.py, but checking it by eye takes a minute.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.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.
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.| Name pattern | What it tells you |
|---|---|
| H36670, H113677 | H for holdout, then the machine's bbchallenge id. Everything inside is about that one machine. |
| …_ok | A computation returned true. rounds_ok, ends_ok, start_ok, tables_ok. |
| …_sound, auto_reach | A checker can be believed: if it says true, the machine really does it. |
| sweep_…, cycle, …_iter | A rule: from this tape shape the machine reaches that one. _iter is the rule repeated k times. |
| halt_C, halt_route | A 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. |
| Good | The 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, nonhalt | The final theorem. |
| (b + 6) in a statement | A 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 18 | The 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.