不動点パズル09：反転（問17の解答）

（前回はこちら）

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

今回は問17について。説明が冗長に、わかりにくくなってしまっている。

問17　記号 Q と C だけを使った記号列で、それ自身をもたらすものはただ一つしかないことが証明できる。
(1) しかしながら、記号 Q、C、V だけを使った記号列で、それ自身をもたらすものはいくつも存在する。それは何種類あるだろうか。
(2) また、記号 Q、R、V だけを使った記号列で、それ自身をもたらすものは何種類あるだろうか。

記号 Q と C だけを使った記号列で、それ自身をもたらすものは、CQC である（問１解答参照）。しかし、問１の解答では、それ自身をもたらす記号列を作ってみたというだけで、ただ一つしかないことの証明にはなっていない。そこでまず、記号 Q と C だけを使った記号列で、それ自身をもたらす記号列は CQC ただ一つしかないことの証明を考えてみよう。

記号 Q と C だけを使った記号列で、それ自身をもたらす記号列を x とすると、

x → x　・・・・・①

となるような記号列 x を探す。

仮にこの記号列が Q からはじまる記号列だとして、x = Qy とすると、①は、

Qy → Qy

となる。これは、規則Q に反する（規則Q では、Qy → y）。よって、x は Q からはじまる記号列ではなく、C からはじまる記号列となる。

x = Cx₁ とすると、①は、

Cx₁ → Cx₁　・・・・・①’

と書ける。規則C のかたちをしているが、これを成り立たせるには、x₁ は記号 Q を含んでいなければならない。そこで、x₁ = yQz とすると、①’は、

CyQz → CyQz　・・・・・①”

と書ける。随伴のかたちとなるには、z = Cy となるため、さらに書き換えると、

CyQCy → CyQCy　・・・・・①'''

となる。このとき、規則C の条件より、

yQCy → Cy　・・・・・②

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

（y を抜いた記号列であれば、QC → C となり、規則Qを満たす。このとき、それ自身をもたらす記号列は CQC である。）

y は、Q からはじまる記号列ではないので（規則Q に反するため）、Cからはじまる記号列である。y = Cy₁ とすると、②は、

Cy₁QCCy₁ → CCy₁　・・・・・②'

と書ける。規則C のかたちをしているが、これを成り立たせるには、y₁ は記号 Q を含んでいなければならない。そこで、y₁ = z₁Qz₂ とすると、②'は、

Cz₁Qz₂QCCz₁Qz₂ → CCz₁Qz₂　・・・・・②'

と書ける。随伴のかたちとなるには、z₂ = CCz₁ となるため、さらに書き換えると、

Cz₁QCCz₁QCCz₁QCCz₁ → CCz₁QCCz₁　・・・・・②''

となる。このとき、規則C の条件より、

z₁QCCz₁QCCz₁QCCz₁ → CCz₁　・・・・・③

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

以下、同様の議論の繰り返しとなる。そのため、記号 Q と C だけを使った記号列で、それ自身をもたらす記号列は CQC 以外に求めることができない。

(1) 記号 Q、C、V だけを使った記号列で、それ自身をもたらすものはいくつも存在する。それは何種類あるだろうか。

（解答）
Q からはじまる記号列でそれ自身をもたらすものは存在せず、C からはじまる記号列でそれ自身をもたらすものは CPC ただ一つであることは先に確認した。そこでここでは、V からはじまる記号列でそれ自身をもたらすものを探す。

記号 Q、C、V だけを使った記号列で、それ自身をもたらす記号列を x とすると、

x → x　・・・・・①

となるような記号列 x を探す。

x は V からはじまる記号列であるので、x = Vx₁ とすると、①は、

Vx₁ → Vx₁　・・・・・①'

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

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

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

反転のかたちであるため、x₁ は、V からはじまる記号列となり、x₁ = Vx₂ とすると、②は、

Vx₂ → [VVx₂]←　・・・・・②

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

x₂ → VVx₂　・・・・・③

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

問４で、任意の記号列 y について、CQyC → yCQyC となることを求めた。ここで y = VV とすると、CQVVC → VVCQVVC となり、③を満たす。
したがって、求める記号列（の一つ）は、

x = Vx₁ = VVx₂ = VVCQVVC

となる。

記号列の反転について、反転の反転はもとの記号列となる。記号列 x の反転の反転は、記号列 x である。先ほど③の式を

x₂ → VVx₂　・・・・・③

としたが、たとえばここで、

x₂ → [VVx₂]←←　・・・・・④

とすることもできた。③は、反転の反転はもとの記号列であることを意識している。

仮に、④の条件ですすめていくと、x₂ が V からはじまる記号列として置き換えて、もう一度、規則V のかたち
だから、とすすめていける。

先ほどは、CQyC → yCQyC を利用して、y = VV として、VVCQVVC を求めたが、④からさらにすすめていけば、yCQyC の y が VVVV であるとき、VVVVVVであるとき、……、つまり、V が偶数個のときに、それ自身をもたらす記号列となる。V が偶数個であるというのは、記号列の反転の反転はそのままであるということと対応している。



(2) また、記号 Q、R、V だけを使った記号列で、それ自身をもたらすものは何種類あるだろうか。

（解答）
(1)での考え方と同じで、(1)では CQyC → yCQyC（記号 Q と C を使った記号列。y は偶数個の V ）を使ったが、ここでは問11で求めた RQyRQ → yRQyRQ を使う。y が偶数個の V である記号列 yRQyRQ（たとえば、VVRQVVRQ など）が、それ自身をもたらす記号列となる。

（つづく）