Post's theorem (computable iff r.e. and co-r.e.)
ProvedFamousTheorems.post_computable_iff_re_and_co_rePost's theorem. A predicate on a computably encodable type is computable (decidable by an algorithm) if and only if both and its negation are recursively enumerable.
One direction is immediate. For the other, run the enumerations of and in parallel; each input eventually appears in exactly one of them. The theorem is a basic fact of computability theory and underlies many undecidability arguments: the halting set is r.e. but not computable, so its complement cannot be r.e.
Formalization note. Mathlib's ComputablePred.computable_iff_re_compl_re. Primcodable α gives an encoding of into , ComputablePred p means is decidable by a computable function, and REPred p means is recursively enumerable (semi-decidable). ComputablePred p asks for some computable decision procedure; the DecidablePred p instance in the statement is only a classical decision function (every predicate has one) and does not restrict .
import Mathlib
namespace FamousTheorems
theorem post_computable_iff_re_and_co_re {α : Type*} [Primcodable α] {p : α → Prop} [DecidablePred p] :
ComputablePred p ↔ REPred p ∧ REPred fun a => ¬p a := by sorry
end FamousTheorems