go-v.orgcodex
Menu
Page tools

codex · Philosophy

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(22n)). 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 ℰ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:

𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸=⋃k∈ℕDTIME(expk(nc)) where expk(n) denotes a k-level exponential tower (e.g., 22⋅⋅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.

Wikipedia contributors, "Elementary recursive function", Wikipedia, revision 1369784560, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex