不動点パズル11：未解決問題

（前回はこちら）

機械に、ある記号列 x を入力すると、ある記号列 y をもたらす。この機械には4つの規則がある。

規則Q　Qx → x
（任意の記号列 x に対して、記号列 Qx は x をもたらす）
規則C　x → y ならば、Cx → yQy
（x が y をもたらすならば、Cx は y の随伴 yQy をもたらす）
規則R　x → y ならば、Rx → yy
（x が y をもたらすならば、Rx は yy、すなわち y の反復をもたらす）
規則V　x → y ならば、Vx → y←
（x が y をもたらすならば、Vx は y の反転をもたらす）

ここでアーニー（スマリヤンの友人）は、未解決問題を提示する。未解決問題は以下のものである。

未解決問題　与えられた記号列 y に対して、xy をもたらす記号列 x が常に存在するだろうか。たとえば、xA をもたらす x が存在するだろうか。私もその答えが気になっている。これを証明または反証できた読者は、ぜひとも知らせてほしい。

このように書いているということは、証明も反証もできないのであろうが、証明も反証もできない状況というのがどのようなものなのかを感じるために、少し考えてみたい。

ここでは、xA をもたらす記号列 x について考えてみよう。

x → xA　・・・・・★

となるような記号列 x を探す。この記号列 x について、（ア）Q からはじまる記号列である場合、（イ）C からはじまる記号列である場合、（ウ）R からはじまる記号列である場合、（エ）V からはじまる記号列である場合、と分けて考えてみる。


（ア）Q からはじまる記号列である場合
x は、Q からはじまる記号列ではない。Qからはじまる記号列は、規則Q より Qx → x となり、★になることはない。

（イ）C からはじまる記号列である場合
C からはじまる記号列 x について、x = Cx₁ とすると、★は、

Cx₁ → Cx₁A　・・・・・①c

と書ける。

規則C は、Cx が y の随伴をもたらすことを言っているので、①cの Cx₁A には Q が含まれているはずである。そこで、x₁ = x₂Qx₃ とすると、①cは次のように書き換えることができる。

Cx₂Qx₃ → Cx₂Qx₃A　・・・・・①c'

さらに、①c'の Cx₂Qx₃A は随伴のかたちとならなければならないので、Cx₂ と x₃A は同じ記号列とならなければならない。そこで、Cx₂ = x₃A = CyA（つまり、x₂ = yA、x₃ = Cy）とおくと、①c'は次のように書き換えることができる。

CyAQCy → CyAQCyA　・・・・・①c"

①"が成り立つためには、規則C の条件より、

yAQCy → CyA　・・・・・②c

とならなければならない。

この先も続けるならば、CyA をもたらすような yAQCy を探していくことになるが、この場合、y が Q からはじまる場合、C からはじまる場合、……と、また繰り返すことになるので、 ここでやめておこう。

（ウ）R からはじまる記号列である場合
R からはじまる記号列 x について、x = Rx₁ とすると、★は、

Rx₁ → Rx₁A　・・・・・①r

と書ける。

規則R は、Rx が y の反復をもたらすことを言っているので、①rの Rx₁A は反復のかたちをとっているはずである。そこで、x₁ = x₂ARx₂ とすると、①rは次のように書き換えることができる。

Rx₂ARx₂ → Rx₂ARx₂A　・・・・・①r'

このとき、規則R の条件より、

x₂ARx₂ → Rx₂A　・・・・・②r

とならなければならない。

この先を続けるならば、Rx₂A をもたらすような x₂ARx₂ を探していくことになるが、この場合、y が Q からはじまる場合、C からはじまる場合、……と、また繰り返すことになるので、（イ）の場合と同じく、ここでやめておこう。

（エ）V からはじまる記号列である場合
V からはじまる記号列 x について、x = Vx₁ とすると、★は、

Vx₁ → Vx₁A　・・・・・①v

と書ける。

①v が成り立つためには、規則V の条件より、

x₁ → [Vx₁A]←　・・・・・②v

とならなければならない。②vは、反転をもたらす記号列 x₁ を示唆しているので、x₁ = Vx₂ とすると、②vは次のように書き換えることができる。

Vx₂ → [VVx₂A]←　・・・・・②v'

このとき、規則V の条件より、

x₂ → VVx₂A　・・・・・③

とならなければならない。

この先を続けるならば、VVx₂A をもたらすような x₂ を探していくことになるが、ここでも、y が Q からはじまる場合、C からはじまる場合、……と、また繰り返すことになるので、やめておこう。


xA をもたらすような記号列 x について、（ア）Q からはじまる記号列である場合、（イ）C からはじまる記号列である場合、（ウ）R からはじまる記号列である場合、（エ）V からはじまる記号列である場合、と分けて考えてみたが、（ア）以外は途中で議論をやめている。証明も、反証もしていない。続けていけば、もしかするとこのような記号列が存在するのかもしれないが、ここではわからない。逆に、このような記号列が存在しないという証明となっているわけでもない。別のやり方で証明、もしくは反証ができるのかもしれないが、ここではわかっていない。

（つづく）