imported>Oneequalsequalsone: Adding local short description: "Concept in computability theory", overriding Wikidata description "complexity class, algebra"

2025-11-03T19:15:09Z

Adding local short description: "Concept in computability theory", overriding Wikidata description "complexity class, algebra"

New page

{{Short description|Concept in computability theory}}
{{About| |other meanings|Elementary function}}
{{use dmy dates|date=July 2025}}
The term '''elementary''' was originally introduced by [[László Kalmár]] in the context of [[computability theory]].{{sfn|Kalmár|1943}}{{sfn|Kleene|1952|pages=285, 526}} He defined the class of '''elementary recursive functions''' (''"Kalmár elementary functions"'') as a subset of the [[primitive recursive function]]s — 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, <math>O(2^{2^n})</math>). 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:

:<math>\mathsf{ELEMENTARY} = \bigcup_{k \in \mathbb{N}} \text{DTIME}(\exp^k(n^c))</math>
:where <math>\exp^k(n)</math> denotes a ''k''-level exponential tower (e.g., <math>2^{2^{\cdot^{\cdot^{n}}}}</math>).

Although the name comes from the same historical origin, the ELEMENTARY complexity class deals with [[decision problem]]s and Turing machine runtime, rather than total functions.

==Definition==

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

# '''Zero function'''. Returns zero: <math>f(x)=0</math>.
# '''Successor function''': <math>f(x)=x+1</math>. Often this is denoted by <math>S</math>, as in <math>S(x)</math>. Via repeated application of a successor function, one can achieve addition.
# '''Projection functions''': these are used for ignoring arguments. For example, <math>f(a,b)=a</math> is a projection function.
# '''Subtraction function''': <math>f(x,y)=x-y</math> if <math>y<x</math>, or 0 if <math>y\ge x</math>. 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 <math>f</math> defined as the composition <math>f(x_1,\ldots,x_n)=h\bigl(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n)\bigr)</math> is elementary recursive if <math>h</math> is elementary recursive and each <math>g_i</math> is elementary recursive.
# '''Bounded summation''': <math>f(m, x_1, \ldots, x_n) = \sum\limits_{i=0}^mg(i, x_1, \ldots, x_n)</math> is elementary recursive if <math>g</math> is elementary recursive.
# '''Bounded product''': <math>f(m, x_1, \ldots, x_n) = \prod\limits_{i=0}^mg(i, x_1, \ldots, x_n)</math> is elementary recursive if <math>g</math> is elementary recursive.

== Superposition bases for elementary functions ==

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

More formally, suppose:

:* <math>f(x_1, \dots, x_k)</math> is a <math>k</math>-ary function, and
:* <math>g_1(x_1, \dots, x_n), \dots, g_k(x_1, \dots, x_n)</math> are <math>n</math>-ary functions.

Then the superposition of these functions yields a new <math>n</math>-ary function:

