Skip to main content
⚡ Calmops
🤖 AI 🏗️ Architecture 🌐 Web 🗃️ Database ⚙️ DevOps 🌍 Network 💻 Programming 🧮 Algorithms 📐 Software Eng. ☁️ Cloud 🔒 Security 📈 Finance More →

Computability and Decidability

Created: December 20, 2025 7 min read

Introduction

Computability and decidability theory explores the fundamental limits of computation. It answers questions like:

  • What problems can be solved by algorithms?
  • What problems are fundamentally unsolvable?
  • How do we prove a problem is undecidable?

These concepts are essential for understanding:

  • The limits of programming
  • Complexity theory
  • Formal verification
  • Algorithm design

In this article, we’ll explore computability and decidability in depth.

Computability

Definition

A function is computable if there exists an algorithm (Turing machine) that computes it.

Formal Definition:

A function f: Σ* → Σ* is computable if there exists a Turing machine M such that:
- M halts on all inputs
- M outputs f(x) when given input x

Examples of Computable Functions

Arithmetic:

Addition: f(x, y) = x + y
Multiplication: f(x, y) = x * y
Factorial: f(n) = n!

String Operations:

Concatenation: f(x, y) = xy
Reversal: f(x) = x^R
Length: f(x) = |x|

Sorting:

Sort: f(list) = sorted list

Church-Turing Thesis

Statement: Any function that can be computed by an algorithm can be computed by a Turing machine.

Implications:

  • Turing machines capture the notion of “algorithm”
  • All reasonable computational models are equivalent
  • Some problems are fundamentally uncomputable

Note: This is a thesis, not a theorem (cannot be formally proven)

Decidability

Definition

A language is decidable if there exists a Turing machine that:

  • Accepts all strings in the language
  • Rejects all strings not in the language
  • Always halts

Formal Definition:

L is decidable if there exists a TM M such that:
- M halts on all inputs
- M accepts w iff w ∈ L

Examples of Decidable Languages

Regular Languages:

L = {a*b*}
Decidable (finite automaton always halts)

Context-Free Languages:

L = {aⁿbⁿ | n ≥ 0}
Decidable (CYK algorithm always halts)

Arithmetic:

L = {n | n is prime}
Decidable (primality testing algorithms exist)

Semi-Decidability

Definition

A language is semi-decidable if there exists a Turing machine that:

  • Accepts all strings in the language
  • May loop forever on strings not in the language

Formal Definition:

L is semi-decidable if there exists a TM M such that:
- M accepts w iff w ∈ L
- M may loop on w if w ∉ L

Examples of Semi-Decidable Languages

Halting Problem:

L = {M, w | Turing machine M halts on input w}
Semi-decidable (can simulate M, but may loop)

Satisfiability:

L = {φ | φ is satisfiable}
Semi-decidable (can verify solutions)

Undecidability

Definition

A language is undecidable if no Turing machine can decide it.

Formal Definition:

L is undecidable if there is no TM M such that:
- M halts on all inputs
- M accepts w iff w ∈ L

The Halting Problem

Definition: Given a Turing machine M and input w, does M halt on w?

Formal Language:

HALT = {M, w | Turing machine M halts on input w}

Proof of Undecidability

Theorem: The halting problem is undecidable.

Proof by Contradiction:

Assume H is a TM that decides HALT.
H(M, w) = accept if M halts on w
H(M, w) = reject if M loops on w

Construct TM D:
D(M) = if H(M, M) accepts then loop forever
       if H(M, M) rejects then halt

Now consider D(D):
Case 1: H(D, D) accepts
  → D halts on D
  → D loops forever (contradiction)

Case 2: H(D, D) rejects
  → D loops on D
  → D halts (contradiction)

Therefore, H cannot exist.

Other Undecidable Problems

Post Correspondence Problem:

Given sequences of strings, can we find a sequence of indices
that produces the same string when concatenated?
Undecidable

Tiling Problem:

Given a set of tiles, can we tile the infinite plane?
Undecidable

Equivalence of Context-Free Grammars:

Given two CFGs, do they generate the same language?
Undecidable

Reduction

Definition

A reduction from problem A to problem B shows that if B is decidable, then A is decidable.

Notation:

