Computability theory and the halting problem #
THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
Any changes to this file require a corresponding PR to mathlib4.
A universal partial recursive function, Rice's theorem, and the halting problem.
A computable predicate is one whose indicator function is computable.
A recursively enumerable predicate is one which is the domain of a computable partial function.
ℕ-valued functions, a predicate for partial recursive