Turing Machines and Decidability
Stub. The Turing machine as the formal model behind the Church-Turing thesis (that it captures everything "algorithm" could reasonably mean), its variants (multitape, nondeterministic, enumerators) all turning out equally powerful, and decidability: which languages a Turing machine can always halt and correctly decide, versus the diagonalization argument that produces an undecidable (and even Turing-unrecognizable) language.
Corresponds to Sipser, Chapters 3–4 (opening Part Two: Computability Theory). A Turing machine adds unbounded, freely-rewritable memory to the finite automaton — the model that turns out to be exactly as powerful as every other reasonable notion of “algorithm” anyone has proposed (multitape machines, nondeterministic machines, enumerators, lambda calculus, …), which is the empirical claim behind the Church-Turing thesis rather than a theorem (there’s no way to formally capture “every possible notion of algorithm” to prove it against). See kolmogorov-complexity for a specific, consequential use of this same machine model. Decidability asks which languages have a Turing machine that always halts and gives the correct yes/no answer; the diagonalization method — build a language defined precisely to differ from every machine on some input, by looking at each machine’s behavior on its own encoding — is the key proof technique, producing both a concrete undecidable language and one that isn’t even Turing-recognizable (no machine can even recognize its “yes” instances).
Outline (TODO — flesh out each)
- Turing machines — formal definition, examples
- Variants of Turing machines — multitape, nondeterministic, enumerators
- Equivalence of the variants
- The definition of algorithm — Hilbert’s problems, the Church-Turing thesis
- Decidable languages — regular and context-free language problems
- The diagonalization method
- An undecidable language
- A Turing-unrecognizable language