10.5 Equivalence of Models
Detailed equivalence proofs between Turing machines, recursive functions, and lambda calculus, with explicit constructions and simulations.
4 notes
Detailed equivalence proofs between Turing machines, recursive functions, and lambda calculus, with explicit constructions and simulations.
Primitive recursive functions, general recursive functions, minimization, and the formal construction of computable numerical functions.
The Church Turing thesis, formal models of computation, equivalence of models, and the distinction between mathematical theorem and foundational principle.
Recursive functions, partial and total functions, the Church-Turing thesis, formal models of computation, and equivalence of models.