SKIコンビネーター計算＜導入偏＞　ツイートまとめ

https://twitter.com/muzudho1/status/1603739785415495680?s=20&t=XLplLsYZbyCB81DUA7PWPw

#プログラミング 

SKI コンビネーター計算の話をする。ヒマなので😪💤💤

コンビネーターという言葉をまず聞かない(￣ー￣)
コンビネーションはまだ聞くだろ(￣ー￣) 3 C 3 なら 1 (￣ー￣)

何か関係あんの？　というと　似たようなもので　違うもの(￣ー￣)

仮に　卵　という字の右側に　卵　が並ぶと、２つ合わせて　鶏　になるというルールがあるとしよう(￣ー￣)

卵

が１個なら永遠に卵だが、

卵卵

なら、

鶏

になる(￣ー￣)

卵草卵卵

なら、左端の卵の右隣に草がきている(￣ー￣)
その場合のルールは定めていないので
計算終了(￣ー￣)

右に２つの卵が並んでいるが、
それを先に計算するようなルールは無いので
計算しない(￣ー￣)

じゃあ　卵の右隣に草が来たら　２つ合わせて１つの卵にしようぜ？

というようなルールを作ったら　どうなるか(￣ー￣)？

卵草卵卵

は、

卵卵卵

になるな(￣ー￣)

すると　まだ計算は続行できそうだ(￣ー￣)

卵卵卵

なら、

鶏卵

になるな(￣ー￣)
鶏の右隣に卵が並んだときの計算は定義されていないので、
これで計算は終了だぜ(￣ー￣)

じゃあ　鶏の右隣に卵が来たら　２つ合わせて　草にしようぜ？

というルールを追加してみよう(￣ー￣)

鶏卵

なら、

草

になるな( ﾟーﾟ) 草の右隣が無いときの計算ルールは定義されていないので、計算はこれで終了だぜ( ﾟーﾟ)

すると、

卵草卵卵

は、最終的には

草

になるわけだぜ( ﾟーﾟ)
このとき、登場した　卵、草、鶏を
卵コンビネーター、
草コンビネーター、
鶏コンビネーター
という( ﾟーﾟ)

モイセイ・シェインフィンケリという　おっさん　が、

こういうことを最初にやっていて、

Sコンビネーター
Kコンビネーター
Iコンビネーター

の計算ルールを定義した( ﾟーﾟ)

だが　お前らは　アルファベットを見ると眠くなって寝てしまうので

S、K、I　以外の話をする( ﾟーﾟ)

例えば、計算ルールの定義を
次のように書くとしよう

鶏　←　卵卵

これは、卵の隣に卵が並んだら、２つ合わせて　１つの鶏になる

ということを表した書き方と、ここで勝手に決めた( ﾟーﾟ)

ここで、現代風に　補助線を引くとしよう( ﾟーﾟ)

鶏　←　卵卵

は、

鶏　←　卵（卵）

という風に、卵の右隣の１個を丸カッコで囲む( ﾟーﾟ)

これは現代で言う　関数　の、祖先にあたる( ﾟーﾟ)

じゃあ、　卵が関数名なら、

卵（卵）

卵関数の　丸カッコの引数の中に　また卵という関数名　が入ってるの　おかしいじゃないか、という人もいるかも知れない

関数の引数に　関数名を入れていいのか？

良いのだ( ﾟーﾟ)

これを現代で言うと　関数も第一級のオブジェクト　という( ﾟーﾟ)

計算は左から始めるというのを　左結合　という

卵草卵卵

に補助線を引くと

{{{卵草}卵}卵}

で、内側の波カッコから計算する( ﾟーﾟ)

{{{卵草}卵}卵}

を、現代の関数風に書くと以下のようになる( ﾟーﾟ)

卵（草）（卵）（卵）

何も嬉しくないやんけ！　と思うかも知れないが
補助線の引き方の一例だ( ﾟーﾟ)

こんな話　もう眠い　と思うやつが

１学級４０人のうち４０人だと
計算機科学は発展しないが、

毎年　全国に１人居れば　十分すぎると思う(￣ー￣)

そのようなレベルの話をするやつ
よほど　ヒマ人(￣ー￣)

次に　皿コンビネーター　を新しく定義してみよう

