The undecidability of the halting problem
ProvedFamousTheorems.halting_problem_undecidableThe undecidability of the halting problem. Fix an input . There is no computable procedure that decides, given a program , whether halts on input .
This is Turing's theorem, the founding result of computability theory. Most other undecidability results, from Hilbert's tenth problem to the word problem for groups, are proved by reduction to it, and it underlies Gödel-type incompleteness phenomena.
Formalization note. Mathlib's ComputablePred.halting_problem. Programs are codes Nat.Partrec.Code for partial recursive functions, c.eval n is the (partial) result of running c on n, and .Dom says it is defined, i.e. the computation halts. ComputablePred means the predicate is decidable by a computable function.
import Mathlib
namespace FamousTheorems theorem halting_problem_undecidable (n : ℕ) : ¬ComputablePred fun c : Nat.Partrec.Code => (c.eval n).Dom := by sorry end FamousTheorems
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.