Turing Machine Acceptance and Halting: RE and Recursive Languages

1. The Two Tiers of Solvability

The behavior of a Turing Machine on a given language's strings can be categorized into two main levels of "solvability." One is a stronger guarantee than the other. Let's start with the strongest guarantee.

Recursive Languages (Decidable Languages)

Imagine an algorithm that you can always rely on to give you a definitive "yes" or "no" answer in a finite amount of time. This is the essence of a recursive language.

A language $L$ is recursive if there exists a Turing Machine M that decides it. This means M halts on every input string w:

• If $w\in L$, M halts in an accepting state.
• If $w\notin L$, M halts in a rejecting state.

Crucially, a TM that decides a language never loops. Because of this, recursive languages are also called decidable languages. The problem of determining membership in such a language is a "decidable problem."

Recursively Enumerable Languages (Turing-Recognizable Languages)

Now, consider a slightly weaker guarantee. Instead of a definitive yes/no, what if we only had a procedure that could confirm "yes" answers, but might run forever if the answer is "no"? This is the nature of a recursively enumerable language.

A language $L$ is recursively enumerable (RE) if there exists a Turing Machine M that recognizes it. This means:

• If $w\in L$, M halts in an accepting state.
• If $w\notin L$, M either halts in a rejecting state or loops forever.

The term "recursively enumerable" comes from an alternative definition: a language is RE if there is a TM (an "enumerator") that can output all the strings of the language, one by one. RE languages are also known as Turing-recognizable or semi-decidable languages.

To get a clear grasp of these two definitions and their differences, let's watch a short, focused video.

For a more detailed textual explanation that reinforces these concepts, you can review the following document.

2. The Relationship Between the Classes

From the definitions, you can see that any TM that is a decider (for a recursive language) also fits the criteria of being a recognizer (for an RE language). If a machine always halts, it certainly halts for strings in the language. This implies a clear hierarchical relationship:

The set of all recursive languages is a proper subset of the set of all recursively enumerable languages.

This relationship is perfectly captured by the following diagram:

This begs the question: what is an example of a language that is in the outer circle (RE) but not the inner one (Recursive)? We already have our canonical example: $A_{TM}$.

• $A_{TM}$ is Recursively Enumerable: As we discussed in the last lesson, the Universal Turing Machine U recognizes $A_{TM}$. Given input $⟨M,w⟩$, U simulates M on w. If M accepts w, U halts and accepts. This perfectly matches the definition of a recognizer for an RE language.

• $A_{TM}$ is Not Recursive: The UTM U loops if M loops on w. Since U does not halt on all inputs, it is not a decider. Therefore, $A_{TM}$ is not a recursive (decidable) language. (We will formally prove the undecidability of the closely related Halting Problem in a future lesson).

This video reinforces why $A_{TM}$ is recognizable.

3. A Decisive Characterization: Post's Theorem

The distinction between these two classes is elegantly captured by a result known as Post's Theorem. It gives us a way to test if a language is recursive by looking at its RE properties.

Theorem: A language $L$ is recursive if and only if both $L$ and its complement, $L^c$, are recursively enumerable.

Let's break down the intuition behind this proof, which should resonate with your software engineering background.

• Proof Sketch (⇒ "if" part): Assume both $L$ and $L^c$ are RE. This means we have a recognizer $M_L$ for $L$ and a recognizer $M_{L^c}$ for $L^c$. We can build a new TM, $M_{decider}$, that decides $L$. On any input w, $M_{decider}$ does the following:
  1. It runs $M_L$ and $M_{L^c}$ "in parallel" on input w. (In a single-tape TM, this is done by alternating steps: run one step of $M_L$, then one step of $M_{L^c}$, and so on).
  2. Since any string w must be in either $L$ or $L^c$, one of the two recognizers is guaranteed to eventually halt and accept.
  3. If $M_L$ accepts, then $M_{decider}$ halts and accepts.
  4. If $M_{L^c}$ accepts, then $M_{decider}$ halts and rejects.

This new machine, $M_{decider}$, is guaranteed to halt for every input w and give the correct answer. Therefore, $L$ is recursive.

• Proof Sketch (⇐ "only if" part): This direction is simpler. If $L$ is recursive, there is a decider $M$ for it.
  • $M$ itself serves as a recognizer for $L$, so $L$ is RE.
  • We can create a decider for $L^c$ by simply taking $M$ and swapping its accept and reject states. Since $L^c$ has a decider, it is also recursive, and therefore it is also RE.

This theorem provides a powerful link between the two classes. For the formal proof, which aligns with your interest in mathematical rigor, the following notes are an excellent resource.

An important consequence of this theorem is that if a language is RE but not recursive (like $A_{TM}$), then its complement cannot be recursively enumerable.

Conclusion

In this lesson, we have established the formal definitions that distinguish between fully solvable problems and partially solvable ones within the framework of Turing Machines.

Key Takeaways:

• A language is recursive (or decidable) if a Turing Machine exists that halts on all inputs, definitively accepting or rejecting.
• A language is recursively enumerable (RE) (or Turing-recognizable) if a Turing Machine exists that is guaranteed to halt and accept strings within the language, but may loop on strings not in the language.
• The class of recursive languages is a strict subset of the class of RE languages.
• The language of the Universal Turing Machine, $A_{TM}$, is our primary example of a language that is RE but not recursive.
• Post's Theorem provides a crucial link: a language $L$ is recursive if and only if both $L$ and its complement $L^c$ are recursively enumerable.

Preview of the Next Lesson:
Now that we have defined these important language classes, we can investigate their mathematical properties. In the next lesson, we will explore the closure properties of recursive and RE languages. We will ask questions like: If you take the union of two RE languages, is the result also RE? What about intersection or complement? Answering these questions helps us understand how these classes behave and how we can reason about the computability of complex problems.