Elementary recursive function

From Wikipedia, the free encyclopedia

The term elementary was originally introduced by László Kalmár in the context of computability theory.^{[1] [2]} 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, ${\displaystyle O(2^{2^{n}})}${\displaystyle O(2^{2^{n}})}). Not all primitive recursive functions are elementary; for example, tetration grows too rapidly to be included in the elementary class.

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:

${\displaystyle {\mathsf {ELEMENTARY}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}(\exp ^{k}(n^{c}))}${\displaystyle {\mathsf {ELEMENTARY}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}(\exp ^{k}(n^{c}))}

where ${\displaystyle \exp ^{k}(n)}${\displaystyle \exp ^{k}(n)} denotes a k-level exponential tower (e.g., ${\displaystyle 2^{2^{\cdot ^{\cdot ^{n}}}}}${\displaystyle 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.

The definitions of elementary recursive functions are the same as for primitive recursive functions, except that primitive recursion is replaced by bounded summation and bounded product. All functions work over the natural numbers. The basic functions, all of them elementary recursive, are:

1. Zero function. Returns zero: ${\displaystyle f(x)=0}${\displaystyle f(x)=0}.
2. Successor function: ${\displaystyle f(x)=x+1}${\displaystyle f(x)=x+1}. Often this is denoted by ${\displaystyle S}${\displaystyle S}, as in ${\displaystyle S(x)}${\displaystyle S(x)}. Via repeated application of a successor function, one can achieve addition.
3. Projection functions: these are used for ignoring arguments. For example, ${\displaystyle f(a,b)=a}${\displaystyle f(a,b)=a} is a projection function.
4. Subtraction function: ${\displaystyle f(x,y)=x-y}${\displaystyle f(x,y)=x-y} if ${\displaystyle y<x}${\displaystyle y<x}, or 0 if ${\displaystyle y\geq x}${\displaystyle y\geq x}. This function is used to define conditionals and iteration.

From these basic functions, we can build other elementary recursive functions.

1. Composition: applying values from some elementary recursive function as an argument to another elementary recursive function. The function ${\displaystyle f}${\displaystyle f} defined as the composition ${\displaystyle f(x_{1},\ldots ,x_{n})=h{\bigl (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}){\bigr )}}${\displaystyle f(x_{1},\ldots ,x_{n})=h{\bigl (}g_{1}(x_{1},\ldots ,x_{n}),\ldots ,g_{m}(x_{1},\ldots ,x_{n}){\bigr )}} is elementary recursive if ${\displaystyle h}${\displaystyle h} is elementary recursive and each ${\displaystyle g_{i}}${\displaystyle g_{i}} is elementary recursive.
2. Bounded summation: ${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}${\displaystyle f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})} is elementary recursive if ${\displaystyle g}${\displaystyle g} is elementary recursive.
3. Bounded product: ${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})}${\displaystyle f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})} is elementary recursive if ${\displaystyle g}${\displaystyle g} is elementary recursive.

In the context of computability theory, superposition is a method of constructing new functions from existing ones by functional composition. It allows the outputs of one or more functions to serve as the inputs to another function.

More formally, suppose:

• ${\displaystyle f(x_{1},\dots ,x_{k})}${\displaystyle f(x_{1},\dots ,x_{k})} is a ${\displaystyle k}${\displaystyle k}-ary function, and
• ${\displaystyle g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n})}${\displaystyle g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n})} are ${\displaystyle n}${\displaystyle n}-ary functions.

Then the superposition of these functions yields a new ${\displaystyle n}${\displaystyle n}-ary function:

${\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n}))}${\displaystyle h(x_{1},\dots ,x_{n})=f(g_{1}(x_{1},\dots ,x_{n}),\dots ,g_{k}(x_{1},\dots ,x_{n}))}.

The class of elementary recursive functions coincides with the closure under superposition of the projection functions and one of the following sets of initial functions:

