[#情報数学](情報数学) [#理論計算機科学](理論計算機科学) 定義 - [[最小解関数]]は以下で定義される - 述語$P: N^{n+1} \rightarrow {T, F}$に対して、$f(x_1, x_2, ..., x_n) = min(\{ y | p(x_1, x_2, , ..., x_n, y) \mathrm{\ is \ True} \})$ - fはpが真となる最小のy - fは述語pの最小解関数と呼ばれ、$\mu_y(p(x_1, x_2, ..., x_n, y))$と書かれる - $\mu$は[[最小解演算子]]とよばれる - [[帰納的関数]]([[Recursive function]])は以下で定義される - [[原始帰納的関数]] - [[原始帰納的述語に対する最小解関数]] - 帰納的関数の合成 定理 - 帰納的関数は[[計算可能]]である - 証明: 原始帰納的関数は計算可能なので、最小解関数の場合だけ示せば良い - [[計算可能]]な関数は[[帰納的関数]]である