帰納的関数 - 暇つぶしWikipedia

帰納的関数

μ再帰関数（ミューさいきかんすう、英: μ-recursive function）または帰納的関数（きのうてきかんすう）とは、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。

また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。

計算複雑性理論では、全再帰関数の集合をRと称する。
定義

μ再帰関数（または部分μ再帰関数）は、有限個の自然数の引数をとり、1つの自然数を返す部分関数である。μ再帰関数は初期関数を含み、合成や原始再帰やμ作用素において閉じている、部分関数の最小のクラスである。

原始再帰関数も同じような形式で定義されるが、全域関数という点が異なる。また、原始再帰関数は、3つの基本関数（定数関数、後者関数、射影関数）と2つの作用素（合成と原始再帰）で定義されるが、μ再帰関数にはさらにμ作用素が登場する。これはアッカーマン関数のように原始再帰関数でない全域再帰関数を定義するためである。μ再帰関数においてμ作用素は計算を終了させる。μ作用素は無制限探索演算子として働き、（全域関数の定義から）無制限ではあるが何らかの手段（帰納的定義など）で最終的に数を生成し計算を終わらせるのである。

しかし、無制限μ作用素自身が部分的な場合（つまり、ある数について数を返せないことがある場合）、それを使って定義された関数も部分関数となり、一部の数については値が定義されない。この場合、無制限という性質上、μ作用素は永遠に探索を続け、計算を終了して数を返すことがない。アルゴリズムによっては、"u" という記号で「決定不能（undecided）」を表し、計算を終了させるとする場合もある（例えば、Kleene (1952) pp. 328ff）。換言すれば、部分μ再帰関数は部分μ作用素を使うため、全域的でない可能性がある。全域μ再帰関数（total μ-recursive functions）は部分μ再帰関数の部分集合である。

以下の定義は Kleene (1952) p. 219 に基づいている。最初の3つの関数(1)-(3)を「初期関数（initial functions）」または「基本関数（basic functions)」と呼ぶ。その他の記号体系については「記号体系」の節を参照されたい。

(1) 定数関数（Constant function）: 任意の自然数 n {\displaystyle n} と k {\displaystyle k} について:
f ( x 1 , … , x k ) = n {\displaystyle f(x_{1},\ldots ,x_{k})=n} .定数 n {\displaystyle n} は、「初期オブジェクト・ゼロ（initial object 0）」と呼ばれるオブジェクトに後者関数を繰り返し適用することで生成されることがある。

(2) 後者関数（Successor function）S: 既に生成されたオブジェクトから別のオブジェクト n + 1 {\displaystyle n+1} または n ′ {\displaystyle n'} （ n {\displaystyle n} の後者）への逐次的経路
S ( x ) = d e f f ( x ) = x ′ = x + 1 {\displaystyle S(x){\stackrel {\mathrm {def} }{=}}f(x)=x'=x+1\,}

(3) 射影関数（Projection function）Pik （Identity function Iik とも）: 1 ≤ i ≤ k {\displaystyle 1\leq i\leq k} であるような全ての自然数 i {\displaystyle i} について:
P i k = d e f f ( x 1 , … , x k ) = x i {\displaystyle P_{i}^{k}{\stackrel {\mathrm {def} }{=}}f(x_{1},\ldots ,x_{k})=x_{i}} .

(4) 合成作用素（Composition operator）: 置換（substitution）とも呼ばれ、関数 h ( x 1 , … , x m ) {\displaystyle h(x_{1},\ldots ,x_{m})} と 1 ≤ i ≤ m {\displaystyle 1\leq i\leq m} であるような i {\displaystyle i} それぞれについての関数 g i ( x 1 , … , x k ) {\displaystyle g_{i}(x_{1},\ldots ,x_{k})} をとり、 x 1 , … , x k {\displaystyle x_{1},\ldots ,x_{k}} を以下のようにマップする関数を返す操作である。
f ( x 1 , … , x k ) = h ( g 1 ( x 1 , … , x k ) , … , g m ( x 1 , … , x k ) ) {\displaystyle f(x_{1},\ldots ,x_{k})=h(g_{1}(x_{1},\ldots ,x_{k}),\ldots ,g_{m}(x_{1},\ldots ,x_{k}))} .

(5) 原始再帰作用素（Primitive recursion operator）: 関数 g ( x 1 , … , x k ) {\displaystyle g(x_{1},\ldots ,x_{k})} と h ( y , z , x 1 , … , x k ) {\displaystyle h(y,z,x_{1},\ldots ,x_{k})} をとり、以下のような関数 f {\displaystyle f} を返す操作である。
f ( 0 , x 1 , … , x k ) = g ( x 1 , … , x k ) {\displaystyle f(0,x_{1},\ldots ,x_{k})=g(x_{1},\ldots ,x_{k})} , f ( y + 1 , x 1 , … , x k ) = h ( y , f ( y , x 1 , … , x k ) , x 1 , … , x k ) {\displaystyle f(y+1,x_{1},\ldots ,x_{k})=h(y,f(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})} .

(6) μ作用素: 関数 f ( y , x 1 , … , x k ) {\displaystyle f(y,x_{1},\ldots ,x_{k})} をとり、 x 1 , … , x k {\displaystyle x_{1},\ldots ,x_{k}} を引数とする関数 μ y f ( y , x 1 , … , x k ) {\displaystyle \mu yf(y,x_{1},\ldots ,x_{k})} を返す操作である。関数 f {\displaystyle f} は自然数 { 0 , 1 , . . . n } {\displaystyle \{0,1,...n\}} から自然数 { 0 , 1 , . . . n } {\displaystyle \{0,1,...n\}} への数論的関数か、または値域 { 0 , 1 } {\displaystyle \{0,1\}} で真偽を示す述語としての指示関数である。
どちらの場合でも、関数 μ y f {\displaystyle \mu yf} は、 f ( 0 , x 1 , … , x k ) , f ( 1 , x 1 , … , x k ) , . . . , f ( y , x 1 , … , x k ) {\displaystyle f(0,x_{1},\ldots ,x_{k}),f(1,x_{1},\ldots ,x_{k}),...,f(y,x_{1},\ldots ,x_{k})} が全て値を返すとき、 f ( y , x 1 , … , x k ) = 0 {\displaystyle f(y,x_{1},\ldots ,x_{k})=0} となるような自然数 y {\displaystyle y} があれば、そのうちの最小のものを返す。もしそのような y {\displaystyle y} がなければ、 μ y f {\displaystyle \mu yf} はそのときの引数 x 1 , … , x k {\displaystyle x_{1},\ldots ,x_{k}} の組み合わせに対して定義されない。

部分μ再帰関数同士を比較する演算子として ≃ {\displaystyle \simeq } （strong equality）がある。部分関数 f {\displaystyle f} と g {\displaystyle g} について、 f ( x 1 , … , x k ) ≃ g ( x 1 , … , x l ) {\displaystyle f(x_{1},\ldots ,x_{k})\simeq g(x_{1},\ldots ,x_{l})}

Size:22 KB
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef