Draft — mutable and not usable as a dependency; its citation marks the draft state.

Proof of `The acceptance problem for Turing machines is undecidable`

groundedproofs/Lax251941Proofs/Results.lean · lax-251941

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.

Read the Lean proof on GitHub

Description

The acceptance problem for single-tape Turing machines is undecidable.

Proof strategy

A decision procedure for the tape machines would decide ATMA_TM: the partial function whose domain is ATMA_TM is partial recursive, so by Turing-completeness one fixed tape machine accepts the unary encoding of nn exactly when nATMn ∈ A_TM, and the decision procedure applied to that machine and the unary inputs decides ATMA_TM (Acceptance.tmacceptancenotcomputablyDecidableAcceptance.tm_acceptance_not_computablyDecidable). The bridge computablePredacceptsiffcomputablePred_accepts_iff 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 (RequestProject/Acceptance/Bridge.leanRequestProject/Acceptance/Bridge.lean).