情報数学 理論計算機科学 定義 最小解関数は以下で定義される 述語P:Nn+1→T,Fに対して、f(x1,x2,...,xn)=min({y∣p(x1,x2,,...,xn,y) is True}) fはpが真となる最小のy fは述語pの最小解関数と呼ばれ、μy(p(x1,x2,...,xn,y))と書かれる μは最小解演算子とよばれる 帰納的関数(Recursive function)は以下で定義される 原始帰納的関数 原始帰納的述語に対する最小解関数 帰納的関数の合成 定理 帰納的関数は計算可能である 証明: 原始帰納的関数は計算可能なので、最小解関数の場合だけ示せば良い 計算可能な関数は帰納的関数である