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 Turing-machine acceptance problem is recognizable
Statement
The language of The Turing-machine acceptance problem is recognizable.
Facts & Assumptions
Given: The coded language .
A binary word lies in exactly when it has the form for some coded deterministic one-tape Turing machine and some input word that accepts, by The Turing-machine acceptance problem .
The chosen machine encoding has a total decoder that either reconstructs the unique coded machine or reports malformed input, by A fixed effective binary encoding of deterministic one-tape Turing machines.
There is a deterministic one-tape interpreter that, from a valid pair consisting of a machine code and a configuration code, returns the same configuration code in the halting case and the unique one-step successor in the nonhalting case, by A fixed interpreter can execute one encoded machine step.
The well-formed machine-description language is decidable, by Well-formed deterministic one-tape Turing machine descriptions form a decidable language.
A language is recognizable when some deterministic Turing machine accepts exactly its members, while nonmembers may be rejected or may diverge, by Decidable and recognizable languages.
Proof
Build a deterministic one-tape machine that, on input , first parses as a candidate pair . If the pair parse fails, it rejects. It next runs the decider from [L4] on ; if is not a well-formed machine code, it rejects. If is valid, it uses [L2] to recover the coded machine . It then parses as a candidate word code , rejects if that parse fails, and also rejects if some recovered symbol lies outside the input alphabet . From the recovered word , the machine writes the canonical initial configuration code of on input .
The machine now repeatedly invokes the one-step interpreter from [L3] on the pair consisting of the recovered code and the current configuration code. After each return, it reads the decoded state component of that configuration code. If the state is accepting, accepts. If the state is rejecting, rejects. Otherwise it feeds the returned successor configuration back into the next interpreter call.
By [L3], each iteration in step 2.1 maintains exactly the current configuration of on . Therefore accepts precisely when eventually reaches an accepting configuration on , rejects when reaches a rejecting configuration, and diverges when diverges. By [L1] and [L5], this means that recognizes .
Depends on
- The Turing-machine acceptance problem $A_{TM}$
- A fixed effective binary encoding of deterministic one-tape Turing machines
- A fixed interpreter can execute one encoded machine step
- A universal Turing machine exists for the chosen coding
- Well-formed deterministic one-tape Turing machine descriptions form a decidable language
- Decidable and recognizable languages
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
18 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
- EECS 376 Course Notes, Part 6: Computability (standard reference, not scraped)
- Richard Zach, Sets, Logic, Computation: An Open Introduction to Metalogic (standard reference, not scraped)