2019/08/13

不動点パズル06:反復(問9~問11の解答)

(前回はこちら

機械に、ある記号列 x を入力すると、ある記号列 y をもたらす。この機械には3つの規則(規則Q、規則C、規則R)がある。
規則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 の反復をもたらす)
今回は、問9~11。

問9 それ自身をもたらすような x があることはすでに分かっており、それは記号QとCから作られたものであった。しかし、記号Cを使わない別の記号列で、それ自身をもたらすものがある。そのような記号列を見つけよ。

問10 RQx が x の反復をもたらすことは分かっている。記号列 x で、Rx が x の反復をもたらすものは存在するだろうか。

問11 Ax をもたらす記号列 x として CQAC がある(すなわち CQAC が ACQAC をもたらす)ことは分かっている。記号 Q、R、A だけを使った別の記号列xで、Ax をもたらすものがある。このような x を見つけよ。より一般的には、任意の記号列 y に対して、記号 Q、R と y に含まれる記号だけを使った記号列 x で、yx をもたらすものが存在する。このような x を見つけよ。

*****

問9 それ自身をもたらすような x があることはすでに分かっており、それは記号QとCから作られたものであった。しかし、記号Cを使わない別の記号列で、それ自身をもたらすものがある。そのような記号列を見つけよ。

(解答)
それ自身をもたらすような記号QとCから作られた記号列は、CQC である(問1参照)。
ここでは、記号Cを使わない記号列で、それ自身をもたらすものを探す。つまり、求める記号列を x とすると、
x → x ・・・・・①
となるような記号列を探す。記号Cを使わない記号列であるため、x = Rx1とすると、①は、
Rx1 → Rx1 ・・・・・①’
と書ける。さらに、反復のかたちに合わせるため、x1 = x2Rx2 とすると、
Rx2Rx2 → Rx2Rx2 ・・・・・①''
と書ける。このとき、規則Rの条件より、
x2Rx2 → Rx2 ・・・・・②
とならなければならない。ここで、x2 = Q とすると、②は QRQ → RQ となり、規則Qを満たす。

求める記号列は x であるため、
x = Rx1 = Rx2Rx2 = RQRQ
∴それ自身をもたらす記号Cを使わない記号列は、RQRQ
*****

問10 RQx が x の反復をもたらすことは分かっている。記号列 x で、Rx が x の反復をもたらすものは存在するだろうか。

(解答)
規則Q、規則Rより、Qx → x であるので、RQx → xx は明らかである。

記号列 x で、Rx が x の反復をもたらすものは存在するだろうかという問は、
Rx → xx ・・・・・①
となる記号列 x は存在するか、という問となる。

①を満たすためには、規則Rより、
x → x ・・・・・②
とならなければならない。

問9や問1で求めた CQC や RQRQ は、それ自身をもたらす記号列であるため、②を満たす。規則R に沿った書き方をすれば、
CQC は CQC をもたらすため、RCQC は CQCCQC(CQC の反復)をもたらす。
RQRQ は RQRQ をもたらすため、RRQRQ は RQRQRQRQ(RQRQ の反復)をもたらす。
*****

問11 Ax をもたらす記号列 x として CQAC がある(すなわち CQAC が ACQAC をもたらす)ことは分かっている。記号 Q、R、A だけを使った別の記号列xで、Ax をもたらすものがある。このような x を見つけよ。より一般的には、任意の記号列 y に対して、記号 Q、R と y に含まれる記号だけを使った記号列 x で、yx をもたらすものが存在する。このような x を見つけよ。

(解答)
CQAC → ACQAC であることは、問4で求めた。

まずは、
x → Ax ・・・・・①
となるような記号 Q、R、A だけを使った記号列 x を探していく。x は Q や A からはじまる記号列ではないため、x = Rx1 とすると、①は、
Rx1 → ARx1 ・・・・・①’
と書ける。反復のかたちに合わせるため、x1 = x2ARx2 とすると、
Rx2ARx2 → ARx2ARx2 ・・・・・①''
と書ける。このとき、規則Rの条件より、
x2ARx2 → ARx2 ・・・・・②
とならなければならない。ここで、x2 = Q とすると、②は QARQ → ARQ となり、規則Qを満たす。

求める記号列は x であるため、
x = Rx1 = Rx2ARx2 = RQARQ
∴それ自身をもたらす記号Cを使わない記号列は、RQARQ

より一般的に、RQARQ の A を任意の記号列 y とした記号列 RQyRQ は、yRQyRQ をもたらす。
(QyRQ は yRQ をもたらすので、RQyRQ は、yRQyRQ(yRQ の反復)をもたらす。)

記号 Q、R と y に含まれる記号だけを使った記号列 RQyRQ を x とすると、記号列 RQyRQ は、yx をもたらしている。

つづく

0 件のコメント:

コメントを投稿

ブログ アーカイブ