from 帰納的関数

while文に対応する

ref 帰納的であることと、計算可能であることは同値である

定義

関数fが以下のように定義されるとき、fはgから最小化で得られた、と言う

f(\vec{x})=\mu y[g(\vec{x}, y)]と表す

補足

\muはμ演算子

f(\vec{x})の返り値は、yもしくは未定義になる

f(\vec{x})=yであるとは、下図のようになっていること

下表になるような自然数n_0,\cdots,n_{y-1} \ne 0が存在する

\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

何を表している？

部分関数の構成法？

何が嬉しい？

有界最小化との違い

μ演算との違い

参考

『(理論)12 計算モデルの基礎理論』 p.51-