本日のまとめ - SKIコンビネータはなぜチューリング完全なのか考察

ちょまど@ ITエンジニア @chomado

A「マジヤバイ！マジヤバイってマジで！マジヤバイ！」 B「マジで？！wwウケるwヤバイw」 隣のテーブルの女子高生軍団、本当に 「ヤバイ」 「ウケる」 「マジで」 の3語だけでチューリング完全な会話を実現している

ちょまど@ ITエンジニア @chomado

@chomado チューリング完全な言語

らいどっと @rydotyosh

skiコンビネータが思い出される（

ちょまど@ ITエンジニア @chomado

Lazy Kかな

ちょまど@ ITエンジニア @chomado

> Lazy K（れいじーけー）は組み込み関数が3つしかない、純粋関数型言語である。 3つの組み込み関数 (I, K, S) I x = x K x y = x S x y z = (x z) (y z)

Deprecatad @deprecatad

というかなんでSKIコンビネータだけでチューリング完全なんだろうね？

Deprecatad @deprecatad

Iコンビネータはもちろん、だろうけども。 関数と1つの…アルファベット？ つまり任意の関数と1つの値AでAの同等のものを出力せよ、 と言われたときに最小になるのがid関数だからじゃないかと思うっぽい。

Deprecatad @deprecatad

つまり関数と値の切り離せない対応で 値のみの状態にアンリフトするイメージなのかな。 id関数は id aとした時にaになるので idとaという対応からaを取り出せる。

Deprecatad @deprecatad

じゃあKコンビネータはなんだろう。 Kはつまりconstなんだけど、λで言うと \x _ -> x つまり λxy.x であって名前を付けると f x = \_ -> x になる関数っぽい。

Deprecatad @deprecatad

これは…さっきの感じで言うと 2つの値a,bを必ず使用してaを表せと言われたときに const a b とするということなのかな？

Deprecatad @deprecatad

うーん？ じゃあSコンビネータはどうかな。 Sコンビネータは引数を共有するんだったよね。 f,gを関数、xを値とした時に share f g x = f x (g x) という。

Deprecatad @deprecatad

これは…何？ 前にもこれでつまづいた気がする。 これがあれば、1つの値で複数の関数に関数適用できるとかそういうこと…？ うーん、わかんない。

Deprecatad @deprecatad

λfgx.(f x (g x)) だよね。 これが何を表しているのか…？

Deprecatad @deprecatad

1つの二引数関数に1つの一引数関数と言えば、 さっきのconstとid、つまりKコンビネータとIコンビネータを連想した…。

Deprecatad @deprecatad

これで組み立てるとすると f = const g = id として λfgx.(f x (g x)) とすると const x (id x) const x x x と簡約できる…っぽい。

Deprecatad @deprecatad

えーと…、S,K,I、 どれも1つの値で1つの値を表現できてる。 Sは今ので表現できる。 Kはconst x xで表現できる。 Iはid xで表現できる。 そしてSは上記のKとIの形に依存していた。

Deprecatad @deprecatad

依存していた(先ほどの形にするならば)。 うーん、でも、これでつまりアルファベットとλ式で値を抽象的に表せるのか…。

Deprecatad @deprecatad

それでなぜ、チューリング完全になるんだろう？

Deprecatad @deprecatad

あとは id,const,shareと進むにつれて1,2,3と引数を必要とするようになっているよね。 (あ、Sコンビネータはfix関数って言うんだっけ、忘れちゃった。)

Deprecatad @deprecatad

それで、 idは1つの引数を受け取って式内部でも1つの引数を1度だけ使用していたよね。 λx.x constは2つの引数を受け取って式内部ではそのうち1つの引数を1度だけ使用していたよね。 λxy.x

Deprecatad @deprecatad

Sは3つの引数を受け取って式内部ではf,g,xを1,1,2という頻度で使用していた。 λfgx.(f x (g x)) つまり idは引数1つで引数1つを処理する。 constは引数2つで引数1つを処理する。 Sは引数3つで引数4つを処理する。

Deprecatad @deprecatad

引数の受け取りと使用の頻度の対応は id => 1と1 (+0) const => 2と1 (-1) share => 3と4 (+1) になってる。

Deprecatad @deprecatad

それで、SコンビネータはKIコンビネータさえあれば表現することができた。 つまりはこの3つさえあれば引数をいくらでも使えていくらでも処理することができるっぽい？ だからチューリング完全になる…？

Deprecatad @deprecatad

確かにこの3つさえあれば、 表現の幅は広そう。 そういう理解になった。