title: "Lecture 9 - Turing Machines and the Church-Turing Thesis"
unit: 2
lecture: 9

Lecture 9 - Turing Machines and the Church-Turing Thesis

(Skeleton for Fall 2026.)

The Turing Machine

TODO: formal definition; configurations; accept, reject, loop; contrast with DFA/PDA (unbounded rewritable tape).

Variants

TODO: multitape, nondeterministic, enumerators; all equivalent in power (proof sketches); robustness as evidence the definition is right.

The Church-Turing Thesis

TODO: thesis, not theorem; historical context (Turing, Church, lambda calculus); what would refute it; modern framings.

Describing Turing Machines

TODO: levels of description (formal, implementation, high-level); the notation contract for the rest of the course.