合成
composition
普通の関数合成$ f=h\circ gを$ n引数関数の場合へと一般化する
下の定義の$ m=n=1のときが普通のやつやねmrsekut.icon
$ g_1,\cdots,g_m, hが計算可能なら、それらを合成した$ f(\vec{x})=h(g_1(\vec{x}),\cdots,g_m(\vec{x}))も計算可能 古典的順序と図式順序
classical order
$ g\circ fのように書く
順序を逆転して書く
diagrammatic order
$ f;gのように書く
合成のそのままの順序で書く
でも日英ともにググってもヒットしないのであまり一般的な用語ではない気がするmrsekut.icon
定義
任意の関数
$ g_1,\cdots,g_m:\mathbb{N}^n\rightarrow\mathbb{N}
$ h:\mathbb{N}^m\rightarrow\mathbb{N}
から、次のようにして定義される関数$ f:\mathbb{N}^n\rightarrow\mathbb{N}を構成する操作を合成という $ f(\vec{x})=h(g_1(\vec{x}),\cdots,g_m(\vec{x}))
補足
見ればわかるが、$ f,g_1,\cdots,g_mは全て$ n引数の全域関数
個数を特定しない変数の並びを以下のように表している
$ \vec{x}:=x_1,\cdots,x_k
「関数のクラス$ Eが合成に関して閉じている」とは
$ \forall f,g_1\cdots,g_n\in E\Rightarrow\lambda\vec{x}.f(g_1(\vec{x}),\cdots,g_n(\vec{x}))\in E
部分関数の場合は
参考