recursive functions
Summary
Recursive functions are a kind of mathematical function which, if the Church-Turing hypothesis is correct, correspond to functions which can be computed algorithmically. A subclass knows as primitive recursive functions consists of functions computable by programs where a bound on the number of steps can be calculated in advance. Recursive functions are useful for formalizing notions of computability, because the notion of a recursive function is more precise than that of an algorithm.
Context
-this concept has no prerequisites-
Goals
- Define the set of primitive recursive functions
- Be able to show that simple functions are primitive recursive
- Know what the minimization operator is and what additional power it adds
- Know why definitions in terms of minimization can give only partial, not total, functions
Core resources (read/watch one of the following)
-Free-
→ Stanford Encyclopedia of Philosophy
A philosophy reference.
Supplemental resources (the following are optional, but you may find them useful)
-Paid-
→ A Course in Mathematical Logic
A graduate textbook in mathematical logic.
- Section 6.5, "Recursive functionals and functions," pages 239-247
- Section 6.6, "A stockpile of examples," pages 247-256
Other notes:
- The parts concerning computability (starting with Theorem 5.5) are optional, and depend on Sections 6.3-6.4
See also
-No Additional Notes-