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 nonhalting set is productive and the halting set is creative
Statement
For the fixed machine-coding acceptable numbering of The fixed machine coding gives an acceptable numbering, let Then is productive, and therefore is creative.
Facts & Assumptions
Given: The diagonal halting set for the fixed machine-coding numbering.
A set is productive when it has a partial computable function defined with an escaping value on every index of a c.e. subset, and a set is creative when it is c.e. and its complement is productive, by Productive and creative sets.
The fixed machine-coding family is an acceptable numbering of the partial computable functions, by The fixed machine coding gives an acceptable numbering.
The chosen machine coding is injective and has a total decoder, by The chosen machine coding is injective and has a total decoder.
Proof
The set is computably enumerable: dovetail over all indices , decode each one using [L3], and simulate the decoded machine on input . Enumerate exactly when that simulation halts. By [L2], this lists precisely the numbers in .
For each , build a coded machine that on input simulates the enumeration of and halts exactly when the number appears in that enumeration. Let . The effective machine coding makes total computable; productivity in [L1] does not require this particular witness to be injective.
Assume . If , then by the definition of the computation halts, so , which contradicts . Therefore . But then the simulation inside never sees enter , so diverges and hence . Thus .
Step 2.1 shows that is a productive function for . By [L1], the complement of is productive. Together with step 1.1, [L1] gives that is creative.
Depends on
Used by
Dependency tree · two levels
11 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
- Robert I. Soare, Turing Computability: Theory and Applications (standard reference, not scraped)