Recursive and RE Sets

Mathematical Logic · Axiom Academy

Understanding the fundamental hierarchy of computability: recursive (decidable) sets, recursively enumerable sets, and their relationship to Turing machines In other words, for a recursive set, we can algorithmically decide membership: given any natural number n, we can determine in finite time whether n ∈ A or n ∉ A. The computation always terminates with a definite answer. The set of even numbers 0, 2, 4, 6, ... The empty set ∅ and the set of all natural numbers ℕ 2. Recursively Enumerable (RE) Sets For RE sets, if n ∈ A, the Turing machine will eventually halt and accept. However, if n ∉ A, the machine might run forever—we have no guarantee of termination for non-members. This is a semi-decision procedure : we can recognize membership but not necessarily non-membership. 3. Equivalent Characterizations of RE Recursively enumerable sets have several equivalent characterizations, all capturing the same intuitive concept: "we can recognize members if they exist." A is recursively enumerable (RE) A is the domain of a partial computable function A is the range of a (total or partial) computable function The domain characterization is particularly important: A is RE if and only if A = dom(φ) for some partial computable function φ. This means n ∈ A exactly when φ(n) is defined. Theorem: Recursive ↔ RE + Co-RE

This is the written version of the interactive lesson above. See the full Mathematical Logic course.