Elementary recursive function

In recursion theory, an elementary recursive function, also called an elementary function, or a Kalmár elementary function, is a restricted form of a primitive recursive function, allowing bounded applications of exponentiation (for example, ).

The name was coined by László Kalmár, in the context of recursive functions and undecidability; most elementary recursive functions are far from elementary. Not all primitive recursive problems are elementary; for example, tetration is not elementary. The corresponding class of decision problems is denoted .