不動点パズル10：反転（問18の解答）

（前回はこちら）

機械に、ある記号列 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 の反転をもたらす）

今回は、問18を解いていく。


問18　任意の記号列 y に対して、ある記号列 x で、x←y をもたらすものが存在することを証明せよ。たとえば、どのような記号列 x が x←JKL をもたらすだろうか。

（解答）
まずは、x←JKL をもたらす記号列 x を探していこう。

求める記号列 x は、x←JKL をもたらすので、

x → x←JKL　・・・・・①

を満たす。

反転のかたちがあるので、x は V からはじまる記号列として、x = Vx₁ とすると、①は、

Vx₁ → [Vx₁←]JKL　・・・・・①'

と書ける。このとき、規則V の条件より、

x₁ → LKJVx₁　・・・・・②

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

問４より、CQyC → yCQyC であるので、この y = LKJV とすると、CQLKJVC → LKJVCQLKJVC が成り立ち、これは②の x₁ を x₁ = CQLKJVC としたときに一致する。

したがって、求める記号列は VCQLKJVC である。
（問９で求めた、RQyRQ → yRQyRQ を利用した VRQLKJVRQ も解答となる。）

いまの結果をあらためて規則V に沿ったかたちで明示的に書くと、「CQLKJVC は LKJVCQLKJVC をもたらすので、VCQLKJVC は CVJKLQCVJKL をもたらす」、つまり、

CQLKJVC → LKJVCQLKJVC であるので、
VCQLKJVC → CVJKLQCVJKL　・・・・・③

ここで、記号列JKL を z とすると、LKJ は z← となり、③は、

CQz←VC → z←VCQz←VC であるので、VCQz←VC → CVzQCVz　・・・・・③'

と書ける。CQz←VC → z←VCQz←VC は z がどのような記号列であっても成り立つ（CQyC → yCQyC の y を z←V としたもの）。また、VCQz←VC → CVzQCVz の CVzQCVz　は、VCQz←VC の反転に、任意の記号列 z を続けたものである。

したがって、任意の記号列 y に対して、x←y をもたらすものが存在し、その記号列に VCQy←VC がある。
（VRQy←VRQ も、任意の記号列 y に対して、x←y をもたらす記号列である。）

（つづく）