A ≤ B (A reduces to B)

Proof by Reduction

To prove a problem is undecidable:

  1. Assume it is decidable
  2. Show how to use it to solve a known undecidable problem
  3. Derive a contradiction

Example: Proving Undecidability

Problem: Does a Turing machine M accept the empty string?

Proof:

Assume EMPTY = {M | M accepts ε} is decidable.
Use it to solve HALT:

Given M and w:
1. Construct M' that:
   - Ignores input
   - Simulates M on w
   - Accepts if M halts
2. Check if M' accepts ε using EMPTY decider
3. M halts on w iff M' accepts ε

This would solve HALT, which is undecidable.
Therefore, EMPTY is undecidable.

Complexity Classes

P (Polynomial Time)

Languages decidable by deterministic TM in polynomial time.

Examples:

Sorting: O(n log n)
Searching: O(n)
Graph connectivity: O(n²)

NP (Non-Deterministic Polynomial Time)

Languages decidable by non-deterministic TM in polynomial time.

Examples:

SAT: Boolean satisfiability
TSP: Traveling salesman problem
Knapsack: Knapsack problem

P vs NP

Open Question: Is P = NP?

Significance:

  • One of the Millennium Prize Problems
  • $1 million prize for solution
  • Fundamental to computer science

Implications:

  • If P = NP: Many hard problems become easy
  • If P ≠ NP: Cryptography is secure

Glossary

  • Computable: Function that can be computed by algorithm
  • Decidable: Language that can be decided by TM
  • Semi-decidable: Language that can be recognized by TM
  • Undecidable: Language that cannot be decided
  • Halting problem: Undecidable problem about TM termination
  • Reduction: Showing one problem reduces to another
  • Church-Turing thesis: Equivalence of computation models
  • P: Polynomial-time decidable languages
  • NP: Non-deterministic polynomial-time languages
  • NP-complete: Hardest problems in NP

Practice Problems

Problem 1: Decidability

Is the language {aⁿbⁿ | n ≥ 0} decidable? Why?

Solution:

Yes. The CYK algorithm can decide this language in O(n³) time.
It always halts and correctly accepts/rejects.

Problem 2: Undecidability

Prove that the language {M | M accepts at least one string} is undecidable.

Solution:

Assume NONEMPTY = {M | L(M) ≠ ∅} is decidable.
Use it to solve HALT:

Given M and w:
1. Construct M' that:
   - Ignores input
   - Simulates M on w
   - Accepts if M halts
2. Check if M' accepts something using NONEMPTY decider
3. M halts on w iff L(M') ≠ ∅

This would solve HALT, which is undecidable.
Therefore, NONEMPTY is undecidable.

Problem 3: Complexity

Is SAT in P or NP? Why?

Solution:

SAT is in NP (can verify solutions in polynomial time).
Unknown if SAT is in P (this is the P vs NP question).
SAT is NP-complete (hardest problem in NP).

Problem 4: Reduction

Show that if HALT were decidable, we could solve the equivalence problem for TMs.

Solution:

Given TMs M1 and M2:
1. Construct M that accepts w iff M1 and M2 differ on w
2. Use HALT decider to check if M halts
3. If M halts, we can determine equivalence
4. But HALT is undecidable, so this doesn't work

Online Platforms

Interactive Tools

  • “Introduction to Automata Theory, Languages, and Computation” by Hopcroft, Motwani, Ullman
  • “Theory of Computation” by Sipser
  • “Elements of the Theory of Computation” by Lewis & Papadimitriou
  • “Computability and Complexity” by Papadimitriou
  • “Gödel, Escher, Bach” by Hofstadter - Accessible introduction

Academic Journals

Software Tools

Conclusion

Computability and decidability theory reveals fundamental limits:

  • Computable functions can be computed by algorithms
  • Decidable languages can be decided by Turing machines
  • Undecidable problems exist and cannot be solved
  • Reductions prove undecidability
  • Complexity classes organize problems by difficulty

Understanding these concepts is essential for theoretical computer science and recognizing the limits of computation.

In the next article, we’ll explore complexity classes and NP-completeness in more depth.

Next Article: Complexity Classes and NP-Completeness

Previous Article: Turing Machines: Computation Model

Comments