Proof of `The acceptance problem 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 is undecidable (Sipser, Theorem 4.11).
Proof strategy
Diagonalisation, as in the textbook: a decider for yields, by programming (), a machine that accepts the code of a machine exactly when does not accept its own code ( in the source); on its own code is a contradiction (). The concept's definitions of machines, acceptance and 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 ().