人気ブログランキング | 話題のタグを見る

「スマリヤンのゲーデル・パズル」Q70の証明 3

Cの定義より、

[ ]→x
ならば
C[ ]→xQx

なので、

[ ]→y
yが[ ]よりも長い記号列ならば、
C[ ]→yQy
の右辺は、[ ]よりも長い記号列になります。ここで、

C[ ]とyQyが異なることが示されました。(ただしCQCの場合を除く)

C[C・・C[ ]]→[C・・C[ ]]Q[C・・C[ ]]


この場合、両辺は異なると仮定します(数学的帰納法)。さて、Cをもうひとつ増やすと

C[C[C・・C[ ]]]→[C[C・・C[ ]]]Q[C[C・・C[ ]]]


となり、この両辺も異なります。ゆえに、CとQのみを使った記号列で、自らをもたらす記号列はCQCのみであることが証明できました。

いやあ、長くて非エレガントですね。もっと簡潔に書けるといいのですが、僕にはこれが限界です。
by tomoarrow | 2015-08-06 07:00 | モチーフについて | Comments(0)