計算可能性理論を100年ぐらい前に勉強したときに、帰納的関数論、チューリングマシン、PASCALのサブセット、何とかタブロー(忘れた。なんかカードゲームみたいなので ポストシステム?) だの何だのが全部チューリング完全で計算能力としては同等、というのを延々証明していた。
がしかし、
なぜかラムダ計算はやってなかった。というわけでやってみた。
C#書いていて無名関数書いたりとかは苦も無くできるものの(矢印書くだけだものな!)、こう、故郷(ふるさと)を少し見てやりたくなったのだ。
※本来は結合の順番や、どのような規則が適用されるかから積立てればいいのは分かっているんだけれども、どっちみちこの分野は 0 定義して +1 定義して sum pred … と組み立てていくところは共通。変換規則をとやかくいうのももちろん。自由変数と衝突する変数名の付替えとかももちろん(C言語ですら…)。なにか計算したいんだろうということと、この計算方法が他の計算モデルと計算能力が同じと言いたいとかそのへんはいつもどーーりだろう。
というわけで、ざーっと素手でやってみた。
結構コケました。
wikipedia の例題を改題しながら辿ってみました。
関数と適用
最初は + とか 5 とかが何でできているのかはぼんやりスルーしてみる。
λx. x + 5
. の前の部分は変数リストみたいなもの。入力 x に対して x+5 を返す関数を表す。
適用…関数に値を放り込む。いや、値を関数で処理してやるというのが適切か。
(λx. x + 5 ) 3
=3+5=8
まて!! このイコールはナンダ !!! もここではスルーしてみる。(等価性で検索してくださいな)
※普通のイコールは「値が等しい」。別に左辺と右辺の文字列が等しいとは言ってない。じゃあ関数が等しいって何? 関数の挙動が等しいってこと? 両辺の文字列を変形したら同じものにたどり着くような変形の path が存在するということ? 何なんだーーー という問題があるのです。
λxy. x +y #むむむ? 変数ぞろっと増えたぞ。大丈夫か?
適用…関数に値を放り込む。
(λxy. x +y) 2 3
xに2, yに3が入り 2+3=5
一変数関数の入れ子で書き直してみる。
λx.(λy. x +y)
λと. の間が引数であるから、この関数は x に a を放り込むと
λy. a +y …を返す関数
(関数が関数を返すというアイデアに慣れていない人は立ち止まって考えた方が良い 少し下の方に補足がある)
適用…関数に値を放り込む。3 2 だが 左から適用されていく。つまり 3 を適用。
λx.(λy. x +y) 3 2
関数 λx.(λy. x +y) が
引数: x 返り値: (λy. x +y)
と読めているか確認。返ってくるのは、
(λy. 3 +y) 2
さらに適用し、3+2 が返り、5となる。
略記
(λxy. x +y) 3 2
x に 3, y に 2。
補足 関数が等しいとか、関数を変数に代入するというのは高校数学まででは出てこないので意味不明かもしれない
関数 f は、対応表みたいなものなんだ。
例えば
f(0)=0, f(1)=2, f(2)=4
は
0には0を、1には2を、2には4 を対応させている
というだけ。
コンピュータの計算などのときには、動きをつけて表現することが多くて、
0を入れたら0が出てくる、1を入れたら2が出てくる、2を入れたら3が出てくる
対応の集合として書けば
{(0,0),(1,2),(2,4)}
という風にペアの集合というだけ。対応表。有限個ならば書きまくれば良い。
g(x)=x+3, x:自然数 だと書ききれないじゃないか!!
ご安心。
{ (x,x+3) | x= 0,1,2,3,… }
補足注意: ここで言う関数は数学の関数。C言語の関数とは違う。例えば func1(x) func2(x) どちらも任意の入力に対し同じ計算をするのであれば、数学の関数としては同じ。一つの関数を計算するプログラムは無数にある。
ラムダ式による自然数の表現
0 ≝ λf x. x
1 ≝ λf x. f x
2 ≝ λf x. f (f x)
3 ≝ λf x. f (f (f x))
と続く。↓の方がウルサイけど語弊がないかな
0=λf(λx.x)
1=λf(λx.fx)
2=λf(λx.f(fx))
3=λf(λx.f(f(fx)))
0 ≝ λf x. x
引数が f と x、返り値がx。
引数 f には x, 引数 x には何もなし。f の値に関係なく、どのみち返り値は x。
なんだこの f やる気あるんか? λ x. x でもいいじゃないのか?
と言いたくなるけど次から f は本気出してくれる?
1 ≝ λf x. f x
引数が f と x、返り値が f x。
引数 f には f, 引数 x には x。
fx は f を x に適用するもの。まだ謎? 次へ。
2 ≝ λf x. f (f x)
引数が f と x、返り値が f (f x )。
引数 f には f, 引数 x には x。
λf x.f (f x) の挙動を見てみよう。+,3,4,5,…が定義されていないぞというツッコミは却下。
f に λy.y+1 を
x に 2 とすることを考えてみる。
(λf x. f (f x)) (λy.y+1) 2
※f (f x)の
※f のところに (λy.y+1)
※x のところに 2 と書く
(λy.y+1) ((λy.y+1) 2 ))
(λy.y+1) (2+1)
(λy.y+1) 3
3+1
4
f を 2回適用している訳か
3 ≝ λf x. f (f (f x))
ああ、f 3回やるんだな
f に λy.y+1 を
x に 2 とすることを考えてみる。
λf x. f (f (f x)) (λy.y+1) 2
(λy.y+1) ( (λy.y+1) ( (λy.y+1) 2))
(λy.y+1) ( (λy.y+1) 3 )
(λy.y+1) 4
5
後続者関数 succ(x) を定義してみる
本当は 0 と succ を定義してやればいいだけだったんだけどね。まあいいや。
ご先祖様がいて、次の子孫がいて、次の子孫がいて、次の子孫がいて、…
λn f x. f (n f x) 関数適用は左結合である。 f( (n f) x )
λn.(λf.(λx.f((nf)x)))
0に適用してみる。
λn .(λf.(λx.f((nf)x)))0
λf.(λx.f((0f)x))
!!! 0 ????
0 ≝ λf x. x を思い出して、
0f は
(λf x. x) f
λx. x
λf.(λx.f((0f)x))
λf.(λx.f((λx. x)x))
λf.(λx.f(x))
これは 1 だな。
和 SUM(m,n) を定義してみる
SUM(m,n) = λm n f x. m (n f x) ????
m,n=2,1 ぐらいで試すと
2 ( 1 f x)
1 = λfx.fx
2 = λfx.f(fx)
だから
( λfx.f(fx) ) ((λfx.fx ) f x)
( λfx.f(fx) ) (fx) ###
f(fx) 2!!!
何か足らん…###でf が一個なくなるんだな…
SUM(m,n) = λm n f x. m f (n f x) ????
m,n=2,1 ぐらいで試すと
2 f ( 1 f x)
1 = λfx.fx
2 = λfx.f(fx)
だから
( λfx.f(fx) ) f ((λfx.fx ) f x)
( λfx.f(fx) ) f ((λx.fx ) x)
( λfx.f(fx) ) f (fx)
( λfx.f(fx) ) f(fx)
( λx.f(fx) ) (fx)
f(f(fx)) 3!!!!
今日はここまでー。
