不動点パズル03：随伴（問４の解答）

（前回はこちら）

アーニーの機械は記号列を操作する機械で、ある記号列 x を入力すると、ある記号列 y をもたらす。いま、機械には2つの規則がある。2つの規則、規則Qと規則Cをあらためて見ておこう（「→」は「もたらす」を表す。前回参照）。

規則Q　Qx → x
（任意の記号列 x に対して、記号列 Qx は x をもたらす）
規則C　x → yならば、Cx → yQy
（x が y をもたらすならば、Cx は y の随伴 yQy をもたらす）

問題は以下の4問で、前回は問１～３について解答した。今回は問４を解いていく。

問１　それ自身をもたらすような記号列を見つけよ。
問２　それ自身の随伴をもたらすような記号列を見つけよ。
問３　それ自身の随伴の随伴をもたらすような記号列を見つけよ。
問４　任意の記号列 y に対して、ある記号列 x で、yx をもたらすようなものが存在することを証明せよ。たとえば、どのような x が Ax をもたらすだろうか。

＊＊＊＊＊

問４　任意の記号列 y に対して、ある記号列 x で、yx をもたらすようなものが存在することを証明せよ。たとえば、どのような x が Ax をもたらすだろうか。

（解答）
まずは、どのような x が Ax をもたらすかを考えよう。

x → Ax　・・・・・①

となるような記号列 x を探す。
x は、Cからはじまる記号列（QからはじまってもAxとはならない）なので、x = Cx₁ とすると、①は、

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

となる。
規則Cでは随伴をもたらすが、①’にはQの文字がない。そこで、x₁ = Qx₂ とすると、①’は、

CQx₂ → ACQx₂　・・・・・①’

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

Qx₂ → AC

でなければならない。したがって、x₂ = AC となり、

x = Cx₁ = CQx₂ = CQAC
∴CQAC は ACQAC をもたらす。

CQAC→ACQAC であるので、Aの部分を任意の記号列 y に変更した記号列 CQyC について考えると、規則Cより、

QyC → yC であるので、CQyC → yCQyC

が成り立つ。任意の記号列 y に対して、yCQyCをもたらす記号列 CQyC が存在する（CQyC を x とすると、yCQyC は yx ）。

＊＊＊＊＊

問１～４でわかったことをまとめておく。

規則CQ　CQx → xQx（ x の随伴）
（任意の記号列 x に対して、記号列 CQx は x の随伴 xQx をもたらす）
CQC は、それ自身をもたらす

規則CCQ　CCQx → xQxQxQx（ x の随伴の随伴）
（任意の記号列 x に対して、記号列 CCQx は x の随伴の随伴をもたらす）　
CCQCC は、それ自身の随伴をもたらす

規則CCCQ　CCCQx → xQxQxQxQxQxQxQx（ x の随伴の随伴の随伴）
（任意の記号列 x に対して、記号列 CCCQx は x の随伴の随伴の随伴をもたらす）
CCCQCCC は、それ自身の随伴の随伴をもたらす

規則CQ-C　CQyC → yCQyC
（任意の記号列 y に対して、記号列 CQyC は yCQyC をもたらす）

（つづく）