title: "Lecture 10 - Decidability and Recognizability"
unit: 2
lecture: 10

Lecture 10 - Decidability and Recognizability

(Skeleton for Fall 2026.)

Deciders versus Recognizers

TODO: decidable (always halts) versus recognizable (accepts by halting, may loop on non-members); definitions to drill.

Decidable Problems About Automata

TODO: acceptance, emptiness, and equivalence for DFAs and CFGs; the universal Turing machine as a program that runs programs.

The Relationship

TODO: decidable equals recognizable and co-recognizable; setting the table for undecidability in Lecture 11.