不動点パズル16：回文（問20～22の解答）

（前回はこちら）

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

規則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 の反転をもたらす）
規則P　x → y ならば、Px → yy←
（x が y をもたらすならば、Px は 対称記号列（回文記号列）yy← をもたらす）

回文記号列の問題は以下の3問であった。順に見てみよう。

問20　それ自身の回文 xx← をもたらすような x を見つけよ。

問21　x←x をもたらすような x を見つけよ。

問22　それ自身の随伴の回文をもたらすような記号列を見つけよ。

＊＊＊＊＊

問20　それ自身の回文 xx← をもたらすような x を見つけよ。

（解答）

x → xx←　・・・・・①

となる記号列 x を探す。

x は P からはじまる記号列となるので、x = Px₁ とすると、①は、

Px₁ → Px₁[Px₁]←　・・・・・①'

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

x₁ → Px₁　・・・・・②

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

CQyC → yCQyC の y を P とすると、CQPC → PCQPC となり、②を満たす。
求める記号列 x は、

x = Px₁ = PCQPC
∴求める記号列は、PCQPC

RQyRQ → yRQyRQ を利用した、PRQPRQ も、それ自身の回文をもたらす。

＊＊＊＊＊

問21　x←x をもたらすような x を見つけよ。

（解答）

x → x←x　・・・・・①

となる記号列 x を探す。

x を P からはじまる記号列として、x = Px₁ とすると、①は、

Px₁ → [Px₁]←Px₁　・・・・・①'

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

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

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

②は反転のかたちをしているので、x₁ = Vx₂ とすると、②は、

Vx₂ → [PVx₂]←　・・・・・②'

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

x₂ → PVx₂　・・・・・③

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

CQyC → yCQyC の y を PV とすると、CQPVC → PVCQPVC となり、②を満たす。
求める記号列 x は、

x = Px₁ = PVx₂ = PVCQPVC
∴求める記号列は、PVCQPVC

RQyRQ → yRQyRQ を利用した、PVRQPVRQ も同様に求められる。

本では、VPCQVPC が解答として掲載されている。こちらは、最初に x = Vx₁ とすることで求められる。

＊＊＊＊＊

問22　それ自身の随伴の回文をもたらすような記号列を見つけよ。

（解答）
求める記号列を x とすると、

x → xQx[xQx]←　・・・・・①

となる x を探す。

x は P からはじまる記号列となるので、x = Px₁ とすると、①は、

Px₁ → Px₁QPx₁[Px₁QPx₁]←　・・・・・①'

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

x₁ → Px₁QPx₁　・・・・・②

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

随伴のかたちをしているので、x₁ = Cx₂ とすると、②は、

Cx₂ → PCx₂QPCx₂　・・・・・②'

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

x₂ → PCx₂　・・・・・③

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

CQyC → yCQyC の y を PC とすると、CQPCC → PCCQPCC となり、②を満たす。
求める記号列 x は、

x = Px₁ = PCx₂ = PCCQPCC
∴求める記号列は、PCCQPCC

RQyRQ → yRQyRQ を利用した、PCRQPCRQ も同様に求められる。

＊＊＊＊＊

（つづく）