Theory of Computation · topic
Turing machine definition and configurations, a decider for a^n b^n, equivalent variants (multitape, nondeterministic, two-way, enumerators), recursive versus recursively enumerable languages, linear-bounded automata and CSLs, the Chomsky hierarchy and the closure master table.
A Turing machine (TM) is a finite-state controller with a doubly infinite (or one-way infinite) tape and a read/write head. It is the standard model of general-purpose computation.) languages; languages decided by TMs that always halt are the recursive (decidable) languages.
The Chomsky hierarchy organizes grammars and their languages into four classical types: regular (Type-3), context-free (Type-2), context-sensitive (Type-1), and unrestricted (Type-0). Matching machine models are finite automata, PDAs, linear bounded automata (LBAs), and Turing machines.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
