Course contentsShow
← Computer Science
Lesson 1875 of 2,87242. Turing Machines and ComputabilityFree lesson

Recognizable vs. Decidable

Clarify that recognizable languages may loop forever, while decidable languages always halt.

Recognizable vs. Decidable

What you'll learn: You'll understand the crucial difference between languages that Turing machines can recognize and those they can decide—one might loop forever, the other always stops.

The Core Distinction

A language is recognizable (also called recursively enumerable) if there exists a Turing machine that:

  • Accepts every string in the language (halts in an accepting state)
  • Rejects or loops forever on strings not in the language

A language is decidable (also called recursive) if there exists a Turing machine that:

  • Accepts every string in the language (halts in an accepting state)
  • Rejects every string not in the language (halts in a rejecting state)
  • Always halts—no infinite loops allowed

The Critical Difference: Halting Guarantee

The key distinction is what happens on strings not in the language. A recognizer might run forever searching for a reason to accept, never committing to rejection. A decider must eventually halt with a yes-or-no answer for every possible input.

An Analogy

Think of recognizable like a detective searching for evidence of guilt: if the person is guilty, they'll eventually find proof. But if innocent? The detective might search forever, never certain enough to declare innocence.

Decidable is like a court system with a deadline: guilty or innocent, a verdict must be reached in finite time.

The Hierarchy

Every decidable language is recognizable (if you always halt, you certainly halt on accepting inputs), but not every recognizable language is decidable. Some problems simply cannot guarantee termination on all inputs.

Key Takeaway: Recognizable languages may loop forever on non-members; decidable languages always halt with a definitive yes/no answer, making them strictly more powerful in practical terms.