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 halting problem is recognizable and undecidable
Statement
The language of The halting problem is recognizable but not decidable.
Facts & Assumptions
Given: The halting language .
A binary word lies in exactly when it has the form and the decoded machine halts on the decoded input word , by The halting 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, and it is decidable when such a machine also halts on every input, by Decidable and recognizable languages.
A machine either halts on an input by reaching an accepting or rejecting configuration, or else diverges on that input, by Finite computation histories, halting computations, and divergence.
The acceptance language is undecidable, by The Turing-machine acceptance problem is undecidable.
Proof
Recognizability: 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 .
Undecidability: if were decidable, then by [L5] there would be a deterministic decider for . Given an input for , effectively build a machine that ignores its own input, simulates on , halts and accepts if that simulation accepts, and otherwise loops forever. Then . Indeed, halts on the blank input exactly in the case that accepts . So the assumed decider would decide , which [L7] forbids.
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 or rejecting, accepts. 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 or rejecting configuration on , and diverges when diverges. By [L1], [L5], and [L6], this means that recognizes .
Steps 3.1 and 1.2 prove recognizability and undecidability, respectively. Therefore is recognizable and undecidable.
Depends on
- The halting problem $HALT_{TM}$
- A fixed effective binary encoding of deterministic one-tape Turing machines
- A fixed interpreter can execute one encoded machine step
- Well-formed deterministic one-tape Turing machine descriptions form a decidable language
- The Turing-machine acceptance problem is undecidable
- Decidable and recognizable languages
- Finite computation histories, halting computations, and divergence
Used by
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
- Richard Zach, Sets, Logic, Computation: An Open Introduction to Metalogic (standard reference, not scraped)
- Stan Nelson, Computability: Undecidable Problems (standard reference, not scraped)