2022-12-17に更新

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

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

#プログラミング 

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

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

何か関係あんの? というと 似たようなもので 違うもの( ̄ー ̄)
仮に 卵 という字の右側に 卵 が並ぶと、2つ合わせて 鶏 になるというルールがあるとしよう( ̄ー ̄)

卵

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

卵卵

なら、

鶏

になる( ̄ー ̄)
卵草卵卵

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

右に2つの卵が並んでいるが、
それを先に計算するようなルールは無いので
計算しない( ̄ー ̄)
じゃあ 卵の右隣に草が来たら 2つ合わせて1つの卵にしようぜ?

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

卵草卵卵

は、

卵卵卵

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

卵卵卵

なら、

鶏卵

になるな( ̄ー ̄)
鶏の右隣に卵が並んだときの計算は定義されていないので、
これで計算は終了だぜ( ̄ー ̄)
じゃあ 鶏の右隣に卵が来たら 2つ合わせて 草にしようぜ?

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

鶏卵

なら、

草

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

卵草卵卵

は、最終的には

草

になるわけだぜ( ゚ー゚)
このとき、登場した 卵、草、鶏を
卵コンビネーター、
草コンビネーター、
鶏コンビネーター
という( ゚ー゚)
モイセイ・シェインフィンケリという おっさん が、

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

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

の計算ルールを定義した( ゚ー゚)
だが お前らは アルファベットを見ると眠くなって寝てしまうので

S、K、I 以外の話をする( ゚ー゚)
例えば、計算ルールの定義を
次のように書くとしよう

鶏 ← 卵卵

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

ということを表した書き方と、ここで勝手に決めた( ゚ー゚)
ここで、現代風に 補助線を引くとしよう( ゚ー゚)

鶏 ← 卵卵

は、

鶏 ← 卵(卵)

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

これは現代で言う 関数 の、祖先にあたる( ゚ー゚)
じゃあ、 卵が関数名なら、

卵(卵)

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

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

良いのだ( ゚ー゚)

これを現代で言うと 関数も第一級のオブジェクト という( ゚ー゚)
計算は左から始めるというのを 左結合 という

卵草卵卵

に補助線を引くと

{{{卵草}卵}卵}

で、内側の波カッコから計算する( ゚ー゚)
{{{卵草}卵}卵}

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

卵(草)(卵)(卵)

何も嬉しくないやんけ! と思うかも知れないが
補助線の引き方の一例だ( ゚ー゚)
こんな話 もう眠い と思うやつが

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

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

そのようなレベルの話をするやつ
よほど ヒマ人( ̄ー ̄)
次に 皿コンビネーター を新しく定義してみよう

卵 ← 皿(草草)

皿の右隣に 草が2つ並んでいると
3つ合わせて 1つの卵 になる
という計算ルールも許容する( ゚ー゚)

補助線を外すと

卵 ← 皿草草
じゃあ

皿草草草皿草草皿草草

は、

卵草皿草草皿草草

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

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

は

卵草卵卵

だ( ゚ー゚)
ここで 後先考えず 適当に

草 ← 草皿

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

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

のように1文字ずれるだけで結果は異なる( ゚ー゚)
計算が途中ですぐ止まってしまうの
面白くないだろ

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

SKIコンビネーター計算

というわけだ( ゚ー゚)
これに ハスケル・カリー という おっさんが はまっていたらしい( ゚ー゚)
導入は書いたので あとは 勝手に調べろだぜ 寝る😪💤💤

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

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

チューリング完全

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

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

では、チューリング完全とは何だろうか( ̄ー ̄)?
計算は 大雑把にいって、次の2つのどちらかだ( ̄ー ̄)

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

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

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

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

このどちらも計算だ( ̄ー ̄)
で、特に重要なのが

100÷3=33.33333333

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

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

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

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

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

そういうのがあると 計算不能だ( ゚ー゚)
逆説的に言うと

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

というか実際は

人間は頭が良すぎて、ルール上不備があることでも独自解釈して 自分の裁量で、あるいは裁量を超えてでも やってしまう( ゚ー゚) これが、計算不能だ( ゚ー゚)
なんも頭を使わなくても 解釈に ぶれ も生じず せっせと動けるようなものを 計算可能 と呼んでいる( ゚ー゚)
特に、

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

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

状態1

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

状態2

計算した結果は、状態3だ( ゚ー゚)
これを まとめて言うと

状態n

計算した結果は、状態n+1だ

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

n+1

のとこを どんなけ 色々書けるか、
というぐらいの違いが 計算可能 の言いたいことと言える( ゚ー゚)
SKIコンビネーター計算は、

その n+1 の換わりに、
3種類の演算方法を 定義 しただけだ( ゚ー゚)

それを説明するのに こんなけかかった( ゚ー゚)
誰も聞いてない 寝よ😪💤💤
ツイッターでシェア
みんなに共有、忘れないようにメモ

むずでょ

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

有料記事を販売できるようになりました!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?

コメント