# 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-