Proof of `The acceptance problem for Turing machines is undecidable`
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The acceptance problem for single-tape Turing machines is undecidable.
Proof strategy
A decision procedure for the tape machines would decide : the partial function whose domain is is partial recursive, so by Turing-completeness one fixed tape machine accepts the unary encoding of exactly when , and the decision procedure applied to that machine and the unary inputs decides (). The bridge moves between the concept's machines and the source's.
Attribution
Sipser, Theorem 4.11 for the tape machines of Section 5.2; Lean proof by Aristotle ().