Mathematical logic and foundations Computability theory Concept
Computable function
Summary
A computable function is a function on the natural numbers whose values can be calculated by an algorithm. Formally, it is a partial function computed by a Turing machine, and this class equals the class of partial general recursive functions. Computable functions are the central objects of computability theory. Some functions, such as the one that tells whether a program halts, are well defined but not computable.
Where this leads
20 pages build on this one.
- Kolmogorov complexity
- Evans's theorem on word problems
- Realizability
- Ordinal analysis
- Gödel numbering
- Word problem for an algebra
- Ackermann function is not primitive recursive
- Tarski's finite basis problem
- Rice's theorem
- Word problem for free algebras of a variety
- Proof-theoretic ordinal
- Computable set
- Realizability
- Kleene's recursion theorem
- Many-one reduction
- McKenzie's undecidability of the finite basis problem
- Computably enumerable set
- Tennenbaum's theorem
- Priority method
- Smn theorem
Further reading
About this page
| Tag | KZSB5E471K |
|---|---|
| URI | m2://KZSB5E471K |
| Kind | concept |
| Writing | W0 stub |
| MSC | 03D20, 03D10 |
| Specializes | Function |
| Same as |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Used by
- Kolmogorov complexity
- Realizability
- Gödel numbering
- Word problem for an algebra
- Ackermann function is not primitive recursive
- Tarski's finite basis problem
- Rice's theorem
- Word problem for free algebras of a variety
- Proof-theoretic ordinal
- Computable set
- Realizability
- Kleene's recursion theorem
- Many-one reduction
- Computably enumerable set
- Tennenbaum's theorem
- Priority method
- Smn theorem