What is Decidability?
You'll learn: What it means for a problem to be decidable and when a Turing Machine can solve it algorithmically.
The Core Idea
Now that we've built Turing Machines and explored the Church-Turing Thesis, we can ask a fundamental question: Which problems can we actually solve with algorithms?
A decidable problem (or decidable language) is one where a Turing Machine exists that will always halt and correctly answer "yes" or "no" for every possible input. Think of it as a problem where an algorithm can definitively tell you the answer in finite time, guaranteed.
Decision Problems
A decision problem is any yes/no question about an input. For example:
- "Is this string a palindrome?"
- "Is this number prime?"
- "Does this grammar generate the string w?"
A decision problem is decidable if there's a Turing Machine that:
- Halts on all inputs (never runs forever)
- Accepts inputs where the answer is "yes"
- Rejects inputs where the answer is "no"
This TM is called a decider because it decides membership in the language.
The Key Distinction
Remember that Turing Machines can accept languages, but some might loop forever on certain inputs. A decider is special—it always halts. This distinction matters because some problems look solvable but actually aren't: no algorithm exists that will always give you an answer in finite time.
Key Takeaway: A language or problem is decidable if a Turing Machine exists that halts on all inputs and correctly accepts or rejects them; such problems can be solved algorithmically with guaranteed termination.