計算言語５（帰納的関数）
このページはマス旅の一部です。
今回は機能関数を作ろう。
ざっくり、whileでプログラムがかける関数を「while関数」と呼びます。
while関数は今回紹介する「帰納的関数、機能関数」とつながります。
さて、帰納的といえば、数学的帰納法や反復計算や再帰関数を連想しますね。
想像ではなく、コトバで定義してみよう。
まず、帰納的関数のクラスには初期関数が３つあります。
ゼロ関数、後者関数、射影です。
この３つは帰納的です。
・ゼロ関数は変数を取らずただゼロを返します。zero()=0です。
・後者関数はsucc(x)=x+1,前回やったadd1(x)と同じですね。
・射影はu_i^n(x1,...,xn)=xiのように、n個の引数からi番目の成分を抜き出す。
これらは前回作った言語Mで実現できそうですね。
初期関数から開始して「次の３つの操作」を使ってできる関数は、帰納的関数となります。
「３つの操作」は、合成、原始帰納、最小だ。
・合成：m個の引数をとる関数ｆと、n個の引数をとる関数g1,g2,..gmが帰納的なら、f(g1(x1,...,xn),....,gm(x1,...,xn))も帰納的だ。
・原始帰納：n変数のgと(n+2)変数のhが帰納的なら、(n+1)変数のｆも帰納的になる。
f(0,x1...xn)=g(x1...xn),f(k+1,x1...xn)=h(f(k,x1...xn),k,x1...xn)
特に、
n=0の場合、ｆ(0)=ｇ、f(y+1)=h(y,f(y))となるｆが原始関数。
n=1の場合、
f(0,x)=g(x),f(k+1,x)=h(f(k,x),k,x)となるｆが原始関数。
f(x,0)=g(x), f(x,k+1)=h(x,k,f(x,k))となるｆが原始関数。
hはfの前のステップのkとfも受けるから、gよりも引数が2個多いことは注目しておこう、hの引数の位置は任意だけれど、それにfの引数の順序が一定であればよいですね。
・最小化：g(x1,...xn,y)=0となる最小の自然数をyを探す操作。
f(x1,....xn)=μ_y[g(x1,...,xn,y)=0]
この操作でできる関数fも帰納的だ。
ただし、この最小化操作で条件を満たすyが見つからない、停止しない無限ループになることもあるので、入力しても値が定義されない可能性を許した関数として、部分関数と呼ぶ。
以上の３初期関数に３操作を繰り返してできる（部分）関数のクラスを帰納的関数と呼ぶ。
天下り的な始まりなので、実例で確かめていこう。
＜自然数は帰納的関数＞
one=succ(zero())=succ(0)=1
two=succ(one)=succ(1)=2,
three=succ(two)=succ(2)=3,
....
1,2,3.,...という自然数が、帰納的関数になる。
ペアノ的で単純で美しいですね！
＜加算、乗算は帰納的関数＞
h(x1,x2,x3)=succ(u_3^3(x1,x2,x3))
3引数の第3成分（前の計算結果）を取り出して１加算するh関数を使うと、次のようにして加算plus(x,k)は原始帰納で定義できる。
plus(x,0)=u_1^1(x)
plus(x,k+1)=h(x,k,plus(x,k))=plus(x,k)+1
h'(x1,x2,x3)=plus(u_1^3(x1,x2,x3),u_3^3(x1,x2,x3))
h'は3引数の先頭と最後を取り出し加算する関数とすれば、
すると、次のようにして乗算mult(k,x)は原始帰納で定義できる。
mult(0,x)=zero(x)=0
mult(k+1,x)=h'(mult(k,x),k,x)=plus(mult(k,x),x)
これって、同じ数ｘのたし算の反復がかけ算になるという
常識的な定義をうまく表しているね。
＜論理演算子も帰納的関数＞
省略しますが、上と同様にして、原始帰納を使うと、
帰納関数をぞろぞろ作れる。
pred(0)=0, pred(k+1)=k
gt(x,y)=if(x>y,1,0)
zero?(x)=if(x==0,1,0)
dif(x,y)=if(x>=0,x-y,0)
abs(x,y)=plus(dif(x,y),dif(y,x))
eq(x,y)=if(x==y,1,0)
ge(x,y)=if(x>=y,1,0)
面白いことに、算術関数を流用して、論理関数が作れる。
１を真、0を偽とし、述語を{0,1}とする関数を定義する。
not(p)=zero?(p) これはpがゼロなら真で１、それ以外は0を返すからだ。
and(p,q)=mult(p,q)。
乗算は(p,q)=(1,1)のときだけ1になるから同じだとわかる。
andとnotが定義できれば、おなじみのドモルガンの定理でor関数も帰納的になるね。
自然数の上の（部分）関数ｆが 帰納的（部分）関数であることとwhile関数であることは同値だという。
車輪の開発ワールドになっているね。
でも、それはそれで、
基礎を振り返る、建物の地盤を調べるということで、大切なことではあるね。
課題：mult(3,4)を原始帰納を使って、12になることを確認しよう。
h'(x1,x2,x3)=plus(u_1^3(x1,x2,x3),u_3^3(x1,x2,x3))
mult(0,x)=zero(x)=0
mult(k+1,x)=h'(mult(k,x),k,x)=plus(mult(k,x),x)
mult(x,0)=zero(x)=0
mult(x,k+1)=h'(x,k,mult(x,k))=plus(x,mult(x,k))
これを前提とする。
＜手動トレース＞
4を0にするよりも、3を0にする方が回数が少ないから、
mult(3,4)
=plus(mult(2,4),4)
=plus(plus(mult(1,4),4),4)
=plus(plus(plus(mult(0,4),4),4),4)
=plus(plus(plus(0,4),4),4)
=plus(plus(4,4),4)
=plus(8,4)
=12
plus(x,4)
=plus(x,3)+1
=plus(x,2)+1+1
=plus(x,1)+1+1+1
=plus(x,0)+1+1+1+1
=x+1+1+1+1=x+4
となるから、
plus(x,4)はxから4後者の数。
x=0から始まって、3回入れ子plus(x,4)を繰り返すので、
mult(3,4)=((0+4)+4)+4=4+4+4=12
こうして、
乗算⇒加算⇒後者関数
と、基礎に還元できることがわかる。
＜geogebraでコード化＞
mult(3,4)を作る。
g(x)=x+4とすると、
Iteration(g,0,3)=((0+4)+4)+4=12となるはず。
xの初期値0でgを3回繰り返すから。
そこで、
xx=4
mxx(x)=x+xx
とすると、mxxはxのxxだけ後者を指す。
k=3
mul=Iteration(mxx,0,k)=Iteration(+4,0,3)=12
という数値になる。
「新規ツール」で、「入力」をxx,k、「出力」をmulとして、名前をMLとすると
ML(3,4)=12となるはず。
ML(5,8)=40となる。
GUIとしては、
p=InputBox(k)
q=InputBox(xx)
r=ML(k,xx)
text=p+"x"+q+"="+r
タイトルは「かけ算をたし算の反復によって計算しよう。」
これで、かけ算関数をたし算の反復で作ることができた。
もちろん、たし算関数も後者関数で作れるでしょうが、
このくらいにしておこう。