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

What is Decidability?

Define decidable languages and decision problems; understand when a TM can solve a problem algorithmically.

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:

  1. Halts on all inputs (never runs forever)
  2. Accepts inputs where the answer is "yes"
  3. 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.