最小化
minimalization
while文に対応する
定義
関数$ fが以下のように定義されるとき、$ fは$ gから最小化で得られた、と言う
$ f(\vec{x})=\mu y[g(\vec{x}, y)] と表す
補足
$ f(\vec{x})の返り値は、$ yもしくは未定義になる
$ f(\vec{x})=yであるとは、下図のようになっていること
下表になるような自然数$ n_0,\cdots,n_{y-1} \ne 0が存在する
https://gyazo.com/41735a5bd95dae2cfc97299022a106c9
$ \vec{x} が与えられたとき、$ f(\vec{x})=\mu y[g(\vec{x},y)] を求めるアルゴリズム
手順
1. $ y:=0とする
2. $ g(\vec{x},y)の値を計算しようとする
この値を$ zとする
3. $ z=0のとき、$ yを答えとして、計算を終了する
4. $ y:=y+1とする
5. ステップ2へ戻る
$ z=0になるまで、永遠に2~5を繰り返す
逆に言えば、$ z=0になるまで、このアルゴリズムは停止しない
$ gが常に停止する関数であっても、$ fが停止するとは限らない
このアルゴリズムを見れば、$ gが計算可能なとき、$ fは計算可能であることも自明にわかる 「関数のクラス$ Eが最小化に関して閉じている」とは
$ \forall\lambda y\vec{x}.g(y,\vec{x})\in E\Rightarrow\lambda\vec{x}.\mu y[g(y,\vec{x})]\in E
何を表している？
部分関数の構成法？
何が嬉しい？
参考