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.
-this concept has no prerequisites-
- 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)
→ Stanford Encyclopedia of Philosophy
A philosophy reference.
Supplemental resources (the following are optional, but you may find them useful)
→ 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
- The parts concerning computability (starting with Theorem 5.5) are optional, and depend on Sections 6.3-6.4
-No Additional Notes-
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation