Alphabeta Math
LemmaStatement: 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.

A hypothetical decider for ATM yields a diagonal self-application machine

Statement

Assume that some deterministic one-tape Turing machine H decides ATM. For a binary word x=b1b, let x be the word over Σ2={1,2} obtained by replacing each bit 0 by 1 and each bit 1 by 2. Then there exists a deterministic one-tape Turing machine DH with input alphabet Σ2 such that, for every coded deterministic one-tape Turing machine M whose input alphabet contains Σ2, DH accepts M    M does not accept M.

Facts & Assumptions

Given: A deterministic one-tape Turing machine H deciding ATM.

[L1]

A binary word belongs to ATM exactly when it is a coded pair M,w^ whose decoded machine M accepts the decoded input word w, by The Turing-machine acceptance problem ATM.

[L2]

The chosen machine encoding has a total decoder, so machine codes can be checked and decoded effectively, by A fixed effective binary encoding of deterministic one-tape Turing machines.

[L3]

A decider halts on every input and answers membership correctly, by Decidable and recognizable languages.

Proof

technique · direct
1.1

Construct a deterministic one-tape machine DH with input alphabet Σ2 as follows. On input a word yΣ2, first check whether every symbol is 1 or 2 and, if so, recover the unique binary word x obtained by replacing 1 by 0 and 2 by 1. Use [L2] to decode x as a candidate machine code. If x is malformed or decodes to a machine whose input alphabet does not contain both symbols 1 and 2, reject. Otherwise form the coded pair x,x^ and run H on that binary input. If H accepts, then loop forever; if H rejects, then accept. This machine is effective because the recoding xx, the machine-code decoder, and the call to H are all effective, and [L3] guarantees that the call to H halts.

L2L3givenconstruct
2.1

Let M be any coded deterministic one-tape Turing machine whose input alphabet contains Σ2, and put x=M. On input x, the preliminary checks in step 1.1 succeed, and the query sent to H is exactly M,x^=M,M^. By [L1] and the correctness of the decider H from [L3], H accepts that query exactly when M accepts x. Because DH does the opposite of H's answer, DH accepts x exactly when M does not accept x.

L1L3step 1.1
3.1

Step 2.1 is exactly the required diagonal property. Therefore the constructed machine DH exists.

step 2.1

Depends on

Used by

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