ELEMENTARY
このリストを枚挙する原始帰納的関数 f ( c , x ) = 2 2 ⋅ ⋅ x ⏟ c {\displaystyle f(c,x)=\underbrace {2^{2^{\cdot ^{\cdot ^{x}}}}} _{c}} は初等的でない:対角線論法による。 f ( c , x ) {\displaystyle f(c,x)} が初等的と仮定する。すると f ( x , x ) {\displaystyle f(x,x)} もまた初等的であるから、ある c に対して f ( x , x ) < f ( c , x ) {\displaystyle f(x,x)<f(c,x)} が成り立つ。ところがここで x = c {\displaystyle x=c} とすると不合理を得る。同様の増大度を持つテトレーションもまた初等的でない原始帰納的関数である。
クラス ELEMENTARY はレベル3のグジェゴルチク階層、深さ2のループプログラムで計算可能な関数のクラス、時間計算量が指数関数の定数回の反復で抑えられる関数のクラスなどと一致する。
計算複雑性理論において ELEMENTARY とは指数階層(英語版)の和集合で表される複雑性クラスである。
E L E M E N T A R Y = E X P ∪ 2 E X P ∪ 3 E X P ∪ ⋯ = D T I M E ( 2 n ) ∪ D T I M E ( 2 2 n ) ∪ D T I M E ( 2 2 2 n ) ∪ ⋯ {\displaystyle {\begin{matrix}\mathrm {ELEMENTARY} &=&\mathrm {EXP} \cup \mathrm {2EXP} \cup \mathrm {3EXP} \cup \cdots \\&=&\mathrm {DTIME} (2^{n})\cup \mathrm {DTIME} (2^{2^{n}})\cup \mathrm {DTIME} (2^{2^{2^{n}}})\cup \cdots \end{matrix}}}
クラス ELEMENTARY に属す関数は初等帰納的(しょとうきのうてき、英: elementary recursive)あるいは単に初等的と呼ばれる。
初等的関数のクラスは次の何れかの集合と射影の合成に関する閉包と一致する: { n + 1 , n − . m , ⌊ n / m ⌋ , n m } {\displaystyle \{n+1,n{\stackrel {.}{-}}m,\lfloor n/m\rfloor ,n^{m}\}} , { n + m , n − . m , ⌊ n / m ⌋ , 2 n } {\displaystyle \{n+m,n{\stackrel {.}{-}}m,\lfloor n/m\rfloor ,2^{n}\}} , { n + m , n 2 , n mod m , 2 n } {\displaystyle \{n+m,n^{2},n{\bmod {m}},2^{n}\}} ここで n − ̇ m = max { n − m , 0 } {\displaystyle n{\dot {-}}m=\max\{n-m,0\}} は上で定義した減算関数である。 したがって例えば素数列はこれらの関数と自由代入とを用いた表示を持つことになる。
m {\displaystyle n\,{\stackrel {.}{-}}\,m} , n ∧ m {\displaystyle n\wedge m} , ⌊ n / m ⌋ {\displaystyle \lfloor n/m\rfloor } , 指数関数 ( 2 n {\displaystyle 2^{n}} または n m {\displaystyle n^{m}} ) 。ただし二つ以上の指数関数の底を含まないものとする。例えば x y ( z + 1 ) {\displaystyle xy(z+1)} は底を1つ含み、 ( x + y ) y z + x + z x + 1 {\displaystyle (x+y)^{yz+x}+z^{x+1}} は2つ含み、 2 2 x {\displaystyle 2^{2^{x}}} は3つ含む。ここで n ∧ m {\displaystyle n\wedge m} はビットごとのANDを表す。