2015年1月4日

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

SKIコンビネータはなぜチューリング完全なのか? その考察です。 今回の趣旨として…今回? 毎回? まあ、結構な頻度であれですが、 今回は一切のGoogle先生だより等を禁止してみました。 続きを読む
2
ちょまど🎀MS入社5周年嬉しい @chomado

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

2015-01-04 16:18:32
らいどっと @rydotyosh

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

2015-01-04 16:19:23
ちょまど🎀MS入社5周年嬉しい @chomado

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

2015-01-04 16:23:40
Deprecatad @aiya_000

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

2015-01-04 20:23:23
Deprecatad @aiya_000

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

2015-01-04 20:25:31
Deprecatad @aiya_000

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

2015-01-04 20:27:18
Deprecatad @aiya_000

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

2015-01-04 20:29:23
Deprecatad @aiya_000

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

2015-01-04 20:32:18
Deprecatad @aiya_000

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

2015-01-04 20:33:47
Deprecatad @aiya_000

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

2015-01-04 20:36:53
Deprecatad @aiya_000

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

2015-01-04 20:37:52
Deprecatad @aiya_000

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

2015-01-04 20:39:27
Deprecatad @aiya_000

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

2015-01-04 20:40:52
Deprecatad @aiya_000

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

2015-01-04 20:42:33
Deprecatad @aiya_000

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

2015-01-04 20:43:43
Deprecatad @aiya_000

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

2015-01-04 20:43:59
Deprecatad @aiya_000

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

2015-01-04 20:45:47
Deprecatad @aiya_000

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

2015-01-04 20:49:06
Deprecatad @aiya_000

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

2015-01-04 20:51:09
Deprecatad @aiya_000

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

2015-01-04 20:52:24
Deprecatad @aiya_000

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

2015-01-04 20:53:30
Deprecatad @aiya_000

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

2015-01-04 20:56:56

コメント

コメントがまだありません。感想を最初に伝えてみませんか?