> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/600-toc/630-computability-theory/computable-function.md).

# Computable function

<https://en.wikipedia.org/wiki/Computable\\_function>

Computable functions are the formalized analogue of algorithms, such that a function is computable if it can be implemented as an algorithm.

Particular models of computability that give rise to the set of computable functions are the *Turing-computable functions* and the *μ-recursive functions*.

According to the *Church-Turing thesis*, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space.

Equivalently, this thesis states that a function is computable iff it has an algorithm, which here means a sequence of steps that a person with unlimited amount of time on their hands, paper and pencils, could follow.