---
tag: RJ3MCAAZSV
kind: concept
name: Elementary recursive function
aliases: [kalmar-functions]
sources:
  - wikipedia: en:665096@r1369784560
    locator: Elementary recursive function
    note: adopted
    mention: wikipedia://en/665096
    sections: [Summary]
same_as:
  wikidata: Q5323278
  wikipedia: Elementary recursive function
inventory: [R58F0CHQTG]
---

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