2019/08/23

不動点パズル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 xx をもたらすような x を見つけよ。

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

*****

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

(解答)
x → xx ・・・・・①
となる記号列 x を探す。

x は P からはじまる記号列となるので、x = Px1 とすると、①は、
Px1 → Px1[Px1] ・・・・・①'
と書ける。このとき、規則P の条件より、
x1 → Px1 ・・・・・②
とならなければならない。

CQyC → yCQyC の y を P とすると、CQPC → PCQPC となり、②を満たす。
求める記号列 x は、
x = Px1 = PCQPC
∴求める記号列は、PCQPC
RQyRQ → yRQyRQ を利用した、PRQPRQ も、それ自身の回文をもたらす。

*****

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

(解答)
x → xx ・・・・・①
となる記号列 x を探す。

x を P からはじまる記号列として、x = Px1 とすると、①は、
Px1[Px1]Px1 ・・・・・①'
と書ける。このとき、規則P の条件より、
x1[Px1] ・・・・・②
とならなければならない。

②は反転のかたちをしているので、x1 = Vx2 とすると、②は、
Vx2[PVx2] ・・・・・②'
と書ける。このとき、規則V の条件より、
x2 → PVx2 ・・・・・③
とならなければならない。

CQyC → yCQyC の y を PV とすると、CQPVC → PVCQPVC となり、②を満たす。
求める記号列 x は、
x = Px1 = PVx2 = PVCQPVC
∴求める記号列は、PVCQPVC
RQyRQ → yRQyRQ を利用した、PVRQPVRQ も同様に求められる。

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

*****

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

(解答)
求める記号列を x とすると、
x → xQx[xQx] ・・・・・①
となる x を探す。

x は P からはじまる記号列となるので、x = Px1 とすると、①は、
Px1 → Px1QPx1[Px1QPx1] ・・・・・①'
と書ける。このとき規則P の条件より、
x1 → Px1QPx1 ・・・・・②
とならなければならない。

随伴のかたちをしているので、x1 = Cx2 とすると、②は、
Cx2 → PCx2QPCx2 ・・・・・②'
と書ける。このとき規則C の条件より、
x2 → PCx2 ・・・・・③
とならなければならない。

CQyC → yCQyC の y を PC とすると、CQPCC → PCCQPCC となり、②を満たす。
求める記号列 x は、
x = Px1 = PCx2 = PCCQPCC
∴求める記号列は、PCCQPCC
RQyRQ → yRQyRQ を利用した、PCRQPCRQ も同様に求められる。

*****

つづく

0 件のコメント:

コメントを投稿

ブログ アーカイブ