Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-02
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.

The Turing-machine acceptance problem is recognizable

Statement

The language ATM of The Turing-machine acceptance problem ATM is recognizable.

Facts & Assumptions

Given: The coded language ATM.

[L1]

A binary word lies in ATM exactly when it has the form M,w^ for some coded deterministic one-tape Turing machine M and some input word w that M accepts, by The Turing-machine acceptance problem ATM.

[L2]

The chosen machine encoding has a total decoder that either reconstructs the unique coded machine or reports malformed input, by A fixed effective binary encoding of deterministic one-tape Turing machines.

[L3]

There is a deterministic one-tape interpreter that, from a valid pair consisting of a machine code and a configuration code, returns the same configuration code in the halting case and the unique one-step successor in the nonhalting case, by A fixed interpreter can execute one encoded machine step.

[L4]

The well-formed machine-description language is decidable, by Well-formed deterministic one-tape Turing machine descriptions form a decidable language.

[L5]

A language is recognizable when some deterministic Turing machine accepts exactly its members, while nonmembers may be rejected or may diverge, by Decidable and recognizable languages.

Proof

technique · direct
1.1

Build a deterministic one-tape machine R that, on input z, first parses z as a candidate pair x,y. If the pair parse fails, it rejects. It next runs the decider from [L4] on x; if x is not a well-formed machine code, it rejects. If x is valid, it uses [L2] to recover the coded machine M=(m,s,n,τ). It then parses y as a candidate word code c(bin())c(bin(a1))c(bin(a)), rejects if that parse fails, and also rejects if some recovered symbol ai lies outside the input alphabet Σs={1,,s}. From the recovered word w=a1a, the machine writes the canonical initial configuration code of M on input w.

L1L2L4givenconstruct
2.1

The machine R now repeatedly invokes the one-step interpreter from [L3] on the pair consisting of the recovered code x=M and the current configuration code. After each return, it reads the decoded state component of that configuration code. If the state is accepting, R accepts. If the state is rejecting, R rejects. Otherwise it feeds the returned successor configuration back into the next interpreter call.

L3step 1.1construct
3.1

By [L3], each iteration in step 2.1 maintains exactly the current configuration of M on w. Therefore R accepts precisely when M eventually reaches an accepting configuration on w, rejects when M reaches a rejecting configuration, and diverges when M diverges. By [L1] and [L5], this means that R recognizes ATM.

L1L3L5step 2.1

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

18 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