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 fixed machine coding gives an acceptable numbering
Statement
Let be the partial function computed by the coded deterministic one-tape Turing machine with code on input , when decodes to a machine and that machine halts on ; if is malformed or the computation does not halt, leave undefined. Then is an acceptable numbering.
Facts & Assumptions
Given: The fixed machine coding from A fixed effective binary encoding of deterministic one-tape Turing machines.
A numbering is acceptable exactly when it is universal and has a total computable hard-wiring map satisfying by Universal and acceptable numberings.
The chosen machine coding has a total decoder that recovers the unique coded machine or reports malformed input, by The chosen machine coding is injective and has a total decoder.
The fixed machine encoding makes it effective to build a new coded machine from a finite machine description, by A fixed effective binary encoding of deterministic one-tape Turing machines.
Proof
This family is a numbering of the partial computable unary functions. If is partial computable, some deterministic one-tape Turing machine computes it. Relabel that machine's finite state set and tape alphabet by integers so that the start, accept, and reject states become and the symbols become the normalized alphabets of [L3]. The resulting coded machine has some code , and by construction .
The numbering is universal. On input , first run the total decoder from [L2]. If is malformed, diverge forever. If decodes to a machine , simulate on input and output exactly what outputs if it halts. This produces a partial computable binary function with .
For hard-wiring, given and , first run the total decoder [L2]. If is malformed, construct a fixed machine that diverges on every input. Otherwise construct a coded machine that on input first computes the pair code , then simulates the machine coded by on that code, and copies out the simulated output if the simulation halts. By [L2] and [L3], this case-defined map is total and computable.
By construction, for every one has So the function is the required hard-wiring operation from [L1].
Steps 1.1, 1.2, and 2.1 show that is a numbering, is universal, and has the required hard-wiring map. Therefore the fixed machine coding gives an acceptable numbering.
Depends on
Used by
Dependency tree · two levels
15 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)