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

Supplemental resources (the following are optional, but you may find them useful)

-Paid-

See also

-No Additional Notes-