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 yields a diagonal self-application machine
Statement
Assume that some deterministic one-tape Turing machine decides . For a binary word , let be the word over obtained by replacing each bit by and each bit by . Then there exists a deterministic one-tape Turing machine with input alphabet such that, for every coded deterministic one-tape Turing machine whose input alphabet contains ,
Facts & Assumptions
Given: A deterministic one-tape Turing machine deciding .
A binary word belongs to exactly when it is a coded pair whose decoded machine accepts the decoded input word , by The Turing-machine acceptance problem .
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.
A decider halts on every input and answers membership correctly, by Decidable and recognizable languages.
Proof
Construct a deterministic one-tape machine with input alphabet as follows. On input a word , first check whether every symbol is or and, if so, recover the unique binary word obtained by replacing by and by . Use [L2] to decode as a candidate machine code. If is malformed or decodes to a machine whose input alphabet does not contain both symbols and , reject. Otherwise form the coded pair and run on that binary input. If accepts, then loop forever; if rejects, then accept. This machine is effective because the recoding , the machine-code decoder, and the call to are all effective, and [L3] guarantees that the call to halts.
Let be any coded deterministic one-tape Turing machine whose input alphabet contains , and put . On input , the preliminary checks in step 1.1 succeed, and the query sent to is exactly . By [L1] and the correctness of the decider from [L3], accepts that query exactly when accepts . Because does the opposite of 's answer, accepts exactly when does not accept .
Step 2.1 is exactly the required diagonal property. Therefore the constructed machine exists.
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
- A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (standard reference, not scraped)
- Richard Zach, Sets, Logic, Computation: An Open Introduction to Metalogic (standard reference, not scraped)