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.

Shortest acceptance versus clocked all-branch halting

Example

Let N have distinct states q0,qacc,qrej,q. For each scanned symbol a, its initial options are (qacc,a,L) and (q,a,R). At q the only option writes the scanned symbol unchanged, moves right and stays in q. Thus on every binary input it has a one-step accepting branch and a diverging branch. A one-transition exact clock converts its cutoff to an all-branch-halting acceptor.

Facts & Assumptions

Given: The displayed finite machine, on any input x including the empty word.

[F1]

Shortest acceptance takes a minimum and may coexist with divergence; an inclusive exact-clock cutoff preserves precisely the timely accepting branches (Nondeterministic acceptance time and exact clocks).

[F2]

Cutoff scheduling gives a bounded all-branch machine for the cutoff language (Clocks, cutoffs, and finite unions preserve nondeterministic time bounds).

Verification

1.1

On either a bit or the blank scanned for empty x, N's first option enters the accepting state in one transition. Its start state is not accepting, so no length-zero acceptance exists and τN(x)=1. On the other branch it reaches cell one in state q after the first transition and cell t in that state after t transitions, for every t1. Hence this branch never halts and N has no finite all-branch running-time function. Its language is nevertheless all binary words.

F1given
2.1

Take a clock whose first transition on every symbol enters its halt state, so T(n)=1 exactly. Here its transition can be incorporated directly into the finite control: make the same two initial choices as N, but replace the q target by rejection. The resulting machine C has precisely two one-step branches, one accepting and one rejecting, on every input. Thus every branch halts after one step and L(C)={x:τN(x)1}={0,1}. This is an explicit optimized instance of the inclusive product-clock construction of F2, with no copying needed.

F1F2step 1.1
3.1

If one tests the cutoff zero instead, its language is empty because the initial state is nonaccepting. A decider can recognize it by a single rejecting transition, but it is not a zero-transition physical exact clock. At cutoff one, testing acceptance before expiry matters: rejecting immediately at the clock's last transition without testing N's simultaneous acceptance would incorrectly remove all inputs. C keeps that acceptance, as its two explicit branches show. This separates raw shortest and worst-branch times while verifying the correct clocked language and endpoints without AC.

F1step 1.1step 2.1

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 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