不動点パズル26：二重不動点原理の導出（３）

（前回はこちら）

問28　任意の記号列 z₁ と z₂ に対して、y₁ は z₁y₂ をもたらし、y₂ は z₂y₁ をもたらすような記号列 y₁、y₂ が存在することを示せ。たとえば、y₁ が Ay₂ をもたらし、y₂ は By₁ をもたらすような記号列 y₁、y₂ は何か。


（解答）
まずは、y₁ が Ay₂ をもたらし、y₂ は By₁ をもたらすような記号列 y₁、y₂ を求めることからはじめていく。

y₁ が Ay₂ をもたらし、y₂ は By₁ をもたらすので、これまでと同様に式で表してみると、

y₁ → Ay₂　・・・・・①
y₂ → By₁　・・・・・②

となる。

ところで、以前問題27において、規則Q と C だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列 QCQQC と CQQC を見つけた（参照「不動点パズル24」）。Q からはじまる記号列が C からはじまる記号列をもたらし、C からはじまる記号列が Q からはじまる記号列をもたらすようなものを探す際、CQzC が zCQzC をもたらすことを利用して解答を求めた。今回も同じようにできないかを考えてみる。

求める記号列の片方を Q からはじまる記号列となるようにしたい。ここでは y₁ を Q からはじまる記号列とする。y₁ = Qz₁ とすると、①、②は以下のようになる。

Qz₁ → Ay₂　・・・・・①'
y₂ → BQz₁　・・・・・②'

①'において、規則Q より、z₁ = Ay₂ となる。これをあらためて①'、②'にあてはめると、

QAy₂ → Ay₂　・・・・・①"
y₂ → BQAy₂　・・・・・②"

となる。

②"において、CQzC が zCQzC をもたらすことを利用することができる。すなわち、z を BQA とすると、CQBQAC は BQACQBQAC をもたらすので、y₂ は、CQBQAC と求めることができる。このとき、y₁ は、

y₁ = Qz₁ = QAy₂ = QACQBQAC

つまり、y₁ が Ay₂ をもたらし、y₂ は By₁ をもたらすような記号列 y₁、y₂ として、QACQBQAC と CQBQAC がある。

同様のやり方で、任意の記号列 z₁ と z₂ に対して、y₁ は z₁y₂ をもたらし、y₂ は z₂y₁ をもたらすような記号列 y₁、y₂ を求めることができる。上記の A、B を、z₂、z₁ とした記号列 Qz₂CQz₁Qz₂C と CQz₁Qz₂C が該当の記号列である。


さて、次の問題が、アーニーの二重不動点原理の証明である。

問29　アーニーの二重不動点原理を証明せよ。

（つづく）

不動点パズル25：二重不動点原理の導出（２）

（前回はこちら）

前回、アーニーの「二重不動点原理」の証明のガイドとして、問題をひとつ解いた。以下の問27がその問題である。

問27　規則Q と C だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列を見つけよ。

この問題を解くことで、このような記号列として、QCQQC と CQQC があることを確認した。

そして、アーニーの「二重不動点原理」の証明のガイドのために、次の問題が出された。

問28　任意の記号列 z₁ と z₂ に対して、y₁ は z₁y₂ をもたらし、y₂ は z₂y₁ をもたらすような記号列 y₁、y₂ が存在することを示せ。たとえば、y₁ が Ay₂ をもたらし、y₂ は By₁ をもたらすような記号列 y₁、y₂ は何か。

この問題を解くことで、二重不動点原理を簡単に説明することができるようになるという。まずは、y₁ が Ay₂ をもたらし、y₂ は By₁ をもたらすような記号列 y₁、y₂ を求めることからはじめていこう。

（つづく）

不動点パズル24：二重不動点原理の導出（１）

（前回はこちら）

機械に、ある記号列を入力すると、ある記号列をもたらす。この機械には規則がある。規則Q と C を再掲しておく。

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

この機械（処理系）において、アーニーは、「すべての特殊記号列Θは不動点をもつ」という。これを「アーニーの不動点原理」という。

特殊記号列
記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列を呼ぶ。

不動点
x がΘ(x) をもたらすならば、x をΘの不動点という。

さらに、アーニーは、二重不動点原理を持ち出した。

二重不動点原理
任意の特殊記号列Θ₁ とΘ₂ に対して、x がΘ₁(y) をもたらし、y がΘ₂(x) をもたらすような記号列 x と y が存在する。

この「アーニーの二重不動点原理」を証明することが目標である。

そのためのガイドとして、以下の問題があった。今回はこの問題について考える。
問27　規則Q と C だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列を見つけよ。


（解答）
それぞれが互いにもう一方をもたらすような二つの相異なる記号列を x、y とし、

x → y　・・・・・①
y → x　・・・・・②

となるような記号列 x、y を探す。

このとき、記号列 x、y は、どちらかが Q からはじまる記号列で、もう片方は C からはじまる記号列であると考えられる。なぜなら、両方とも同じ記号からはじまる記号列であると、規則の性質上、互いにもう一方をもたらす相異なる記号列は存在しないからである（これにも証明が必要かもしれないがここでは省略する）。

そこで、x = Qx₁、y = Cy₁ と考えると、

Qx₁ → Cy₁　・・・・・①'
Cy₁ → Qx₁　・・・・・②'

となるような記号列を探すことになる。

②'において、CQzC → zCQzC が使えそうである。この z を Q とすると、CQQC → QCQQC がいえる。QCQQC は CQQC をもたらすので、①'も満たす。

よって、規則Q と C だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列に、QCQQC と CQQC がある。

（つづく）

不動点パズル23：二重不動点原理（試行錯誤）

（前回はこちら）

アーニーは、二重不動点原理がわかっていれば、次の問題が解けるという。

二重不動点原理
任意の特殊記号列Θ₁ とΘ₂ に対して、x がΘ₁(y) をもたらし、y がΘ₂(x) をもたらすような記号列 x と y が存在する。

問26　二つの記号列 x と y で、x は y の反復をもたらし、y は x の反転をもたらすようなものを見つけよ。

現時点では、二重不動点原理がわかっていない状態なので、問26は解けない可能性が高い。しかし、わからないかもしれないが、まずはやってみよう。


（試行錯誤）
これまでと同様のやり方でやってみる。

二つの記号列 x と y で、x は y の反復をもたらし、y は x の反転をもたらすので、

x → yy　・・・・・①
y → x←　・・・・・②

を満たす x と y を探す。

①は反復のかたちをしているので x = Rx₁、②は反転のかたちをしているので y = Vy₁ とすると、①②はそれぞれ、

Rx₁ → Vy₁Vy₁　・・・・・①'
Vy₁ → [Rx₁]←　・・・・・②'

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

x₁ → Vy₁　・・・・・③
y₁ → Rx₁　・・・・・④

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