• ${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;2^{n}\}}${\displaystyle \{n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;2^{n}\}}^[3]
• ${\displaystyle \{1,\;n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;n\times m,\;n^{m}\}}${\displaystyle \{1,\;n+m,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;n\times m,\;n^{m}\}}^[4]
• ${\displaystyle \{n+1,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;n^{m}\}}${\displaystyle \{n+1,\;n\mathbin {\dot {-}} m,\;\lfloor n/m\rfloor ,\;n^{m}\}}^{[citation needed ]}
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;n^{2},\;2^{n}\}}${\displaystyle \{n+m,\;n{\bmod {m}},\;n^{2},\;2^{n}\}}^[5]
• ${\displaystyle \{n+m,\;n{\bmod {m}},\;2^{n}\}}${\displaystyle \{n+m,\;n{\bmod {m}},\;2^{n}\}}^[6]

where ${\displaystyle n\mathbin {\dot {-}} m=\max(n-m,0)}${\displaystyle n\mathbin {\dot {-}} m=\max(n-m,0)} denotes truncated subtraction (monus).

In 2025 Mihai Prunescu, Lorenzo Sauras-Altuzarra and Joseph M. Shunia proved that the class of Kalmár elementary functions can be inductively generated from the addition (${\displaystyle n+m}${\displaystyle n+m}), the integer remainder (${\displaystyle n{\bmod {m}}}${\displaystyle n{\bmod {m}}}) and the base-two exponentiation (${\displaystyle 2^{n}}${\displaystyle 2^{n}}), improving previous results by Marchenkov^[5] and Mazzanti.^[4] In addition, they further proved that the substitution basis defined by these three operations is minimal.^[7]

Example 1

Let

${\displaystyle f(a,b)=a{\bmod {b}},\;g_{1}(n)=2^{n+n}}${\displaystyle f(a,b)=a{\bmod {b}},\;g_{1}(n)=2^{n+n}}, and ${\displaystyle g_{2}(n)=2^{n}+n}${\displaystyle g_{2}(n)=2^{n}+n}.

Then the function

${\displaystyle h(n)=f(g_{1}(n),g_{2}(n))=2^{n+n}{\bmod {(}}2^{n}+n)}${\displaystyle h(n)=f(g_{1}(n),g_{2}(n))=2^{n+n}{\bmod {(}}2^{n}+n)}

defines the square function ${\displaystyle h(n)=n^{2}}${\displaystyle h(n)=n^{2}} by superposition alone.

This shows how functions like squaring can be expressed using only addition, exponentiation, and modulo through superposition, without requiring explicit recursion.

Example 2

${\displaystyle x\mathbin {\dot {-}} y=((2^{x+y}+x){\bmod {(}}2^{x+y}+y)){\bmod {(}}2^{x+y}+x)}${\displaystyle x\mathbin {\dot {-}} y=((2^{x+y}+x){\bmod {(}}2^{x+y}+y)){\bmod {(}}2^{x+y}+x)}.^[8]

Example 3

${\displaystyle x^{y}=2^{(xy+x+1)y}{\bmod {(}}2^{xy+x+1}\mathbin {\dot {-}} x)}${\displaystyle x^{y}=2^{(xy+x+1)y}{\bmod {(}}2^{xy+x+1}\mathbin {\dot {-}} x)}.^[9]

Lower elementary recursive functions follow the definitions as above, except that bounded product is disallowed. That is, a lower elementary recursive function must be a zero, successor, or projection function, a composition of other lower elementary recursive functions, or the bounded sum of another lower elementary recursive function.

Lower elementary recursive functions are also known as Skolem elementary functions.^{[10] [11]}

Whereas elementary recursive functions have potentially more than exponential growth, the lower elementary recursive functions have polynomial growth.

