Computability

Builds on

Required prerequisites, all the way down: 21

You will learn to

• Design simple Turing machines and simulate them.
• Prove that the halting problem is undecidable by a diagonal argument.
• Use reductions to prove undecidability, and state Rice's theorem.

Definition

• A Turing machine is a finite-state machine with an unbounded tape that it can read, write and move along.
• A set is decidable if some algorithm always halts and correctly decides membership, and recursively enumerable if some algorithm halts exactly on its members.
• The Church–Turing thesis states that every effectively computable function is computable by a Turing machine.

Theorem

• The halting problem is undecidable (Turing, 1936).
• A set is decidable if and only if both it and its complement are recursively enumerable.
• Rice's theorem: every non-trivial property of the functions computed by programs is undecidable.
• There are only countably many Turing machines, so most functions ℕ → ℕ are not computable.

Common misconceptions

• Treating the Church–Turing thesis as a theorem; it concerns the informal notion of effective computability and is supported by the equivalence of many models.
• Thinking undecidability means no instance can be solved; it means no single algorithm solves every instance.

Leads to

Optional discoveries

• The λ-calculus Church's λ-calculus computes exactly the same functions as Turing machines.
• ← Repetition and decisions
• ← First-order logic

Learning pathways

• Computer science and formal methods

Further reading

• Michael Sipser, Introduction to the Theory of Computation (1996)
• George S. Boolos, John P. Burgess and Richard C. Jeffrey, Computability and Logic