AFTD Auto-Formalizing Theoretical Domains

self_halting_problem_re

theoremverifiedformalization

The diagonal halting problem, consisting of codes c such that c halts on its own code, is recursively enumerable.

Statement

theorem self_halting_problem_re : REPred (fun c : Nat.Partrec.Code => (Nat.Partrec.Code.eval c (Encodable.encode c)).Dom)
Formalizes
standard textbook result (computability theory: the diagonal halting set is RE)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Lean source view module on GitHub

/-- The diagonal halting problem (self-halting problem) is recursively enumerable. -/
theorem self_halting_problem_re : REPred (fun c : Nat.Partrec.Code => (Nat.Partrec.Code.eval c (Encodable.encode c)).Dom) := (Nat.Partrec.Code.eval_part.comp Computable.id Computable.encode).dom_re
See it in the graphDiscuss this resultChallenge it