Lesson plan
Elementary recursive function
The term elementary was originally introduced by László Kalmár in the context of computability theory. He defined the class of elementary recursive functions ("Kalmár elementary functions") as a subset of the primitive recursive functions — specifically, those that can be computed using a limited set of operations such as composition, bounded sums, and bounded products. These functions grow no faster than a fixed-height tower of exponentiation (for example, O(2^{2^n}) ). Not all primitive recursive functions are elementary; for example, tetration grows too rapidly to be included in the elementary class. The elementary recursive functions correspond to the class \mathcal{E}^3 of the Grzegorczyk hierarchy. In computational complexity theory, the term ELEMENTARY refers to a class of decision problems solvable in elementary time — that is, within time bounded by some fixed number of exponentials. Formally: : \mathsf{ELEMENTARY} = \bigcup_{k \in \mathbb{N}} \text{DTIME}(\exp^k(n^c)) :where \exp^k(n) denotes a k-level exponential tower (e.g., 2^{2^{\cdot^{\cdot^{n}}}} ). Although the name comes from the same historical origin, the ELEMENTARY complexity class deals with decision problems and Turing machine runtime, rather than total functions.
Article summary
The term elementary was originally introduced by László Kalmár in the context of computability theory. He defined the class of elementary recursive functions ("Kalmár elementary functions") as a subset of the primitive recursive functions — specifically, those that can be computed using a limited set of operations such as composition, bounded sums, and bounded products. These functions grow no faster than a fixed-height tower of exponentiation (for example, O(2^{2^n}) ). Not all primitive recursive functions are elementary; for example, tetration grows too rapidly to be included in the elementary class. The elementary recursive functions correspond to the class \mathcal{E}^3 of the Grzegorczyk hierarchy. In computational complexity theory, the term ELEMENTARY refers to a class of decision problems solvable in elementary time — that is, within time bounded by some fixed number of exponentials. Formally: : \mathsf{ELEMENTARY} = \bigcup_{k \in \mathbb{N}} \text{DTIME}(\exp^k(n^c)) :where \exp^k(n) denotes a k-level exponential tower (e.g., 2^{2^{\cdot^{\cdot^{n}}}} ). Although the name comes from the same historical origin, the ELEMENTARY complexity class deals with decision problems and Turing machine runtime, rather than total functions.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.