さて、ここからどうするか……。一旦ここでやめておこう。

総当りで探す手はあるが、『スマリヤンのゲーデル・パズル』の本には二重不動点原理の導出のガイドとなる問題が出ているので、それらを順に解いていこう。

そのガイドとなる問題は以下である。

問27　規則Q と C だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列を見つけよ。

（つづく）

不動点パズル22：二重不動点原理（プロローグ）

（前回はこちら）

アーニーが作った機械は記号列を操作する機械で、その機械にはいくつかの規則があるが、そこには「不動点原理」が存在することがわかった。

不動点原理
すべての特殊記号列Θは不動点をもつ。

特殊記号列
記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列を呼ぶ。

不動点
x がΘ(x) をもたらすならば、x をΘの不動点という。

さらに規則を追加して、より多くの記号列が特殊記号列になったとしても、不動点原理は成り立つ。機械（処理系）に規則Q と C があれば、そのほかにどんな規則があっても、不動点原理に従う。また、処理系に規則Q と 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 の反復をもたらす）

アーニーはさらに、「二重不動点原理」があるという。

二重不動点原理
任意の特殊記号列Θ₁ とΘ₂ に対して、x がΘ₁(y) をもたらし、y がΘ₂(x) をもたらすような記号列 x と y が存在する。

この二重不動点原理がわかっていれば、次の問題が解けるという。

問26　二つの記号列 x と y で、x は y の反復をもたらし、y は x の反転をもたらすようなものを見つけよ。

現時点では、二重不動点原理がわかっていない状態なので、問26は解けない可能性が高い。しかし、わからないかもしれないが、まずはやってみよう。

（つづく）

不動点パズル21：不動点原理

（前回はこちら）

アーニーは、「すべての特殊記号列Θは不動点をもつ」という。これを「アーニーの不動点原理」という。

特殊記号列
記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列を呼ぶ。

不動点
x がΘ(x) をもたらすならば、x をΘの不動点という。

そして、この不動点原理は、

「さらに規則を追加して、より多くの記号列が特殊記号列になったとしても、不動点原理は依然として成り立つ。処理系に規則Q と C があれば、そのほかにどんな規則があっても、この原理に従う。また、処理系に規則Q と R があれば、そのほかにどんな規則があっても、この原理に従う。すなわち、任意の特殊記号列Θに対して、記号Q と C にくわえてΘに含まれる記号だけ、または記号Q と R にくわえてΘに含まれる記号だけを使ったΘの不動点が存在する」

という。

今回の問題は、その不動点原理の証明である。

問25　アーニーの不動点原理を証明せよ。与えられた特殊記号列Θに対して、そのΘの不動点となる記号列を見つけよ。これには2種類の解がある。一つは、記号Q と C、そしてΘに含まれる記号だけを使うもので、もう一つは、記号Q と R、そしてΘに含まれる記号だけを使うものだ。

（解答）
これまで問題を解いてきて、よく使った記号列があった。それは、CQyC と RQyRQ である。CQyC は yCQyC をもたらし、RQyRQ は yRQyRQ をもたらす。ともに、x → yx となるような記号列で、CQyC は、記号Q と C、そして y に含まれる記号だけを使った記号列であり、RQyRQ は、記号Q と R、そして y に含まれる記号だけを使った記号列である。おそらくはこれらを使うことになるだろう。

また、話が前後してしまうが、特殊記号列についてあらためて確認しておこう。これまでに見た規則をあらためて確認すると、規則Q、C、R は以下である。

規則Q　任意の記号列 x に対して、記号列 Qx は x をもたらす
規則C　x が y をもたらすならば、Cx は y の随伴 yQy をもたらす
規則R　x が y をもたらすならば、Rx は y の反復 yy をもたらす

特殊記号列について確認したときに、規則Q と規則C から以下のことがいえるとした。

任意の記号列 x に対して、CQx は C(x)（すなわち xQx）をもたらす

C の不動点は、CCQCC である（「不動点パズル02」問２参照）。

同様に、規則Q と規則R からは、

任意の記号列 x に対して、RQx は R(x)（すなわち、xx）をもたらす

といえる。R の不動点は、RCQRC である（「不動点パズル05」問５参照）。

同様の表現で特殊記号列Θについて述べると、

任意の記号列 x に対して、ΘQx は Θ(x) をもたらす

といえる。ならば、Θの不動点は、ΘCQΘC となるのではないか。

と、まあ、ここまでは証明ではなく、単なる予想である。

さて、特集記号列は「記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす」という性質をもつ。ここで、ある記号列 y をΘ(x) と表すことにしている。この性質から、規則C や 規則R のような表現にすることも可能である。（便宜上、「規則Θ」と名付ける。）

規則Θ　z が x をもたらすならば、Θz はΘ(x) をもたらす

問いは、アーニーの不動点原理を証明することであった。与えられた特殊記号列Θに対して、そのΘの不動点となる記号列を見つけるということである。

これまでと同じようなやり方でやってみよう。

求める記号列（Θの不動点）を x とする。不動点の定義より、

x → Θ(x)　・・・・・①

となる記号列をさがす。

規則Θを使うため、x はΘからはじまる記号列として、x = Θz とすると、①は、

Θz → Θ(Θz)　・・・・・①'

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

z → Θz　・・・・・②

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

ここで、CQyC → yCQyC の y をΘとすると、CQΘC → ΘCQΘC で、②を満たす。このとき z = CQΘC である。

したがって、求める記号列 x は、

x = Θz = ΘCQΘC
∴特殊記号列Θに対して、そのΘの不動点 ΘCQΘC が存在する

同様に、RQyRQ → yRQyRQ を使うと、ΘRQΘRQ が得られる。

（つづく）

不動点パズル20：不動点

（前回はこちら）

さて、いよいよ「不動点」の登場である。アーニーの言葉を引用しよう。

「よろしい。ここで、x がΘ(x) をもたらすならば、x をΘの不動点という。ここまでに出題した問題の多くは、不動点を見つけるという問題の単なる言い換えにすぎない。……（中略）……。しかしながら、これらをすべてひとまとめにして一般化できるのだ」

不動点原理　すべての特殊記号列Θは不動点をもつ。

これまでの問題には、次のような問題があった。たとえば、問２は、

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

というものである。

これを僕は「x → xQx となるような記号列 x を探す」というように解いていった。前回、特殊記号列のところで、Θ(x) という表記を見たが、それを使うと、「x → C(x) となるような記号列 x を探す」と言い換えることができる。C(x) をもたらす x を探すというのは、「C の不動点を見つける」ということの言い換えにすぎない。問３の「それ自身の随伴の随伴をもたらすような記号列を見つけよ」は、「CC の不動点を見つけよ」ということだし、「それ自身の随伴の反転の反復をもたらすような記号列を見つけよ（問16）」は、「RVC の不動点を見つけよ」ということである。

