computable_iff_re_compl_re' — Mathlib

English

Same as Rice equivalence, expressed for the variant syntax; a predicate is computable iff both it and its negation are recursively enumerable.

Русский

То же самое, что и эквивалентность Риса, для варианта записи; predикат вычислим тогда и только тогда, когда и он, и его отрицание перечислимые.

LaTeX

$$$$\mathrm{ComputablePred}(p) \iff \mathrm{REPred}(p) \land \mathrm{REPred}(\lambda x. \neg p(x)).$$$$

Lean4

theorem computable_iff_re_compl_re' {p : α → Prop} : ComputablePred p ↔ REPred p ∧ REPred fun a => ¬p a := by
  classical exact computable_iff_re_compl_re

Похожие утверждения