Mathematics.

computability

Computability and Decidability

Theory of Computation40 minDifficulty7 out of 10

You should know: turing machines

Overview

A problem is decidable if some Turing machine can always determine the correct yes/no answer and halt. Not every well-defined problem is decidable — the most famous example, the halting problem (does a given program halt on a given input?), was proven undecidable by Turing in 1936. Computability theory studies exactly which problems can, in principle, ever be solved by any algorithm at all, regardless of how much time or memory is available.

Intuition

It's tempting to think 'given enough time, a computer can solve anything.' Computability theory proves this is false — there are precisely-stated, simple-to-describe problems (like 'will this program eventually stop?') for which NO algorithm, however clever or however much time it's given, can always give the correct answer. This is a hard mathematical limit, not a limit of current technology.

Formal Definition

Definition

Key definitions distinguishing degrees of computability:

L is decidable  ⟺  ∃ Turing machine M that halts on every input and correctly accepts/rejectsL \text{ is decidable} \iff \exists \text{ Turing machine } M \text{ that halts on every input and correctly accepts/rejects}
Decidable
L is recognizable (semi-decidable)  ⟺  ∃ M that halts and accepts on every w∈L, but may loop forever on w∉LL \text{ is recognizable (semi-decidable)} \iff \exists\, M \text{ that halts and accepts on every } w \in L, \text{ but may loop forever on } w \notin L
Recognizable

Derivation

Sketch of Turing's proof that the halting problem is undecidable, by diagonalization/contradiction:

Assume a machine H decides HALT(M,w):accepts if M halts on w, rejects otherwise\text{Assume a machine } H \text{ decides HALT}(M, w): \text{accepts if } M \text{ halts on } w, \text{ rejects otherwise}
Build D(M): run H(M,M); if it says ’halts’, loop forever; if it says ’loops’, halt.\text{Build } D(M): \text{ run } H(M, M); \text{ if it says 'halts', loop forever; if it says 'loops', halt.}
Run D(D): if D halts on itself, H says it loops (contradiction); if it loops, H says it halts (contradiction).\text{Run } D(D): \text{ if } D \text{ halts on itself, } H \text{ says it loops (contradiction); if it loops, } H \text{ says it halts (contradiction).}
∴ no such H can exist, so the halting problem is undecidable\therefore \text{ no such } H \text{ can exist, so the halting problem is undecidable}

Theorems

Theorem 1: Undecidability of the Halting Problem
There is no Turing machine that decides, for every program M and input w, whether M halts on w.\text{There is no Turing machine that decides, for every program } M \text{ and input } w, \text{ whether } M \text{ halts on } w.
Theorem 2: Rice's theorem
Every non-trivial semantic property of a program’s behavior (e.g. ’does it always output 0?’) is undecidable.\text{Every non-trivial semantic property of a program's behavior (e.g. 'does it always output 0?') is undecidable.}

Applications

Rice's theorem implies no general-purpose tool can perfectly detect all bugs, viruses, or infinite loops in arbitrary programs — a hard theoretical ceiling on static analysis tools.

Worked Examples

  1. This is a non-trivial semantic property of program behavior, so Rice's theorem applies directly.

    By Rice’s theorem, this is undecidable.\text{By Rice's theorem, this is undecidable.}

Answer: No — undecidable by Rice's theorem

Practice Problems

Difficulty 7/10

Explain, in one sentence, why the halting problem being undecidable does not mean 'we can never tell if any specific program halts.'

Difficulty 6/10

Rice's theorem says any non-trivial semantic property of a program's behaviour is undecidable. Why does this doom the dream of a perfect antivirus that decides 'is this program malicious?' for all inputs?

Difficulty 5/10

Which of these problems IS decidable (an algorithm always gives the right yes/no answer and halts)?

Difficulty 7/10

In practice, how do computer scientists PROVE a new problem is undecidable without re-running Turing's diagonal argument each time?

Common Mistakes

Common Mistake

Believing undecidability means 'we haven't found the algorithm yet, but might in the future.'

Undecidability is a proven mathematical impossibility (via diagonalization), not a current technological limitation — no future hardware or cleverness can change it.

Quiz

A perfect general 'is this program malicious?' detector is impossible mainly because of:
The usual way to prove a new problem undecidable is to:
Undecidable means:

Summary

  • A problem is decidable if some Turing machine always halts with the correct answer.
  • The halting problem is the canonical undecidable problem, proven via a diagonalization argument.
  • Rice's theorem generalizes this: virtually every non-trivial question about a program's behavior is undecidable.
  • This sets a hard theoretical limit on what any bug-finder, virus-scanner, or perfect optimizer can guarantee.

References

  1. WebsiteWikipedia — Computability theory