そして、アーニーの不動点原理は「すべての特殊記号列Θは不動点をもつ」という。

「さらに規則を追加して、より多くの記号列が特殊記号列になったとしても、不動点原理は依然として成り立つ。処理系に規則Q と C があれば、そのほかにどんな規則があっても、この原理に従う。また、処理系に規則Q と R があれば、そのほかにどんな規則があっても、この原理に従う。すなわち、任意の特殊記号列Θに対して、記号Q と C にくわえてΘに含まれる記号だけ、または記号Q と R にくわえてΘに含まれる記号だけを使ったΘの不動点が存在する」

問25　アーニーの不動点原理を証明せよ。与えられた特殊記号列Θに対して、そのΘの不動点となる記号列を見つけよ。これには2種類の解がある。一つは、記号Q と C、そしてΘに含まれる記号だけを使うもので、もう一つは、記号Q と R、そしてΘに含まれる記号だけを使うものだ。

（つづく）

不動点パズル19：特殊記号列

（前回はこちら）

さて、ここからが、しっかりと理解したいところだ。

『スマリヤンのゲーデル・パズル』のなかで、アーニーはまず、特殊記号列について説明している。

「記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列と呼ぶことにする。したがって、どの特殊記号列Θも、y₁ と y₂ が同じ記号列をもたらすならば、Θy₁ とΘy₂ は同じ記号列をもたらす。記号C、R、V だけから作られた任意の記号列は、どれも特殊記号列になる。任意の特殊記号列Θと任意の記号列 x に対して、ΘQx がもたらす（または x をもたらす任意の記号列 y に対してΘy がもたらす）記号列をΘ(x)で表す。たとえば、（RQx は xx をもたらすので）R(x) は x の反復になる。また、V(x) は x の反転、C(x) は x の随伴 xQx、RC(x) は x の随伴の反復、CV(x) は x の反転の随伴になる。ここまではいいかね」

うん。よくない。

しかし、まったくわからないというわけではない。何となくわかるような、わからないようなという感じである。こんなときは、ゆっくりじっくり確認していくことだ。

このなかでわかっていない感が一番強いところは、特殊記号列の性質のところである。なので、後回しにして、まずは具体例から見ていきたいと思う。

任意の特殊記号列Θと任意の記号列 x に対して、ΘQx がもたらす（または x をもたらす任意の記号列 y に対してΘy がもたらす）記号列をΘ(x)で表す。たとえば、（RQx は xx をもたらすので）R(x) は x の反復になる。また、V(x) は x の反転、C(x) は x の随伴 xQx、RC(x) は x の随伴の反復、CV(x) は x の反転の随伴になる。

ここで書かれていることを別の言葉でいえば、たとえば、xx（x の反復）を R(x) と表現しよう、ということである。

これまでの規則をあらためて書いておこう。

規則Q　Qx → x
（任意の記号列 x に対して、記号列 Qx は x をもたらす）
規則C　x → y ならば、Cx → yQy
（x が y をもたらすならば、Cx は y の随伴 yQy をもたらす）
規則R　x → y ならば、Rx → yy
（x が y をもたらすならば、Rx は y の反復 yy をもたらす）
規則V　x → y ならば、Vx → y←
（x が y をもたらすならば、Vx は y の反転 y← をもたらす）
規則P　x → y ならば、Px → yy←
（x が y をもたらすならば、Px は y の回文 yy← をもたらす）
規則M　x → y ならば、Mx → y●
（x が y をもたらすならば、Mx は y● をもたらす）

規則Q と 規則R から次のことがいえる。

Qx は x をもたらすので、RQx は xx をもたらす。

R(x) を使って表現すると、

Qx は x をもたらすので、RQx は R(x) をもたらす。

ということである。

規則Q は、任意の記号列 x に対して成り立つ。つまり、

任意の記号列 x に対して、RQx は R(x) をもたらす。

ということである。

ここで、R をΘと置き換えると、

任意の記号列 x に対して、ΘQx は Θ(x) をもたらす。

「任意の特殊記号列Θと任意の記号列 x に対して、ΘQx がもたらす記号列をΘ(x)で表す」というのは、こういうことだ。

では、特殊記号列の性質について、だ。

「記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列と呼ぶことにする。したがって、どの特殊記号列Θも、y₁ と y₂ が同じ記号列をもたらすならば、Θy₁ とΘy₂ は同じ記号列をもたらす。記号C、R、V だけから作られた任意の記号列は、どれも特殊記号列になる」

一文ずつ区切ってみよう。

「記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列と呼ぶことにする」

少し入り組んだ表現であるので、骨格を明確にして、これまでと同じように、「もたらす」を記号「→」で表現すると、

・ΘQx → y（記号列ΘQx がある記号列 y をもたらす）
・z → x ならば、Θz → y（z が x をもたらすならば、Θz は y をもたらす）

この2つが成り立つ記号列Θのことを特殊記号列と呼ぼうと言っている。

何か具体例がほしい。そこで、これまでの問題を見直していると、問10（「不動点パズル06」参照）がよさそうだ。問10では、記号列 x で、Rx が x の反復をもたらす記号列として、CQC と RQRQ を挙げていて、具体例としてあてはめることができそうだ。

特殊記号列Θを R として、先ほどの特殊記号列の性質にあてはめると、

・RQx → xx
・z → x ならば、Rz → xx

たとえば、x = CQC で見ると、

・RQCQC → CQCCQC
・z → CQC ならば、Rz → CQCCQC

CQC は、それ自身をもたらす記号列であるので、z = CQC とすることができる。

・RQCQC → CQCCQC
・CQC → CQC ならば、RCQC → CQCCQC

これを特殊記号列の性質の言葉どおりに書くと、『記号列 RQCQC が記号列 CQCCQC をもたらすならば、CQC をもたらす 記号列 CQC に対しても、RCQC は RQCQC と同じく CQCCQC をもたらす』ということになる。

具体例があることで、少しイメージがつかめたような気がする。

次は、特殊記号列の性質からあきらかである。

「したがって、どの特殊記号列Θも、y₁ と y₂ が同じ記号列をもたらすならば、Θy₁ とΘy₂ は同じ記号列をもたらす」

さて、その次はどうだろうか。

「記号C、R、V だけから作られた任意の記号列は、どれも特殊記号列になる」

たとえば、記号P や M から作られた記号列は特殊記号列にはなりえないのだろうか。この点に関しては、まだ考えていない。

（つづく）

不動点パズル18：移動（問24の解答）

（前回はこちら）

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

