ELEMENTARY
この名称はカルマール(英語版)による造語である。
帰納的関数や決定不能性の文脈で扱われる多くの問題は ELEMENTARY よりも高いレベルにある。いくつかの帰納的問題は ELEMENTARY を超える。すなわち NONELEMENTARY となる。とくに注目されるのは、原始帰納的問題で ELEMENTARY に属さないものが存在することである。次が知られている。
LOWER-ELEMENTARY ⊊ {\displaystyle \subsetneq } EXPTIME ⊊ {\displaystyle \subsetneq } ELEMENTARY ⊊ {\displaystyle \subsetneq } PR ⊊ {\displaystyle \subsetneq } R
ELEMENTARY は指数関数の定数回の入れ子(例えば 2 2 n {\displaystyle 2^{2^{n}}} )を含むが、PRは指数関数の一般化であるハイパー演算子で ELEMENTARY に属さないもの(例えばテトレーション)を含む。