ku-ma-me https://blog.hatena.ne.jp/ku-ma-me/ まめめも https://mametter.hatenablog.com/ Ruby クリーネの再帰定理のプログラマ向け説明（＋証明）を書いてみました。何か間違ってたら教えて！ 前提 すべてのプログラムは文字列を 1 つ入力して文字列を 1 つ出力する、という世界を考えます。なお、プログラム自体も当然文字列です。 プログラムは eval っぽい命令を使っていいことにします。つまり、プログラムpと、pへの入力文字列sを受け取って、pを実行した結果の出力文字列を返す関数 E(p, s) が利用可能です。*1 二つのプログラム p と q が完全に同じように振る舞うとき、p 〜 q と書くことにします*2。これは明らかに推移的。 定理 任意のプログラム f に対し、p 〜 E(f, … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmametter.hatenablog.com%2Fentry%2F20140207%2Fp1" title=" クリーネの再帰定理＋ Quine が書けることの証明 - まめめも" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-02-07 00:00:00 rich https://mametter.hatenablog.com/entry/20140207/p1 1.0 100%