規則Q　Qx → x
（任意の記号列 x に対して、記号列 Qx は x をもたらす）
規則C　x → y ならば、Cx → yQy
（x が y をもたらすならば、Cx は y の随伴 yQy をもたらす）
規則R　x → y ならば、Rx → yy
（x が y をもたらすならば、Rx は y の反復 yy をもたらす）
規則V　x → y ならば、Vx → y←
（x が y をもたらすならば、Vx は y の反転 y← をもたらす）
規則P　x → y ならば、Px → yy←
（x が y をもたらすならば、Px は y の回文 yy← をもたらす）
規則M　x → y ならば、Mx → y●
（x が y をもたらすならば、Mx は y● をもたらす）

x● は、記号列 x の先頭の記号を末尾に移した記号列を意味する。記号列が1文字だけの記号の場合には、x● は x そのものとする。

今回は、問24について。

問24　任意の記号列 y に対して、規則Q、C、R、V だけを使った記号列 x で xy をもたらすものがあるかどうかは未解決問題だとすでに述べた（「不動点パズル11：未解決問題」参照）。しかし、規則M を追加すると、任意の記号列 y に対して、記号列 x が xy をもたらすような x を比較的簡単に見つけることができる。それは、どのようにすればよいだろうか。たとえば、x が xJKL をもたらすような x を見つけよ。

（解答）
まずは、xJKL をもたらすような x を探す。

x → xJKL　・・・・・①

規則Q、C、R、V だけを使った記号列 x で xy をもたらすものがあるかどうかは未解決問題であったため、規則M を使えるように、x を M からはじまる記号列として考えていこう。x = Mx₁ とすると、①は、

Mx₁ → Mx₁JKL　・・・・・①'

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

x₁ → LMx₁JK　・・・・・②

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

ここで、x₁ = Mx₂ とすると、②は、

Mx₂ → LMMx₂JK　・・・・・②'

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

x₂ → KLMMx₂J　・・・・・③

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

同様に、x₂ = Mx₃ とすると、③は、

Mx₃ → KLMMMx₃J　・・・・・③'

規則M の条件より、

x₃ → JKLMMMx₃　・・・・・④

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

CQyC → yCQyC の y を JKLMMM としたとき、④を満たす。このとき、x₃ = CQJKLMMMC である。したがって、xJKL をもたらすような記号列 x は、

x = Mx₁ = MMx₂ = MMMx₃ = MMMCQJKLMMMC
∴xJKL をもたらすような記号列 x は、MMMCQJKLMMMC

これを一般的にして、xy をもたらすような記号列 x を考えてみよう。

さきほどの x → xJKL のときに使った規則をならべて書いてみると、

CQJKLMMMC → JKLMMMCQJKLMMMC
MCQJKLMMMC → KLMMMCQJKLMMMCJ
MMCQJKLMMMC → LMMMCQJKLMMMCJK
MMMCQJKLMMMC → MMMCQJKLMMMCJKL

となる。JKL の移動の様子がわかるように太字にした。

規則M は先頭の記号を末尾に1文字ずつ移す。そのため、一般的に xy をもたらすような記号列を考えると、y の文字数（記号列の長さ）分の M が必要であることがわかる。

したがって、xy をもたらすような記号列 x には、任意の記号列 y と、y と同じ長さをもつ M からなる記号列 z を使った、zCQyzC がある。
（また、RQyRQ → yRQyRQ を使った zRQyzRQ も同様の記号列となりうる。）

（つづく）

不動点パズル17：移動

（前回はこちら）

機械に、ある記号列 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 は y の反復 yy をもたらす）
規則V　x → y ならば、Vx → y←
（x が y をもたらすならば、Vx は y の反転 y← をもたらす）
規則P　x → y ならば、Px → yy←
（x が y をもたらすならば、Px は y の回文 yy← をもたらす）

さらに規則を導入する。

規則M　x → y ならば、Mx → y●
（x が y をもたらすならば、Mx は y● をもたらす）

x● は、記号列 x の先頭の記号を末尾に移した記号列を意味する。記号列が1文字だけの記号の場合には、x● は x そのものとする。たとえば、x が KGS ならば、x● は GSK となる（x の先頭の記号 K を末尾に移動）。

問題は以下。

問23　x が x● をもたらすような x を見つけよ。

問24　任意の記号列 y に対して、規則Q、C、R、V だけを使った記号列 x で xy をもたらすものがあるかどうかは未解決問題だとすでに述べた（「不動点パズル11：未解決問題」参照）。しかし、規則M を追加すると、任意の記号列 y に対して、記号列 x が xy をもたらすような x を比較的簡単に見つけることができる。それは、どのようにすればよいだろうか。たとえば、x が xJKL をもたらすような x を見つけよ。

問23についてはここで解答しよう。

問23　x が x● をもたらすような x を見つけよ。

（解答）

x → x●　・・・・・①

となる x を探す。

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

Mx₁ → Mx₁●　・・・・・①'

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

x₁ → Mx₁　・・・・・②

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

CQyC → yCQyC の y を M とすると、CQMC → MCQMC となり、②を満たす。
求める記号列 x は、

x = Mx₁ = MCQMC
∴求める記号列は、MCQMC

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

（つづく）

不動点パズル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 も同様に求められる。

＊＊＊＊＊

（つづく）

不動点パズル15：回文

（前回はこちら）

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

規則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← をもたらす）

たとえば、x が ABC をもたらすならば、Px は ABCCBA をもたらす。xx← は対称記号列であり、前から読んでも後ろから読んでも同じ記号列となる。そのため対称記号列は、回文記号列とも呼ばれる。xx← を x の回文と呼ぶ。

回文記号列についての問題は、以下の3問。

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

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

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

（つづく）

不動点パズル14：対称記号列（問19の解答後半）

（前回はこちら）

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

規則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 の反転をもたらす）

対称記号列（回文記号列）：反転しても同じである記号列。記号列がその反転と等しいとき、その記号列は対称であるという。

前回、問19で、それ自身をもたらす対称記号列 VVCVVQVVCVV を見つけた。今回は、問19の後半部分、何種類あるかについて考えよう。前回の解答の途中でさらりと触れたが、実は、この問題の本での解答をすでに見ている。しかし、その解答を見てもまだわかっていないので、解答の解説を書くつもりで記載する。


問題19　CQC 以外で、それ自身をもたらす対称記号列を見つけよ。それは何種類あるだろうか。

この問題の解答欄には以下のようにあった。

VVCVVQVVCVV は、それ自身をもたらす対称記号列になる。z を偶数個の V からなる記号列とするとき、zCzQzCz もそれ自身をもたらす対称記号列になる。

z = VV（2個の V からなる記号列）としたとき、zCzQzCz は VVCVVQVVCVV である。

z を偶数個の V からなる記号列とするとき、zCzQzCz もそれ自身をもたらす対称記号列になるのだから、VVVVCVVVVQVVVVCVVVV（z = VVVVとしたとき）も、それ自身をもたらす対称記号列になる。

