Alphabeta Math
ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-13
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A two-step computation tableau and its local clauses

Example

Consider the one-tape machine with states q0,q1,qacc,qrej, alphabet {0,1,}, and instructions (q0,0)(q1,0,R) and (q1,)(qacc,,L). All other nonhalting state/symbol pairs go to rejection, leaving the scanned symbol unchanged and moving left. On the one-bit input 0 it accepts after exactly two transitions. With T=2,W=4, its three augmented rows are ((q0,0),,,),(0,(q1,),,),((qacc,0),,,). The input 0 can also be read as the paired encoding of empty input and empty fixed-length certificate for this fixed test. No certificate positions are left free in this instance.

Facts & Assumptions

Given: The displayed machine, input, rows and the assignment selecting exactly their displayed symbols.

[F1]

The tableau clause families use one-hot cells, pinned initial/guard cells and forbidden local tuples (Bounded Turing-computation tableaux).

[F2]

A consistent tableau decodes its actual accepting run (The tableau formula characterizes accepting computations).

Verification

1.1

Let a0=(q0,0), a1=(q1,), a2=(qacc,0) and B=. Set X0,0,a0=X1,1,a1=X2,0,a2=1, X1,0,0=1, and select B in all other cells. In every cell the positive symbol disjunction has one true term, and every pairwise exclusion has at least one true negated term. All initial units and the three right-guard units Xt,3,B are 1. The final accepting disjunction has its (j,a)=(0,0) term true.

F1given
2.1

The outputs required by the local rule at cells 0 through 3 for the first transition are 0,a1,B,B, and for the second are a2,B,B,B. At cell zero the first tuple is (#,a0,B,0); at cell one it is (a0,B,B,a1). In the second transition the corresponding tuples are (#,0,a1,a2) and (0,a1,B,B). Here # denotes the fixed exterior marker and contributes no Boolean literal. These four tuples follow the two table entries; cells two and three remain unmarked blanks because no head moves into them. Every forbidden-tuple clause therefore has at least one selected-symbol premise false, or its forbidden output false, and evaluates to 1.

F1step 1.1
3.1

Change just the first successor cell zero from unmarked 0 to unmarked 1, retaining one-hot encoding. The tuple (#,a0,B,1) is forbidden, and its explicit clause ¬X0,0,a0¬X0,1,B¬X1,0,1 now has values 000=0. Thus the correct assignment satisfies every clause whereas this altered assignment fails an actual local clause. F2 identifies the satisfying tableau with the stated two-step accepting run; for any larger allowed bound simply repeat its last row and add blank columns.

F1F2step 2.1

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources