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.

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. ==Definition== 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: Zero function. Returns zero: f(x)=0 . Successor function: f(x)=x+1 . Often this is denoted by S , as in S(x) . Via repeated application of a successor function, one can achieve addition. Projection functions: these are used for ignoring arguments. For example, f(a,b)=a is a projection function. Subtraction function: f(x,y) = \max(x-y, 0) . This function is used to define conditionals and iteration. From these basic functions, we can build other elementary recursive functions. Composition: applying values from some elementary recursive function as an argument to another elementary recursive function. The function f defined as the composition 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 h is elementary recursive and each g_i is elementary recursive. Bounded summation: f(m, x_1, \ldots, x_n) = \sum\limits_{i=0}^mg(i, x_1, \ldots, x_n) is elementary recursive if g is elementary recursive. Bounded product: f(m, x_1, \ldots, x_n) = \prod\limits_{i=0}^mg(i, x_1, \ldots, x_n) is elementary recursive if g is elementary recursive. 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: \{ n + m,\; n \mathbin{\dot{-}} m,\; \lfloor n/m \rfloor,\; 2^n \} \{ n+m,\; n \mathbin{\dot{-}} m, \; \lfloor n/m \rfloor, \; nm, \; n^m \} \{ n + m,\; n \bmod m,\; n^2,\; 2^n \} \{ n + m,\; n \bmod m,\; 2^n \} where n \mathbin{\dot{-}} m = \max (n - m, 0) denotes truncated subtraction (monus). Mihai Prunescu, Lorenzo Sauras-Altuzarra and Joseph M. Shunia proved that the class of Kalmár elementary functions can be inductively generated from addition ( n + m ), integer remainder ( n \bmod m ) and base-two exponentiation ( 2^n ), improving previous results by Mazzanti and Marchenkov. They further proved that the substitution basis defined by these three operations is minimal. An open question is whether \{ n+m, \; \lfloor n/m \rfloor, \; 2^n \} is an alternative basis. Example 1: Let f(a, b) = a \bmod b, \quad g_1(n) = 2^{n+n}, \quad g_2(n) = 2^n + n \, . Then the function h(n) = f(g_1(n), g_2(n)) = 2^{n+n} \bmod (2^n + n) defines the square function h(n) = n^2 by superposition alone. This shows how functions like squaring can be expressed using only addition, integer remainder, and base-two exponentiation through superposition, without requiring explicit recursion. Example 2: Another example of an elementary recursive function is the Kronecker delta \delta_{ij} = 2^{ (2^i \bmod (2^j + 1)) + (2^j \bmod (2^i + 1)) \bmod (2^i + 2^j) } \bmod 2 \, , which satisfies \delta_{ij} = 1 if i = j and 0 otherwise. Further examples x \mathbin{\dot{-}} y = ((2^{x+y} + x) \bmod (2^{x+y} + y)) \bmod (2^{x+y} + x) . 2xy = (x + y)^2 \mathbin{\dot{-}} (x^2 + y^2) . \lfloor x / y \rfloor = (2(x+1)(x\mathbin{\dot{-}}(x \bmod y ))) \bmod (2(x + 1 )y \mathbin{\dot{-}} 1) . xy = \lfloor 2xy / 2 \rfloor . x^y = 2^{(x y + x + 1)y} \bmod ( 2^{x y + x + 1} \mathbin{\dot{-}} x ) . ==Notes==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369784560 under CC BY-SA 4.0; modifications have been made.