では、z が奇数個の場合は、それ自身をもたらす対称記号列にならないのだろうか。たとえば、VCVQVCV がどのような記号列をもたらすのかを考えてみる。

VCVQVCV がもたらす記号列を x とすると、

VCVQVCV → x　・・・・・①

と書ける。VCVQVCV は V からはじまる記号列であるため、何らかの記号列をもたらすならば規則V に従う。そのため、

CVQVCV → x←　・・・・・②

ならば、VCVQVCV は x をもたらす。

CVQVCV は C からはじまる記号列であるため、何らかの記号列をもたらすならば規則C に従う。そのため、x← を、y←Qy← とおくと、

VQVCV → y←　・・・・・③

ならば、CVQVCV は x← をもたらす。

VQVCV は V からはじまる記号列であるため、何らかの記号列をもたらすならば規則V に従う。そのため、

QVCV → y

ならば、VQVCV は y← をもたらす。

規則Q より、QVCV は VCV をもたらす。
QVCV は VCV をもたらすので、VQVCV は VCV（VCV の反転）をもたらす。
VQVCV は VCV をもたらすので、CVQVCV は VCVQVCV をもたらす。
CVQVCV は VCVQVCV をもたらすので、VCVQVCV は VCVQVCV をもたらす。

VCVQVCV が、それ自身をもたらす対称記号列となった。VCVQVCV は、zCzQzCz で、z = V（Vが1個）の記号列である。つまり、z が奇数個の V からなる記号列のひとつである。どこかで何か間違ったのだろうか。

3つ以上の奇数の場合はどうだろうか。

先ほど見た記号列 VCVQVCV では、QVCV が VCV をもたらすことが、最終的に VCVQVCV は VCVQVCV をもたらす条件となっている。

前回求めた対称記号列 VVCVVQVVCVV についてみると、
（規則Q）QVVCVV → VVCVV
（規則V）QVVCVV → VVCVV であるので、VQVVCVV → VVCVV
（規則V）VQVVCVV → VVCVV であるので、VVQVVCVV → VVCVV
（規則C）VVQVVCVV → VVCVV であるので、CVVQVVCVV → VVCVVQVVCVV
（規則V）CVVQVVCVV → VVCVVQVVCVV であるので、
VCVVQVVCVV → VVCVVQVVCVV
（規則V）VCVVQVVCVV → VVCVVQVVCVV であるので、
VVCVVQVVCVV → VVCVVQVVCVV
であり、QVVCVV → VVCVV であることが、最終的に VVCVVQVVCVV → VVCVVQVVCVV の条件となっている。

zCzQzCz についても、QzCz → zCz であるので、zCzQzCz → zCzQzCz といえるだろう。

QzCz → zCz
QzCz → zCz であるので、VQzCz → zCz
……（記号列zの V の個数分、繰り返し）……
zQzCz → zCz であるので、CzQzCz → zCzQzCz
CzQzCz → zCzQzCz であるので、VCzQzCz → zCzQzCz
……（記号列zの V の個数分、繰り返し）……
z_n-1CzQzCz → zCzQzCz であるので、zCzQzCz → zCzQzCz
のようになるはずである。（z_n-1 は、z の V の個数より1少ない個数の V からなる記号列）

このなかで、反転の対象となる記号列は、zCz と zCzQzCz で、z が V からなる記号列である場合は、V の個数にかかわらず、zCz と zCzQzCz を反転しても同じ記号列となる（つまり、対称記号列である）。

本の解答に、「偶数個の V」とあるからには何らかの理由があると思うのだが、現時点ではその理由がわかっていない。本に記載されている解答は間違いではない。「z を偶数個の V からなる記号列とするとき、zCzQzCz もそれ自身をもたらす対称記号列になる」ことは間違いではない。

（つづく）

不動点パズル13：対称記号列（問19の解答）

（前回はこちら）

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

規則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 の反転をもたらす）

対称記号列（回文記号列）：反転しても同じである記号列。記号列がその反転と等しいとき、その記号列は対称であるという。

問19について、『スマリヤンのゲーデル・パズル』には、解答は載っているが、どのように導いたのかは載っていない。したがって、以下記載しているのは、僕の試行錯誤の過程である。


問題19　CQC 以外で、それ自身をもたらす対称記号列を見つけよ。それは何種類あるだろうか。

（解答）
対称記号列とは、前から読んでも後ろから読んでも同じ記号列であるので、求める記号列を x とすると、

x = x←

である。

求める記号列は、それ自身をもたらす記号列であるので、

x → x　・・・・・①

となる対称記号列 x を探す。対称記号列であるので、反転しても同じものである。したがって①は、

x → x←　・・・・・②

とも書き換えられる。

そこで、x は V からはじまる対称記号列（そして V で終わる記号列）として、x = Vx₁V とすると、x₁ は対称記号列であり、①②は、それぞれ

Vx₁V → Vx₁V　・・・・・①’
Vx₁V → [Vx₁V]←　・・・・・②'

と書ける。

①'について、規則V の条件より、

x₁V → [Vx₁V]←　・・・・・③

②'について、規則V の条件より、

x₁V → Vx₁V　・・・・・④

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

（CQyC → yCQyC や RQyRQ → yRQyRQ を使いたくなるが、対称記号列とならない可能性が高いので、別の方法をとる。）

③について、反転のかたちをしており、x₁ は対称記号列であるので、x₁ = Vx₂V とすると、x₂ は対称記号列であり、また③、④はそれぞれ、

Vx₂VV → [VVx₂VV]←　・・・・・③'

Vx₂VV → VVx₂VV　・・・・・④'

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

x₂VV → VVx₂VV　・・・・・⑤
x₂VV → [VVx₂VV]←　・・・・・⑥

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

⑤について、随伴のかたちに似ており、x₂ は対称記号列であるので、x₂ = Cx₃Qx₄C（x₄ は x₃ の反転とする）とすると、

Cx₃Qx₄CVV → VVCx₃Qx₄CVV　・・・・・⑤'
Cx₃Qx₄CVV → [VVCx₃Qx₄CVV]←　・・・・・⑥'

と書ける。

⑤'でもたらされる記号列 VVCx₃Qx₄CVV について、これを随伴のかたちにするため、VVCx₃ = x₄CVV となるような x₃、x₄ を考えると、x₃、x₄ ともに VV であればよい。x₄ は x₃ の反転であることも満たしている。x₃ = x₄ = VV を、⑤'、⑥'に当てはめてみると、

CVVQVVCVV → VVCVVQVVCVV　・・・・・⑤'
CVVQVVCVV → [VVCVVQVVCVV]←　・・・・・⑥'

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

VVQVVCVV → VVCVV　・・・・・⑦

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

⑦は規則V の条件より、 VQVVCVV → VVCVV とならなければならず、VQVVCVV → VVCVV は、QVVCVV → VVCVV とならなければならない。QVVCVV → VVCVV は規則Q を満たしている。

