10.5 Equivalence of Models
Detailed equivalence proofs between Turing machines, recursive functions, and lambda calculus, with explicit constructions and simulations.
Tag
Recursive Functions
4 notes
10.1 Recursive Functions
Primitive recursive functions, general recursive functions, minimization, and the formal construction of computable numerical functions.
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.
Chapter 10. Computable Functions
Recursive functions, partial and total functions, the Church-Turing thesis, formal models of computation, and equivalence of models.