10.5 Equivalence of Models
Detailed equivalence proofs between Turing machines, recursive functions, and lambda calculus, with explicit constructions and simulations.
Tag
Computability
17 notes
10.2 Partial vs Total Functions
Distinction between partial and total computable functions, undefined values, domains of definition, and the role of nontermination.
10.1 Recursive Functions
Primitive recursive functions, general recursive functions, minimization, and the formal construction of computable numerical functions.
14.5 Extensions and Refinements
Stronger forms of incompleteness, Rosser’s improvement, Löb’s theorem, and connections to computability.
12.5 Structure of Degrees
Global properties of the Turing degrees including incomparability, density, and jump structure.
12.4 Post’s Problem
Existence of intermediate degrees between computable sets and the halting problem.
12.3 Recursively Enumerable Sets
Sets that can be enumerated by algorithms and their role in semi-decidability and computability theory.
12.2 Turing Degrees
Equivalence classes of sets under Turing reducibility and the ordering of computational power.
12.1 Reducibility
Formal methods for comparing decision problems using many-one and Turing reducibility.
Chapter 12. Degrees of Unsolvability
Reducibility, Turing degrees, recursively enumerable sets, Post's problem, and the structure of degrees.
11.5 Undecidability Results
Extensions of undecidability using reductions and general results such as Rice’s theorem.
11.4 Halting Problem
The undecidable problem of determining whether a Turing machine halts on a given input.
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.
Chapter 10. Computable Functions
Recursive functions, partial and total functions, the Church-Turing thesis, formal models of computation, and equivalence of models.
03. Logic and Foundations
Formal logic, set theory, computability, and the foundations of mathematics treated as a formal system.