それ自身をもたらす対称記号列 x は、次のようになる。

x = Vx₁V = VVx₂VV = VVCx₃Qx₄CVV = VVCVVQVVCVV
∴それ自身をもたらす対称記号列として、VVCVVQVVCVV が存在する。

（ここで示した解き方は、解答の記号列を見て考えたものであり、解答に合わせるように解いている。ひょっとすると、もう少しうまい解き方があるかもしれない。）

それ自身をもたらす対称記号列が何種類あるかについては次回に回そう。

（つづく）

不動点パズル12：対称記号列

（前回はこちら）

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

規則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 の反転をもたらす）

ここでさらに、新たな規則を導入していく予定だが、その前に、対称記号列について説明しておく。対称記号列とは、前から読んでも後ろから読んでも同じ記号列のことで、回文記号列ともいう。前から読んでも後ろから読んでも同じになるとき、言い換えると、記号列がその反転と等しいとき、その記号列は対称であるという。

問17（不動点パズル09参照）で、それ自身をもたらす記号列を複数見つけた。そこで見つけた記号列は、CQC を除いて対称ではない。

問17で見つけた記号列のいくつかをあらためて見てみよう。

CQC
VVCQVVC
VVRQVVRQ

CQC は前から読んでも後ろから読んでも同じ記号列、つまり対称であるが、VVCQVVC、VVRQVVRQ は、後ろから読むと異なる記号列となるので対称ではない。問17で、偶数個の V で構成される記号列を、記号列 yCQyC、yRQyRQ の y のところに入れたものがそれ自身をもたらす記号列となることも確認しているが、それらも対称ではない。

ここで問題。

問題19　CQC 以外で、それ自身をもたらす対称記号列を見つけよ。それは何種類あるだろうか。

（つづく）

不動点パズル11：未解決問題

（前回はこちら）

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

規則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 の反転をもたらす）

ここでアーニー（スマリヤンの友人）は、未解決問題を提示する。未解決問題は以下のものである。

未解決問題　与えられた記号列 y に対して、xy をもたらす記号列 x が常に存在するだろうか。たとえば、xA をもたらす x が存在するだろうか。私もその答えが気になっている。これを証明または反証できた読者は、ぜひとも知らせてほしい。

このように書いているということは、証明も反証もできないのであろうが、証明も反証もできない状況というのがどのようなものなのかを感じるために、少し考えてみたい。

ここでは、xA をもたらす記号列 x について考えてみよう。

x → xA　・・・・・★

となるような記号列 x を探す。この記号列 x について、（ア）Q からはじまる記号列である場合、（イ）C からはじまる記号列である場合、（ウ）R からはじまる記号列である場合、（エ）V からはじまる記号列である場合、と分けて考えてみる。


（ア）Q からはじまる記号列である場合
x は、Q からはじまる記号列ではない。Qからはじまる記号列は、規則Q より Qx → x となり、★になることはない。

（イ）C からはじまる記号列である場合
C からはじまる記号列 x について、x = Cx₁ とすると、★は、

Cx₁ → Cx₁A　・・・・・①c

と書ける。

規則C は、Cx が y の随伴をもたらすことを言っているので、①cの Cx₁A には Q が含まれているはずである。そこで、x₁ = x₂Qx₃ とすると、①cは次のように書き換えることができる。

Cx₂Qx₃ → Cx₂Qx₃A　・・・・・①c'

さらに、①c'の Cx₂Qx₃A は随伴のかたちとならなければならないので、Cx₂ と x₃A は同じ記号列とならなければならない。そこで、Cx₂ = x₃A = CyA（つまり、x₂ = yA、x₃ = Cy）とおくと、①c'は次のように書き換えることができる。

CyAQCy → CyAQCyA　・・・・・①c"

①"が成り立つためには、規則C の条件より、

yAQCy → CyA　・・・・・②c

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

この先も続けるならば、CyA をもたらすような yAQCy を探していくことになるが、この場合、y が Q からはじまる場合、C からはじまる場合、……と、また繰り返すことになるので、 ここでやめておこう。

（ウ）R からはじまる記号列である場合
R からはじまる記号列 x について、x = Rx₁ とすると、★は、

Rx₁ → Rx₁A　・・・・・①r

と書ける。

規則R は、Rx が y の反復をもたらすことを言っているので、①rの Rx₁A は反復のかたちをとっているはずである。そこで、x₁ = x₂ARx₂ とすると、①rは次のように書き換えることができる。

Rx₂ARx₂ → Rx₂ARx₂A　・・・・・①r'

このとき、規則R の条件より、

x₂ARx₂ → Rx₂A　・・・・・②r

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

この先を続けるならば、Rx₂A をもたらすような x₂ARx₂ を探していくことになるが、この場合、y が Q からはじまる場合、C からはじまる場合、……と、また繰り返すことになるので、（イ）の場合と同じく、ここでやめておこう。

（エ）V からはじまる記号列である場合
V からはじまる記号列 x について、x = Vx₁ とすると、★は、

Vx₁ → Vx₁A　・・・・・①v

と書ける。

①v が成り立つためには、規則V の条件より、

x₁ → [Vx₁A]←　・・・・・②v

とならなければならない。②vは、反転をもたらす記号列 x₁ を示唆しているので、x₁ = Vx₂ とすると、②vは次のように書き換えることができる。

Vx₂ → [VVx₂A]←　・・・・・②v'

このとき、規則V の条件より、

x₂ → VVx₂A　・・・・・③

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

この先を続けるならば、VVx₂A をもたらすような x₂ を探していくことになるが、ここでも、y が Q からはじまる場合、C からはじまる場合、……と、また繰り返すことになるので、やめておこう。


xA をもたらすような記号列 x について、（ア）Q からはじまる記号列である場合、（イ）C からはじまる記号列である場合、（ウ）R からはじまる記号列である場合、（エ）V からはじまる記号列である場合、と分けて考えてみたが、（ア）以外は途中で議論をやめている。証明も、反証もしていない。続けていけば、もしかするとこのような記号列が存在するのかもしれないが、ここではわからない。逆に、このような記号列が存在しないという証明となっているわけでもない。別のやり方で証明、もしくは反証ができるのかもしれないが、ここではわかっていない。

（つづく）

不動点パズル10：反転（問18の解答）

（前回はこちら）

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

規則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 の反転をもたらす）

今回は、問18を解いていく。


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

（解答）
まずは、x←JKL をもたらす記号列 x を探していこう。

求める記号列 x は、x←JKL をもたらすので、

x → x←JKL　・・・・・①

を満たす。

反転のかたちがあるので、x は V からはじまる記号列として、x = Vx₁ とすると、①は、

Vx₁ → [Vx₁←]JKL　・・・・・①'

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

