View source for Elementary recursive function

{{About| |other meanings|Elementary 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, <math>O(2^{2^n})</math>).

The name was coined by [[László Kalmár]], in the context of [[Computable function|recursive functions]] and [[Undecidable problem|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 problem]]s is denoted [[ELEMENTARY|<math>\mathsf{ELEMENTARY}</math>]].

==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: ''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'') = ''x'' − ''y'' if ''y'' < ''x'', or 0 if ''y'' ≥ ''x''. 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. In ''f''(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>) = ''h''(''g''<sub>1</sub>(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>), ..., ''g''<sub>m</sub>(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>)) is elementary recursive if ''h'' is elementary recursive and each ''g''<sub>i</sub> 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 ''g'' 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 ''g'' is elementary recursive.

== Basis for ELEMENTARY ==

The class of elementary functions coincides with the closure with respect to composition of the projections and one of the following function sets: <math>\{ n+1, n \,\stackrel{.}{-}\, m, \lfloor n/m \rfloor, n^m \}</math>, <math>\{ n+m, n \,\stackrel{.}{-}\, m, \lfloor n/m\rfloor, 2^n \}</math>, <math>\{ n+m, n^2, n \,\bmod\, m, 2^n \}</math>, where <math>n \, \stackrel{.}{-} \, m = \max\{n-m, 0\}</math> is the subtraction function defined above.<ref>{{cite journal | last1 = Mazzanti | first1 = S | year = 2002 | title = Plain Bases for Classes of Primitive Recursive Functions | journal = Mathematical Logic Quarterly | volume = 48 | pages = 93–104 | doi=10.1002/1521-3870(200201)48:1<93::aid-malq93>3.0.co;2-8}}</ref><ref>S. S. Marchenkov, "Superpositions of elementary arithmetic functions", ''Journal of Applied and Industrial Mathematics'', September 2007, Volume 1, Issue 3, pp 351-360, {{doi|10.1134/S1990478907030106}}.</ref>

== 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.<ref>[[Thoralf Skolem|Th. Skolem]], "Proof of some theorems on recursively enumerable sets", ''[[Notre Dame Journal of Formal Logic]]'', 1962, Volume 3, Number 2, pp 65-74, {{doi|10.1305/ndjfl/1093957149}}.</ref><ref name="volkov_skolem">S. A. Volkov, "On the class of Skolem elementary functions", ''Journal of Applied and Industrial Mathematics'', 2010, Volume 4, Issue 4, pp 588-599, {{doi|10.1134/S1990478910040149}}.</ref>

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.<ref name="volkov_skolem" /><ref>{{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 }}</ref> 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 \,\stackrel{.}{-}\, 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}}.

== Descriptive characterization ==

In [[descriptive complexity]], ELEMENTARY is equal to the class [[HO (complexity)|HO]] of [[language (computer science)|language]]s that can be described by a formula of [[higher-order logic]].<ref>{{Citation | author = Lauri Hella and José María Turull-Torres | title =Computing queries with higher-order logics | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 355 | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | doi=10.1016/j.tcs.2006.01.009| doi-access = free }}</ref>  This means that every language in the ELEMENTARY complexity class corresponds to as a higher-order formula that is true for, and only for, the elements on the language.  More precisely, <math>\mathsf{NTIME}\left(2^{2^{\cdots{2^{O(n)}}}}\right) = \exists{}\mathsf{HO}^i</math>, where ⋯ indicates a tower of {{mvar|i}} exponentiations and <math>\exists{}\mathsf{HO}^i</math> is the class of queries that begin with existential quantifiers of {{mvar|i}}th order and then a formula of {{math|(''i''&nbsp;−&nbsp;1)}}th order.

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

==Notes==
{{reflist}}

== References ==
* Rose, H.E., ''Subrecursion: Functions and hierarchies'', [[Oxford University Press]], 1984. {{ISBN|0-19-853189-3}}

{{ComplexityClasses}}

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