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 chosen machine coding is injective and has a total decoder
Statement
The coding fixed in A fixed effective binary encoding of deterministic one-tape Turing machines is injective on coded deterministic one-tape Turing machines, and it has a total decoder that either reconstructs the unique coded machine or reports malformed input.
Facts & Assumptions
Given: The fixed coding scheme from A fixed effective binary encoding of deterministic one-tape Turing machines.
A coded deterministic one-tape machine is described by a finite tuple of binary numerals recording , , , and the lexicographically ordered transition triples, and its code is the result of applying the fixed tuple encoder to that description tuple, by A fixed effective binary encoding of deterministic one-tape Turing machines.
The machine definition fixes the single variable-arity encoder , whose arity header and self-delimiting entries give a total parser (A fixed effective binary encoding of deterministic one-tape Turing machines).
Proof
By [L1], each coded machine has one definite description tuple of some fixed length , and is exactly the tuple code of that tuple.
A total decoder first uses [L2] to parse the unary arity header and then exactly that many self-delimiting entries. If the parse fails or leaves unread bits, it returns the malformed token; otherwise it recovers one finite tuple of binary words.
If , then the global injectivity in [L2] gives equality of the decoded tuples, including their arities, so . By [L1], that common tuple records the same values of , , , and every transition triple for both machines. Hence .
The decoder then checks the shape demanded by [L1]: every entry must be a canonical binary numeral; the tuple must have length for the recovered first three numerals; one must have , , and ; and every transition entry must lie in . If any check fails, the decoder returns the malformed token. If all checks pass, those data determine one coded deterministic one-tape machine.
Step 2.1 proves injectivity, and steps 1.2 and 2.2 produce a total decoder. Therefore the chosen machine coding is injective and effectively decodable.
Depends on
Used by
Dependency tree · two levels
7 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
- Richard Zach, Sets, Logic, Computation: An Open Introduction to Metalogic (standard reference, not scraped)
- Michael Sipser, MIT 18.404J Theory of Computation, Lecture 6: TM Variants, Church-Turing Thesis (standard reference, not scraped)