x₁ → LKJVx₁　・・・・・②

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

問４より、CQyC → yCQyC であるので、この y = LKJV とすると、CQLKJVC → LKJVCQLKJVC が成り立ち、これは②の x₁ を x₁ = CQLKJVC としたときに一致する。

したがって、求める記号列は VCQLKJVC である。
（問９で求めた、RQyRQ → yRQyRQ を利用した VRQLKJVRQ も解答となる。）

いまの結果をあらためて規則V に沿ったかたちで明示的に書くと、「CQLKJVC は LKJVCQLKJVC をもたらすので、VCQLKJVC は CVJKLQCVJKL をもたらす」、つまり、

CQLKJVC → LKJVCQLKJVC であるので、
VCQLKJVC → CVJKLQCVJKL　・・・・・③

ここで、記号列JKL を z とすると、LKJ は z← となり、③は、

CQz←VC → z←VCQz←VC であるので、VCQz←VC → CVzQCVz　・・・・・③'

と書ける。CQz←VC → z←VCQz←VC は z がどのような記号列であっても成り立つ（CQyC → yCQyC の y を z←V としたもの）。また、VCQz←VC → CVzQCVz の CVzQCVz　は、VCQz←VC の反転に、任意の記号列 z を続けたものである。

したがって、任意の記号列 y に対して、x←y をもたらすものが存在し、その記号列に VCQy←VC がある。
（VRQy←VRQ も、任意の記号列 y に対して、x←y をもたらす記号列である。）

（つづく）

不動点パズル09：反転（問17の解答）

（前回はこちら）

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

規則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 の反転をもたらす）

今回は問17について。説明が冗長に、わかりにくくなってしまっている。

問17　記号 Q と C だけを使った記号列で、それ自身をもたらすものはただ一つしかないことが証明できる。
(1) しかしながら、記号 Q、C、V だけを使った記号列で、それ自身をもたらすものはいくつも存在する。それは何種類あるだろうか。
(2) また、記号 Q、R、V だけを使った記号列で、それ自身をもたらすものは何種類あるだろうか。

記号 Q と C だけを使った記号列で、それ自身をもたらすものは、CQC である（問１解答参照）。しかし、問１の解答では、それ自身をもたらす記号列を作ってみたというだけで、ただ一つしかないことの証明にはなっていない。そこでまず、記号 Q と C だけを使った記号列で、それ自身をもたらす記号列は CQC ただ一つしかないことの証明を考えてみよう。

記号 Q と C だけを使った記号列で、それ自身をもたらす記号列を x とすると、

x → x　・・・・・①

となるような記号列 x を探す。

仮にこの記号列が Q からはじまる記号列だとして、x = Qy とすると、①は、

Qy → Qy

となる。これは、規則Q に反する（規則Q では、Qy → y）。よって、x は Q からはじまる記号列ではなく、C からはじまる記号列となる。

x = Cx₁ とすると、①は、

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

と書ける。規則C のかたちをしているが、これを成り立たせるには、x₁ は記号 Q を含んでいなければならない。そこで、x₁ = yQz とすると、①’は、

CyQz → CyQz　・・・・・①”

と書ける。随伴のかたちとなるには、z = Cy となるため、さらに書き換えると、

