クリーネの再帰定理＋ Quine が書けることの証明 - まめめも
クリーネの再帰定理のプログラマ向け説明（＋証明）を書いてみました。何か間違ってたら教えて！ 前提 すべてのプログラムは文字列を 1 つ入力して文字列を 1 つ出力する、という世界を考えます。なお、プログラム自体も当然文字列です。 プログラムは eval っぽい命令を使っていいことにします。つまり、プログラムpと、pへの入力文字列sを受け取って、pを実行した結果の出力文字列を返す関数 E(p, s) が利用可能です。*1 二つのプログラム p と q が完全に同じように振る舞うとき、p 〜 q と書くことにします*2。これは明らかに推移的。 定理 任意のプログラム f に対し、p 〜 E(f, p) となるようなプログラム文字列 p が存在する。*3 定理の証明 以下のような 3 つの文字列を考えます。 h: 入力文字列 x に対し、E(x, x) の結果を出力するプログラム*4 e: 入力
Merry Quine-mas 2012 - まめめも
今夜は、年に一度の W. V. Quine の命日イブです。(もう日が変わってますが) %;';;eval$s=%q{eval(%w~i=1;T="$)*L)L)))0)E(E(0(7(>'>'7&E&0&7&>%L%)%0%E*)$L$)* L)L)))0 )E(E(0(7(>' >'7&E&0&7&>%L%)%0%E5&$L%#8C5G7/530L2B1*/'19-D03 #E*&,1). *G'6#3*>5 &'F'#)E(L)0*)'L'?(#)#)7(E'0&E&#(0%0&L%7&0':+)%E# {"4F"*18} 3F4F5F4 F4@493@1@5@7@6@692@2939325952425+4+3+3F4$5F4F".by tes.each_s lice( 2).map{|s,c|[s*3-99,c/7*3-13-i=-i,c%7+41]};$><<"'# {e=27.
山手 quine - まめめも
t="+,m-n./mAm0o1p23a4q56r7sBt89u-t-1:v;A<w4x=y1z>[?]A^@CD_ CD_EsF`GHmIJbKa*l";eval$s=%w{F=%q{ceY8#<DvO1=x&t9CSOqMYkzH U.kCpz+Vo8hB.1AF&tq21+$/IrMY]U.aDd!-1y!4MMGQm6m?bYh($QMYpX s4g,x1UlbNKH?>NzbisMn?sT@m3,F.Abb`xW!r%'%Ybee>xkUfjf[(*^Nd Xo_"@hQh%Fx*q[iB7EM"suSG8GVOIzceg/O=4CL,d[-k]twgVP`&wcfaT` 2M)j8sFY?(HKzOrVCHO_694[Uq8g @i/i;tMBG#;-;B]rV[])`3'<os^. OV(SA<=ok%m[iV#qt[&dJ7SIdB;/ VUnVIrH;hEJ*QWD"E+
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
