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

「スマリヤンのゲーデル・パズル」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であることがわかります。
by tomoarrow | 2015-08-04 07:00 | モチーフについて | Comments(0)