低初等帰納的関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/07 19:04 UTC 版)
「ELEMENTARY」の記事における「低初等帰納的関数」の解説
限定積を用いずに定義できる初等的関数は低初等帰納的（英: lower elementary recursive）という。すなわち、低初等帰納的関数はゼロ関数, 後者関数, 射影関数, 減算関数から始めて関数合成と限定和を取る操作を有限回繰り返して得られる関数をいう。低初等的関数のクラスを LOWER-ELEMENTARY と書く。スコーレムの初等関数としても知られる。 初等的関数が潜在的に指数的な増大度を持つが、他方で低初等的関数は多項式の増大度を持つ。すなわち低初等的関数は多項式関数で支配される。したがって指数関数は初等的だが低初等的でない。 これは初等関数における同様の結果のアナロジーとして、低初等的関数もまた幾つかの単純な関数の合成によって記述できる。すなわち、多項式で抑えられる関数が低初等的であるのは、それが次の関数の合成で表せるとき、かつそのときに限る：射影, n + 1 {\displaystyle n+1} , n m {\displaystyle nm} , n − . 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を表す。
※この「低初等帰納的関数」の解説は、「ELEMENTARY」の解説の一部です。
「低初等帰納的関数」を含む「ELEMENTARY」の記事については、「ELEMENTARY」の概要を参照ください。
- 低初等帰納的関数のページへのリンク
