Alphabeta MathHow 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.
Turing machines admit an effective enumeration
Statement
The coded deterministic one-tape Turing machines of A fixed effective binary encoding of deterministic one-tape Turing machines can be effectively enumerated.
Facts & Assumptions
Given: The fixed coding of deterministic one-tape Turing machines.
Every coded deterministic one-tape Turing machine has a binary code , by A fixed effective binary encoding of deterministic one-tape Turing machines.
The chosen coding has a total decoder and is injective, by The chosen machine coding is injective and has a total decoder.
Proof
Enumerate all binary words in shortlex order and run the total decoder from [L2] on each word. Whenever the decoder reports malformed input, output nothing; whenever it returns a coded machine, output that machine.
By [L1], every coded machine has some binary code , and shortlex enumeration eventually reaches that code. At that stage the decoder returns , so every coded machine appears somewhere in the output stream.
By injectivity in [L2], two different binary words cannot decode to the same coded machine. Therefore the procedure from step 1.1 lists each coded deterministic one-tape Turing machine exactly once and gives an effective enumeration.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
5 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)