10.5 Equivalence of Models
Detailed equivalence proofs between Turing machines, recursive functions, and lambda calculus, with explicit constructions and simulations.
Tag
Turing Machines
8 notes
12.1 Reducibility
Formal methods for comparing decision problems using many-one and Turing reducibility.
11.3 Universal Machines
Machines that simulate any other Turing machine, establishing the concept of programmable computation.
11.2 Computation Traces
Step-by-step evolution of Turing machine configurations and how computations are represented as traces.
11.1 Machine Definitions
Formal definition of Turing machines, including states, tape, alphabets, and transition functions.
Chapter 11. Turing Machines
Turing machine definitions, computation traces, universal machines, the halting problem, and undecidability results.
10.4 Formal Models of Computation
Turing machines, register machines, lambda calculus, recursive functions, and the precise mathematical models used to define computation.
10.3 Church Turing Thesis
The Church Turing thesis, formal models of computation, equivalence of models, and the distinction between mathematical theorem and foundational principle.