不動点パズル06：反復（問９～問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 の反復をもたらす）

今回は、問９～11。

問９　それ自身をもたらすような 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 を見つけよ。

＊＊＊＊＊

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

（解答）
それ自身をもたらすような記号QとCから作られた記号列は、CQC である（問１参照）。
ここでは、記号Cを使わない記号列で、それ自身をもたらすものを探す。つまり、求める記号列を x とすると、

x → x　・・・・・①

となるような記号列を探す。記号Cを使わない記号列であるため、x = Rx₁とすると、①は、

Rx₁ → Rx₁　・・・・・①’

と書ける。さらに、反復のかたちに合わせるため、x₁ = x₂Rx₂ とすると、

Rx₂Rx₂ → Rx₂Rx₂　・・・・・①''

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

x₂Rx₂ → Rx₂　・・・・・②

とならなければならない。ここで、x₂ = Q とすると、②は QRQ → RQ となり、規則Qを満たす。

求める記号列は x であるため、

x = Rx₁ = Rx₂Rx₂ = RQRQ
∴それ自身をもたらす記号Cを使わない記号列は、RQRQ

＊＊＊＊＊

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

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

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

Rx → xx　・・・・・①

となる記号列 x は存在するか、という問となる。

①を満たすためには、規則Rより、

x → x　・・・・・②

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

問９や問１で求めた 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 であることは、問４で求めた。

まずは、

x → Ax　・・・・・①

となるような記号 Q、R、A だけを使った記号列 x を探していく。x は Q や A からはじまる記号列ではないため、x = Rx₁ とすると、①は、

Rx₁ → ARx₁　・・・・・①’

と書ける。反復のかたちに合わせるため、x₁ = x₂ARx₂ とすると、

Rx₂ARx₂ → ARx₂ARx₂　・・・・・①''

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

x₂ARx₂ → ARx₂　・・・・・②

とならなければならない。ここで、x₂ = Q とすると、②は QARQ → ARQ となり、規則Qを満たす。

求める記号列は x であるため、

x = Rx₁ = Rx₂ARx₂ = RQARQ
∴それ自身をもたらす記号Cを使わない記号列は、RQARQ

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

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

（つづく）