:<math>h(x_1, \dots, x_n) = f(g_1(x_1, \dots, x_n), \dots, g_k(x_1, \dots, x_n))</math>.

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:
:* <math>\{ n + m,\; n \mathbin{\dot{-}} m,\; \lfloor n/m \rfloor,\; 2^n \}</math>{{sfn|Marchenkov|1980}}
:* <math>\{ 1, \; n+m,\; n \mathbin{\dot{-}} m, \; \lfloor n/m \rfloor, \; n \times m, \; n^m \}</math>{{sfn|Mazzanti|2002}}
:* <math>\{ n + 1,\; n \mathbin{\dot{-}} m,\; \lfloor n/m \rfloor,\; n^m \}</math>{{citation needed|date=July 2025}}
:* <math>\{ n + m,\; n \bmod m,\; n^2,\; 2^n \}</math>{{sfn|Marchenkov|2007}}
:* <math>\{ n + m,\; n \bmod m,\; 2^n \}</math>{{refn|<math>n^2 = 2^{n+n} \bmod (2^n + n)</math> {{harvtxt|Prunescu|Sauras-Altuzarra|Shunia|2025}}}}
where <math>n \mathbin{\dot{-}} m = \max (n - m, 0)</math> denotes truncated subtraction ([[Monus#Natural_numbers|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 (<math>n + m</math>), the integer remainder (<math>n \bmod m</math>) and the base-two exponentiation (<math>2^n</math>), improving previous results by Marchenkov{{sfn|Marchenkov|2007}} and Mazzanti.{{sfn|Mazzanti|2002}} In addition, they further proved that the substitution basis defined by these three operations is minimal.{{sfn|Prunescu|Sauras-Altuzarra|Shunia|2025}}

'''Example 1'''

Let
:<math>f(a, b) = a \bmod b, \; g_1(n) = 2^{n+n}</math>, and <math>g_2(n) = 2^n + n</math>.
Then the function
:<math>h(n) = f(g_1(n), g_2(n)) = 2^{n+n} \bmod (2^n + n)</math>
defines the square function <math>h(n) = n^2</math> 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'''
:<math>x \mathbin{\dot{-}} y = ((2^{x+y} + x) \bmod (2^{x+y} + y)) \bmod (2^{x+y} + x)</math>.{{sfn|Prunescu|Sauras-Altuzarra|Shunia|2025|loc=Theorem 3}}

'''Example 3'''
:<math> x^y = 2^{(x y + x + 1) y} \bmod ( 2^{x y + x + 1} \mathbin{\dot{-}} x )</math>.{{sfn|Lysikov|2025}}

== Lower elementary recursive functions ==

''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.{{sfn|Skolem|1962}}{{sfn|Volkov|2010}}

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.{{sfn|Volkov|2010}}{{sfn|Volkov|2016}} Namely, a polynomial-bounded function is lower elementary if and only if it can be expressed using a composition of the following functions: projections, <math>n+1</math>, <math>nm</math>, <math>n \mathbin{\dot{-}} m</math>, <math>n\wedge m</math>, <math>\lfloor n/m \rfloor</math>, one exponential function (<math>2^n</math> or <math>n^m</math>) 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, <math>xy(z+1)</math> has 1 floor, <math>(x+y)^{yz+x}+z^{x+1}</math> has 2 floors, <math>2^{2^x}</math> has 3 floors). Here <math>n\wedge m</math> is a bitwise AND of {{mvar|n}} and {{mvar|m}}.

== See also ==
* [[ELEMENTARY]]
* [[Elementary function arithmetic]]
* [[Primitive recursive function]]
* [[Grzegorczyk hierarchy]]
* [[EXPTIME]]

==Notes==
{{reflist|2}}

== References ==

*{{cite journal
| last = Kalmár
| first = László
| author-link= László Kalmár
| title = Egyszerű példa eldönthetetlen aritmetikai problémára
| trans-title = Ein einfaches Beispiel für ein unentscheidbares arithmetisches Problem
| journal = Matematikai és Fizikai Lapok
| volume = 50
| year = 1943
| pages = 1–23
| location = Budapest
| language = hu
| url = https://real-j.mtak.hu/7300/
| quote = Hungarian with German abstract.
}}

*{{Cite book
|last=Kleene
|first=Stephen Cole
|author-link=Stephen Cole Kleene
|title=Introduction to Metamathematics
|publisher=Van Nostrand|location=New York
|year=1952
|oclc=523942
}}, {{Cite book|last=Kleene|first=Stephen Cole|author-link=Stephen Cole Kleene|display-authors=0|title=reprint|publisher= [[Ishi Press]]|orig-year=1952|date=13 March 2009|isbn=9780923891572}}

*{{cite journal
| last = Marchenkov
| first = S. S.
| title = A Superposition Basis in the Class of Kalmar Elementary Functions
| journal = [[Mathematical Notes|Mathematical Notes of the Academy of Sciences of the USSR]]
| volume = 27
| issue = 3
| pages = 161–166
| year = 1980
| issn = 0001-4346
| doi = 10.1007/BF01140159
}}

*{{cite journal
| last = Marchenkov
| first = S. S.
| title = Superpositions of Elementary Arithmetic Functions
| journal = Journal of Applied and Industrial Mathematics
| volume = 1
| issue = 3
| pages = 351–360
| date = September 2007
| issn = 1990-4789
| doi = 10.1134/S1990478907030106
}}

*{{cite journal
| last = Mazzanti
| first = Stefano
| title = Plain Bases for Classes of Primitive Recursive Functions
| journal = Mathematical Logic Quarterly
| volume = 48
| issue = 1
| pages = 93–104
| year = 2002
| issn = 0942-5616
| doi = 10.1002/1521-3870(200201)48:1<93::AID-MALQ93>3.0.CO;2-8
| oclc = 5154649764
}}

* {{cite arxiv
| last1 = Prunescu
| first1 = Mihai
| last2 = Sauras-Altuzarra
| first2 = Lorenzo
| title = On the representation of C-recursive integer sequences by arithmetic terms
| date = 2025-06-05
| arxiv = 2405.04083
| class = math.LO
}}

*{{cite arXiv
| last1 = Prunescu
| first1 = Mihai
| last2 = Sauras-Altuzarra
| first2 = Lorenzo
| last3 = Shunia
| first3 = Joseph M.
| date = 2025-08-08
| title = A Minimal Substitution Basis for the Kalmar Elementary Functions
| arxiv = 2505.23787
| class = math.LO
}}

*{{cite book
| last = Rose
| first = H. E.
| title = Subrecursion: Functions and Hierarchies
| publisher = [[Oxford University Press]]
| year = 1984
| isbn = 0-19-853189-3
}}

*{{cite journal
| last = Skolem
| first = Th.
| author-link = Thoralf Skolem
| title = Proof of some theorems on recursively enumerable sets
| journal = [[Notre Dame Journal of Formal Logic]]
| volume = 3
| issue = 2
| pages = 65–74
| date = 1962
| doi = 10.1305/ndjfl/1093957149
}}

*{{cite journal
| last = Volkov
| first = S. A.
| title = On the class of Skolem elementary functions
| journal = Journal of Applied and Industrial Mathematics
| volume = 4
| issue = 4
| pages = 588–599
| date = 2010
| doi = 10.1134/S1990478910040149
}}

*{{cite arXiv
| last = Volkov
| first = Sergey
| year = 2016
| eprint = 1611.04843
| title = Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions [dissertation]
| class = cs.CC
}}

== External links ==
*{{cite web
| last= Lysikov
| first= Vladimir
| title= Can superposition alone generate the Kalmár elementary function x<sup>y</sup> from ⟨x+y, x mod y, 2<sup>x</sup>⟩?
| url=https://math.stackexchange.com/questions/5094779/can-superposition-alone-generate-the-kalm%c3%a1r-elementary-function-xy-from-x
| date = 2025-09-07
| website=Math Stack Exchange
| access-date=2025-09-08
}}

{{ComplexityClasses}}

[[Category:Complexity classes]]
[[Category:Computability theory]]

Elementary recursive function - Revision history

imported>Oneequalsequalsone: Adding local short description: "Concept in computability theory", overriding Wikidata description "complexity class, algebra"