Definition of a Turing Machine
Turing Machines as Language Accepters
Turing Machines as Transducers
9.2 Combining Turing Machines for Complicated Tasks
9.3 Turing's Thesis
10 Other Models of Turing Machines
10.1 Minor Variations on the Turing Machine Theme
Equivalence of Classes of Automata
Turing Machines with a Stay-Option
Turing Machines with Semi-Infinite Tape
The Off-Line Turing Machine
10.2 Turing Machines with More Complex Storage
Multitape Turing Machines
Multidimensional Turing Machines
10.3 Nondeterministic Turing Machines
10.4 A Universal Turing Machine
10.5 Linear Bounded Automata
11 A Hierarchy of Formal Languages and Automata
11.1 Recursive and Recursively Enumerable Languages
Languages That Are Not Recursively Enumerable
A Language That Is Not Recursively Enumerable
A Language That Is Recursively Enumerable but Not Recursive
11.2 Unrestricted Grammars
11.3 Context-Sensitive Grammars and Languages
Context-Sensitive Languages and Linear Bounded Automata
Relation Between Recursive and Context-Sensitive Languages
11.4 The Chomsky Hierarchy
12 Limits of Algorithmic Computation
12.1 Some Problems That Cannot Be Solved by Turing Machines