「スマリヤンのゲーデル・パズル」Q70の証明 1
記号QとCだけを使った記号列で、それ自身をもたらすものはただひとつしかないことが証明できる。(以下、問題の本文)
とあります。解答ページには本文の問題だけがのっていて、引用した部分の証明はのっていません。そこで、僕が証明に挑戦するわけです。ちなみに、僕の手法はあまりエレガントではありません。
記号字数で進めてゆきます。まずは1文字の場合。
Q→
C→
ここで、「→」は「もたらす」を意味するものとします。QもCも、一文字ですと、なにももたらしません。
2文字の場合。
QQ→Q
QC→C
CQ→
CC→
どの記号列も、自身をもたらしません。
3文字の場合。
CCC→
CCQ→
CQC→CQC
CQQ→QQQ
QCC→CC
QCQ→CQ
QQC→QC
QQQ→QQ
CQCのみが、自身をもたらします。また、xを任意の記号列として、CQx→xQxであることがわかります。