卵　←　皿（草草）

皿の右隣に　草が２つ並んでいると
３つ合わせて　１つの卵　になる
という計算ルールも許容する( ﾟーﾟ)

補助線を外すと

卵　←　皿草草

じゃあ

皿草草草皿草草皿草草

は、

卵草皿草草皿草草

だな( ﾟーﾟ)

計算の優先順位を指定できるように、　波カッコを許容しよう( ﾟーﾟ)

{皿草草}草{皿草草}{皿草草}

は

卵草卵卵

だ( ﾟーﾟ)

ここで　後先考えず　適当に

草　←　草皿

と定義しよう( ﾟーﾟ)
すると

皿草草草　は　卵草
草皿草草　は　草草草

のように１文字ずれるだけで結果は異なる( ﾟーﾟ)

計算が途中ですぐ止まってしまうの
面白くないだろ

じゃあ、なるべく面白い計算ルール何か無いの？
で　一番ええ感じ　のルールが

SKIコンビネーター計算

というわけだ( ﾟーﾟ)
これに　ハスケル・カリー　という　おっさんが　はまっていたらしい( ﾟーﾟ)

導入は書いたので　あとは　勝手に調べろだぜ　寝る😪💤💤

https://twitter.com/muzudho1/status/1603765257096527872?s=20&t=WGyqSu2YgVEw1ujKdxj4GQ

計算していて面白い、
そんな計算ルールは　突き詰めると

チューリング完全

な特徴を備える(￣ー￣)

そして　SKIコンビネーター計算は
チューリング完全　な計算の中でも
特に簡単なやつ　と言われる(￣ー￣)

では、チューリング完全とは何だろうか(￣ー￣)？

計算は　大雑把にいって、次の２つのどちらかだ(￣ー￣)

開始して、いつか止まる
開始して、永遠に止まらない

どちらも計算。
これは　ハードウェアの電源を抜くと止まるという話しではなく、
計算を続けても、その計算は終わりがないという話だ(￣ー￣)

簡単なのは　割り算(￣ー￣)

例えば　100÷5 は 20
これは筆算が止まっている

例えば　100÷3 は 33.3333333
これは計算が止まらない
いい加減なところで強制終了させる指定があるはずだ(￣ー￣)

このどちらも計算だ(￣ー￣)

で、特に重要なのが

100÷3=33.33333333

を計算している途中で　何をしているのかというと、

÷３、÷３、÷３、　ということを永遠にしている。
これは　計算可能　の重要なところだ。

では、それ以外のケースは何だろうか(￣ー￣)
つまり　計算不能　とは何か(￣ー￣)

例えば

式を鉛筆で書いている途中で　ルールで定義されていない書き方が登場したというような　不備　とか、

解釈次第で　どっちとも言えるケースがあり
人によって答えが変わる　不定　とか、

そういうのがあると　計算不能だ( ﾟーﾟ)

逆説的に言うと

コンピューターにできるようなことは　計算可能だ

というか実際は

人間は頭が良すぎて、ルール上不備があることでも独自解釈して　自分の裁量で、あるいは裁量を超えてでも　やってしまう( ﾟーﾟ) これが、計算不能だ( ﾟーﾟ)

なんも頭を使わなくても　解釈に　ぶれ　も生じず　せっせと動けるようなものを　計算可能　と呼んでいる( ﾟーﾟ)

特に、

計算した結果を使って、
また次の計算ができる

これを次のように言い替える。

状態１

計算した結果は、状態２だ

状態２

計算した結果は、状態３だ( ﾟーﾟ)

これを　まとめて言うと

状態ｎ

計算した結果は、状態ｎ＋１だ

変数便利だ( ﾟーﾟ) これだと自然数の数え上げだよな( ﾟーﾟ)

その、

ｎ＋１

のとこを　どんなけ　色々書けるか、
というぐらいの違いが　計算可能　の言いたいことと言える( ﾟーﾟ)

SKIコンビネーター計算は、

その　ｎ＋１　の換わりに、
３種類の演算方法を　定義　しただけだ( ﾟーﾟ)

それを説明するのに　こんなけかかった( ﾟーﾟ)

誰も聞いてない　寝よ😪💤💤