←講義のツボメニューへ
情報学基礎Ａ
【第１４回】【2000.11.28】
関数モデル
（３）
帰納的関数
自然数上の関数の中にはある値に対して未定義となるような関数（部分関数）が
存在する。
部分関数において、未定義の場合には、その関数の計算が終わらない（停止しない）
状態になる。
このような部分関数を原始帰納的関数として定義できない。
また、原始帰納的関数だけからなる集まりに属さないが、きちんと計算できる関数
（例：Ackermann関数）が存在する。
帰納的関数の例
除算関数、平方根関数、対数関数
最小化
停止しないかもしれない計算に対応する関数の構成法
（原始帰納的関数）＋（最小化）→（帰納的関数）
例）
g(x,y)でxが決まったときのy？複数ある場合
→最小化
g(x,y)=xΘy（x＜yのとき０、x≧yのときx-y）
xΘy=0となるとき、x≦yである任意の数（最小のyはx）
min{y|xΘy=0}においてx=3のとき
min{y|3Θy=0}=min{y|3,4,5,・・・}=3
例）
g(x,y)=S(x)+y=0
となるyは自然数上に存在しない。→yが定義できない。
g(x1,...,xn,y)=0:Nn+1→N
に対して、
μy(g(x1,...,xn,y)):Nn→N
を次のように定義する。
１）
g(x1,...,xn,y)=0
となるyが存在するとき
μy(g(x1,...,xn,y))=min{g(x1,...,xn,y)=0}
２）１の条件が満足されないとき、
μy(g(x1,...,xn,y))
の値は定義されない。