CyQCy → CyQCy　・・・・・①'''

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

yQCy → Cy　・・・・・②

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

（y を抜いた記号列であれば、QC → C となり、規則Qを満たす。このとき、それ自身をもたらす記号列は CQC である。）

y は、Q からはじまる記号列ではないので（規則Q に反するため）、Cからはじまる記号列である。y = Cy₁ とすると、②は、

Cy₁QCCy₁ → CCy₁　・・・・・②'

と書ける。規則C のかたちをしているが、これを成り立たせるには、y₁ は記号 Q を含んでいなければならない。そこで、y₁ = z₁Qz₂ とすると、②'は、

Cz₁Qz₂QCCz₁Qz₂ → CCz₁Qz₂　・・・・・②'

と書ける。随伴のかたちとなるには、z₂ = CCz₁ となるため、さらに書き換えると、

Cz₁QCCz₁QCCz₁QCCz₁ → CCz₁QCCz₁　・・・・・②''

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

z₁QCCz₁QCCz₁QCCz₁ → CCz₁　・・・・・③

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

以下、同様の議論の繰り返しとなる。そのため、記号 Q と C だけを使った記号列で、それ自身をもたらす記号列は CQC 以外に求めることができない。

(1) 記号 Q、C、V だけを使った記号列で、それ自身をもたらすものはいくつも存在する。それは何種類あるだろうか。

（解答）
Q からはじまる記号列でそれ自身をもたらすものは存在せず、C からはじまる記号列でそれ自身をもたらすものは CPC ただ一つであることは先に確認した。そこでここでは、V からはじまる記号列でそれ自身をもたらすものを探す。

記号 Q、C、V だけを使った記号列で、それ自身をもたらす記号列を x とすると、

x → x　・・・・・①

となるような記号列 x を探す。

x は V からはじまる記号列であるので、x = Vx₁ とすると、①は、

Vx₁ → Vx₁　・・・・・①'

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

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

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

反転のかたちであるため、x₁ は、V からはじまる記号列となり、x₁ = Vx₂ とすると、②は、

Vx₂ → [VVx₂]←　・・・・・②

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

x₂ → VVx₂　・・・・・③

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

問４で、任意の記号列 y について、CQyC → yCQyC となることを求めた。ここで y = VV とすると、CQVVC → VVCQVVC となり、③を満たす。
したがって、求める記号列（の一つ）は、

x = Vx₁ = VVx₂ = VVCQVVC

となる。

記号列の反転について、反転の反転はもとの記号列となる。記号列 x の反転の反転は、記号列 x である。先ほど③の式を

x₂ → VVx₂　・・・・・③

としたが、たとえばここで、

x₂ → [VVx₂]←←　・・・・・④

とすることもできた。③は、反転の反転はもとの記号列であることを意識している。

仮に、④の条件ですすめていくと、x₂ が V からはじまる記号列として置き換えて、もう一度、規則V のかたち
だから、とすすめていける。

先ほどは、CQyC → yCQyC を利用して、y = VV として、VVCQVVC を求めたが、④からさらにすすめていけば、yCQyC の y が VVVV であるとき、VVVVVVであるとき、……、つまり、V が偶数個のときに、それ自身をもたらす記号列となる。V が偶数個であるというのは、記号列の反転の反転はそのままであるということと対応している。



(2) また、記号 Q、R、V だけを使った記号列で、それ自身をもたらすものは何種類あるだろうか。

（解答）
(1)での考え方と同じで、(1)では CQyC → yCQyC（記号 Q と C を使った記号列。y は偶数個の V ）を使ったが、ここでは問11で求めた RQyRQ → yRQyRQ を使う。y が偶数個の V である記号列 yRQyRQ（たとえば、VVRQVVRQ など）が、それ自身をもたらす記号列となる。

（つづく）

不動点パズル08：反転（問12～16の解答）

（前回はこちら）

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

規則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 ならば、Rx → y←
（x が y をもたらすならば、Vx は y の反転をもたらす）

前回の問題のなかの、問12から16までの解答を以下に記してみる。

＊＊＊＊＊

問12　それ自身の反転をもたらすような記号列を見つけよ。

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

x → x←　・・・・・①

を満たす記号列 x を探す。

x は V からはじまる記号列となるため、x = Vx₁ とすると、①は、

Vx₁ → [Vx₁]←　・・・・・①’

と書ける。（反転を表す矢印←がかかる範囲を明確にするために[]をつけた。）

このとき、規則V の条件より、

x₁ → Vx₁　・・・・・②

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

任意の記号列 y に対して、CQyC → yCQyC であるので（問４参照）、y = V とすると、CQVC → VCQVC となり、②を満たす。

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

x = Vx₁ = VCQVC
∴それ自身の反転をもたらす記号列は VCQVC

また、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、VRQVRQ もそれ自身の反転をもたらす。

＊＊＊＊＊

問13　それ自身の反復の反転をもたらすような記号列を見つけよ。

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

x → [xx]←　・・・・・①

を満たす記号列 x を探す。

x は V からはじまる記号列となるため、x = Vx₁ とすると、①は、

Vx₁ → [Vx₁Vx₁]←　・・・・・①’

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

x₁ → Vx₁Vx₁　・・・・・②

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

②は反復のかたちであるので、x₁ は R からはじまる記号列。x₁ = Rx₂ とすると、②は、

Rx₂ → VRx₂VRx₂　・・・・・②’

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

x₂ → VRx₂　・・・・・③

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

任意の記号列yに対して、CQyC → yCQyC であるので、y = VR とすると、CQVRC → VRCQVRC となり、③を満たす。

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

x = Vx₁ = VRx₂ = VRCQVRC
∴それ自身の反復の反転をもたらす記号列は VRCQVRC

また、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、VRRQVRRQ もそれ自身の反転をもたらす。

＊＊＊＊＊

問14　それ自身の随伴の反転をもたらすような記号列を見つけよ。

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

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

を満たす記号列 x を探す。

x は V からはじまる記号列となるため、x = Vx₁ とすると、①は、

Vx₁ → [Vx₁QVx₁]←　・・・・・①’

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

x₁ → Vx₁QVx₁　・・・・・②

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

②は随伴のかたちであるので、x₁ は C からはじまる記号列。x₁ = Cx₂ とすると、②は、

Cx₂ → VCx₂QVCx₂　・・・・・②’

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

x₂ → VCx₂　・・・・・③

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

任意の記号列yに対して、CQyC → yCQyC であるので、y = VC とすると、CQVCC → VCCQVCC となり、③を満たす。

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

x = Vx₁ = VCx₂ = VCCQVCC
∴それ自身の随伴の反転をもたらす記号列は VCCQVCC

また、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、VCRQVCRQ もそれ自身の反転をもたらす。

＊＊＊＊＊

問15　それ自身の反転の随伴をもたらすような記号列を見つけよ。

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

x → x←Qx←　・・・・・①

を満たす記号列 x を探す。

x は C からはじまる記号列となるため、x = Cx₁ とすると、①は、

Cx₁ → [Cx₁]←Q[Cx₁]←　・・・・・①’

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

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

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

②は反転のかたちであるので、x₁ は V からはじまる記号列。x₁ = Vx₂ とすると、②は、

Vx₂ → [CVx₂]←　・・・・・②’

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

x₂ → CVx₂　・・・・・③

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

任意の記号列yに対して、CQyC → yCQyC であるので、y = CV とすると、CQCVC → CVCQCVC となり、③を満たす。

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

x = Cx₁ = CVx₂ = CVCQCVC
∴それ自身の反転の随伴をもたらす記号列は CVCQCVC

また、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、CVRQCVRQ もそれ自身の反転をもたらす。

＊＊＊＊＊

問16　それ自身の随伴の反転の反復をもたらすような記号列を見つけよ。

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

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

を満たす記号列 x を探す。

x は R からはじまる記号列となるため、x = Rx₁ とすると、①は、

Rx₁ → [Rx₁QRx₁]←[Rx₁QRx₁]←　・・・・・①’

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

x₁ → [Rx₁QRx₁]←　・・・・・②

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

②は反転のかたちであるので、x₁ は V からはじまる記号列。x₁ = Vx₂ とすると、②は、

Vx₂ → [RVx₂QRVx₂]←　・・・・・②’

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

x₂ → RVx₂QRVx₂　・・・・・③

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

③は随伴のかたちであるので、x₂ は C からはじまる記号列。x₂ = Cx₃ とすると、③は、

Cx₃ → RVCx₃QRVCx₃　・・・・・③’

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

x₃ → RVCx₃　・・・・・④

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

任意の記号列yに対して、CQyC → yCQyC であるので、y = RVC とすると、CQRVCC → RVCCQRVCC となり、④を満たす。

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

x = Rx₁ = RVx₂ = RVCx₃ = RVCCQRVCC
∴それ自身の随伴の反転の反復をもたらす記号列は RVCCQRVCC

また、問11より、任意の記号列 y に対して、RQyRQ → yRQyRQ であるので、CQyC → yCQyC のときと同様に、RVCRQRVCRQ もそれ自身の反転をもたらす。

＊＊＊＊＊

（つづく）

不動点パズル07：反転

（前回はこちら）

機械に、ある記号列 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 の反復をもたらす）

ここで、さらにもうひとつ別の規則を導入する。

規則V　x → y ならば、Vx → y←
（x が y をもたらすならば、Vx は y の反転をもたらす）

反転とは、その記号列の記号を逆の順に並べた記号列のことである。たとえば、LXQM の反転は MQXL である。任意の記号列 x の反転を x← と表す。

問題は以下である。

問12　それ自身の反転をもたらすような記号列を見つけよ。

問13　それ自身の反復の反転をもたらすような記号列を見つけよ。

問14　それ自身の随伴の反転をもたらすような記号列を見つけよ。

問15　それ自身の反転の随伴をもたらすような記号列を見つけよ。

問16　それ自身の随伴の反転の反復をもたらすような記号列を見つけよ。

問17　記号 Q と C だけを使った記号列で、それ自身をもたらすものはただ一つしかないことが証明できる。しかしながら、記号 Q、C、V だけを使った記号列で、それ自身をもたらすものはいくつも存在する。それは何種類あるだろうか。また、記号 Q、R、V だけを使った記号列で、それ自身をもたらすものは何種類あるだろうか。

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

（つづく）