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

Proof of `The acceptance problem 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 ATMA_TM is undecidable (Sipser, Theorem 4.11).

Proof strategy

Diagonalisation, as in the textbook: a decider HH for ATMA_TM yields, by programming (Nat.Partrec.Code.existscodeNat.Partrec.Code.exists_code), a machine DD that accepts the code of a machine NN exactly when NN does not accept its own code (Acceptance.existsflipmachineAcceptance.exists_flip_machine in the source); DD on its own code is a contradiction (Acceptance.nodiagonalmachineAcceptance.no_diagonal_machine). The concept's definitions of machines, acceptance and ATMA_TM are the source's, so the source theorem is the statement.

Attribution

Sipser, Introduction to the Theory of Computation, Theorem 4.11; Lean proof by Aristotle (Acceptance.atmnotturingDecidableAcceptance.atm_not_turingDecidable).