The class of lower elementary functions has a description in terms of composition of simple functions analogous to that we have for elementary functions.^{[11] [12]} Namely, a polynomial-bounded function is lower elementary if and only if it can be expressed using a composition of the following functions: projections, ${\displaystyle n+1}${\displaystyle n+1}, ${\displaystyle nm}${\displaystyle nm}, ${\displaystyle n\mathbin {\dot {-}} m}${\displaystyle n\mathbin {\dot {-}} m}, ${\displaystyle n\wedge m}${\displaystyle n\wedge m}, ${\displaystyle \lfloor n/m\rfloor }${\displaystyle \lfloor n/m\rfloor }, one exponential function (${\displaystyle 2^{n}}${\displaystyle 2^{n}} or ${\displaystyle n^{m}}${\displaystyle n^{m}}) with the following restriction on the structure of formulas: the formula can have no more than two floors with respect to an exponent (for example, ${\displaystyle xy(z+1)}${\displaystyle xy(z+1)} has 1 floor, ${\displaystyle (x+y)^{yz+x}+z^{x+1}}${\displaystyle (x+y)^{yz+x}+z^{x+1}} has 2 floors, ${\displaystyle 2^{2^{x}}}${\displaystyle 2^{2^{x}}} has 3 floors). Here ${\displaystyle n\wedge m}${\displaystyle n\wedge m} is a bitwise AND of n and m.

• ELEMENTARY
• Elementary function arithmetic
• Primitive recursive function
• Grzegorczyk hierarchy
• EXPTIME

• Kalmár, László (1943). "Egyszerű példa eldönthetetlen aritmetikai problémára" [Ein einfaches Beispiel für ein unentscheidbares arithmetisches Problem]. Matematikai és Fizikai Lapok (in Hungarian). 50. Budapest: 1–23. Hungarian with German abstract.

• Kleene, Stephen Cole (1952). Introduction to Metamathematics. New York: Van Nostrand. OCLC 523942., reprint. Ishi Press. 13 March 2009 [1952]. ISBN 9780923891572.

• Marchenkov, S. S. (1980). "A Superposition Basis in the Class of Kalmar Elementary Functions". Mathematical Notes of the Academy of Sciences of the USSR . 27 (3): 161–166. doi:10.1007/BF01140159. ISSN 0001-4346.

• Marchenkov, S. S. (September 2007). "Superpositions of Elementary Arithmetic Functions". Journal of Applied and Industrial Mathematics. 1 (3): 351–360. doi:10.1134/S1990478907030106. ISSN 1990-4789.

• Mazzanti, Stefano (2002). "Plain Bases for Classes of Primitive Recursive Functions". Mathematical Logic Quarterly. 48 (1): 93–104. doi:10.1002/1521-3870(200201)48:1<93::AID-MALQ93>3.0.CO;2-8. ISSN 0942-5616. OCLC 5154649764.

• Prunescu, Mihai; Sauras-Altuzarra, Lorenzo (5 June 2025). "On the representation of C-recursive integer sequences by arithmetic terms". arXiv:2405.04083 [math.LO].

• Prunescu, Mihai; Sauras-Altuzarra, Lorenzo; Shunia, Joseph M. (8 August 2025). "A Minimal Substitution Basis for the Kalmar Elementary Functions". arXiv:2505.23787 [math.LO].

• Rose, H. E. (1984). Subrecursion: Functions and Hierarchies. Oxford University Press. ISBN 0-19-853189-3.

• Skolem, Th. (1962). "Proof of some theorems on recursively enumerable sets". Notre Dame Journal of Formal Logic . 3 (2): 65–74. doi:10.1305/ndjfl/1093957149.

• Volkov, S. A. (2010). "On the class of Skolem elementary functions". Journal of Applied and Industrial Mathematics. 4 (4): 588–599. doi:10.1134/S1990478910040149.

• Volkov, Sergey (2016). "Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions [dissertation]". arXiv:1611.04843 [cs.CC].

• Lysikov, Vladimir (7 September 2025). "Can superposition alone generate the Kalmár elementary function x^y from ⟨x+y, x mod y, 2^x⟩?". Math Stack Exchange. Retrieved 8 September 2025.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Elementary_recursive_function&oldid=1320272935"

Categories:

• Complexity classes
• Computability theory

Hidden categories:

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from July 2025
• All articles with unsourced statements
• Articles with unsourced statements from July 2025
• CS1 Hungarian-language sources (hu)