Domino作曲（習作62）

習作62（3:34）
同じベースラインでどこまでできるか。多少、手抜き感があります。

不動点パズル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 だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列を見つけよ。

（つづく）

Domino作曲（習作61）

習作61（4:16）
なかなかいい仕上がりになったと思います。

不動点パズル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は解けない可能性が高い。しかし、わからないかもしれないが、まずはやってみよう。

（つづく）

Domino作曲まとめ（習作51～60）

習作51から60をまとめたページです。


習作51（4:40）


習作52（4:55）


習作53（4:53）


習作54（3:29）


習作55（4:51）


習作56（4:22）


習作57（4:51）


習作58（4:11）


習作59（5:44）


習作60（5:09）

不動点パズル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 が得られる。

（つづく）

Domino作曲（習作60）

習作60（5:09）
コード進行が単純です。伴奏でカバーしたいところ。

不動点パズル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 から作られた記号列は特殊記号列にはなりえないのだろうか。この点に関しては、まだ考えていない。

（つづく）

戸籍をさかのぼってみた

お盆で実家に帰っておりました。それを機に、長年少し気になっていたことを調べてみました。

それは、自分のルーツがどこなのか、ということです。ご先祖はどんな人なのか、代々さかのぼるとどこに行き着くのか。知ってどうなるわけでもないのでそのままにしていましたが、気にはなっていました。

気になっていた理由はいくつかあります。

実家は愛媛県にあります。私の名字は「佐野」ですが、愛媛の実家がある町内には、佐野姓が3軒しかありません。そしてその3軒は親族です。小中学の友人や町内の知り合いの方々には、同じ姓の人が多いのに、なぜ佐野姓はうち（と親戚）だけなのか。

また、数年前に父方の祖父母が相次いで亡くなり、その際に実家にも家紋があることを知りました。遺影の袴姿を合成するときに母が家紋を確認していたり、お墓を新しくした際に、その新しいお墓に家紋が彫られていたりして、実家の家紋を目にする機会がありました。その家紋は「三つ巴」で、下野国を中心に栄えていた佐野氏の家紋です。現在の栃木県佐野市が佐野氏のはじまりです。栃木と愛媛は離れています。愛媛の実家は佐野姓だから佐野氏の家紋にしたのか、それとも、さかのぼれば栃木の佐野氏に行き着くのか。実家には家系図などないので、由緒正しき佐野氏の末裔というようなことはないでしょうが、関係あるのかないのかというちょっとした疑問がありました。



そして、ここ数年、自分の生い立ちを振り返ったり、自分史を作成したりする機会が多く、長年の小さな疑問がちょこちょこと顔を上げていました。


そういうわけで、せっかく実家に帰ったので、ついでに町役場に行って、戸籍をさかのぼって調べてもらいました。お願いしたのは、父方の祖父から戸籍をさかのぼれるところまでさかのぼってほしいということです。実家の佐野家を調べるので、今回は父系のみ。

結論からいうと、6代さかのぼることができました。6代前から同じ場所に住んでいたようです。町村名が変更していたり、区画整理があったりするので、厳密にずっと同じ土地であるとは確認はしていませんが、役場に6代前（戸籍は5代前まで。6代前は前戸主として名前だけ判明）まであったということは、その管轄地域にはずっといたということになります。

年月のわかる一番古い戸籍の記載事項は、6代前（清吉）から5代前（の兄、彦蔵）への家督相続の記載で「明治7年2月5日相続」というものでした。

家系図を略して書けば以下のような感じです。

清吉┬彦蔵
　　└兵吾―（高祖父）―（曽祖父）―（祖父）―（父）―（私）

日本で戸籍法が制定されたのは、Wikipedeliaによれば1871年（明治3・4年）のことであるようなので、ほぼ制定以来の戸籍をさかのぼったことになります。ここから先は調べるのが難しそうです。清吉さんは前戸主として名前だけ出てくる人物なので詳しくはわかりません。彦蔵さんは嘉永4年生まれの方。ペリーの黒船来航がたしか嘉永年間の出来事です。この頃から実家の佐野家があるのですね。

下野国の佐野氏は平安末期から江戸時代初期に栄えたようで、いろいろと分家があり、詳細は調べておりません。うちの実家は江戸時代は宇和島藩の管轄だったと思われ（ここも詳しくは調べておりません）、宇和島藩には伊達家が入っているので、そんなときに佐野家のご先祖様がやってきたとも考えられますが、想像でしかありません。


今回戸籍をさかのぼってみて、あまり考えることのない、いわば「縦のつながり」を感じることができました。記録もなく誰かわからないなどあるかもしれませんが、誰にも父母はいて、その父母にもまた父母がいて、と命がつながっていきます。実感することは少ないのかもしれませんが、今回戸籍をさかのぼることで、少なくとも6代前まではご先祖様はやはりいたんだと認識はできました。子どもがいればまた違う認識や実感が湧いてくるのかもしれません。現在一緒に暮らしている人、同時代に生きている人など、横のつながりは意識することが多いと思います。そんな中で、縦のつながりの最小単位である親子関係について、これは同時代を生きているという横のつながりでもあります。あるいは家族のかたちとは。

長年の疑問についてはまだわかっておりませんが、さまざまな事を考えるいい機会となりました。

不動点パズル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 をもたらすだろうか。

（つづく）

Domino作曲（習作59）

作りかけのものをこなしていきます。

習作59（5:44）
伴奏が単調ですが、よしとしましょう。

不動点パズル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 をもたらしている。

（つづく）

Domino作曲（習作57、58）

Domino作曲。作りかけの曲は多数ありますが、出来上がりまでは時間がかかります。


習作57（4:51）
三連符を多用した跳ねるリズムの曲。聞いていて楽しくなるような一曲となりました。



習作58（4:11）
サビの部分が「♪あの素晴らしい愛をもう一度」という曲に似ています（曲のタイトル忘れました…）。たぶんサビの部分だけだと思いますが。

不動点パズル05：反復（問５～問８の解答）

（前回はこちら）

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

まずは問５～問８まで解いていこう。

＊＊＊＊＊

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

（解答）
求める記号列を x とすると、x それ自身の反復をもたらすような記号列であるので、

x → xx　・・・・・①

となるような記号列 x を探すことになる。反復をもたらしているため、x = Rx₁ とすると、①は、

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

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

x₁ → Rx₁　・・・・・②

でなければならない。
問４で、CQyC → yCQyC を導いた。ここで y = R とすると、CQRC → RCQRC となり、②の x₁ を x₁ = CQRC としたものに一致する。

∴それ自身の反復をもたらすような記号列は RCQRC

＊＊＊＊＊

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

（解答）
求める記号列を x とすると、x それ自身の随伴の反復をもたらすような記号列であるので、

x → xQxxQx　・・・・・①

となるような記号列 x を探すことになる。反復のかたちであるので、x = Rx₁ とすると、①は、

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

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

x₁ → Rx₁QRx₁　・・・・・②

でなければならない。随伴のかたちであるので、x₁ = Cx₂ とすると、②は、

Cx₂ → RCx₂QRCx₂　・・・・・②’

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

x₂ → RCx₂　・・・・・③

でなければならない。
CQyC → yCQyC で y = RC とすると、CQRCC → RCCQRCC となり、③の x₂ を x₂ = CQRCCとしたものに一致する。
求める記号列は x であるため、

x = Rx₁ = RCx₂ = RCCQRCC
∴それ自身の随伴の反復をもたらすような記号列は RCCQRCC

＊＊＊＊＊

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

（解答）
求める記号列を x とすると、x それ自身の反復の随伴をもたらすような記号列であるので、

x → xxQxx　・・・・・①

となるような記号列 x を探すことになる。随伴のかたちであるので、x = Cx₁ とすると、①は、

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

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

x₁ → Cx₁Cx₁　・・・・・②

でなければならない。反復のかたちであるので、x₁ = Rx₂ とすると、②は、

Rx₂ → CRx₂CRx₂　・・・・・②’

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

x₂ → CRx₂　・・・・・③

でなければならない。
CQyC → yCQyC で y = CR とすると、CQCRC → CRCQCRC となり、③の x₂ を x₂ = CQCRCとしたものに一致する。
求める記号列は x であるため、

x = Cx₁ = CRx₂ = CRCQCRC
∴それ自身の随伴の反復をもたらすような記号列は CRCQCRC

＊＊＊＊＊

問８　それ自身の反復の反復、すなわち xxxx をもたらすような x を見つけよ。

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

x → xxxx　・・・・・①

となるような記号列 x を探すことになる。反復のかたちであるので、x = Rx₁ とすると、①は、

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

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

x₁ → Rx₁Rx₁　・・・・・②

でなければならない。反復のかたちであるので、x₁ = Rx₂ とすると、②は、

Rx₂ → RRx₂RRx₂　・・・・・②’

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

x₂ → RRx₂　・・・・・③

でなければならない。
CQyC → yCQyC で y = RR とすると、CQRRC → RRCQRRC となり、③の x₂ を x₂ = CQRRCとしたものに一致する。
求める記号列は x であるため、

x = Rx₁ = RRx₂ = RRCQRRC
∴それ自身の随伴の反復をもたらすような記号列は RRCQRRC

＊＊＊＊＊

（つづく）

不動点パズル04：反復

（前回はこちら）

アーニーの機械は記号列を操作する機械で、ある記号列 x を入力すると、ある記号列 y をもたらす。この機械には2つの規則、規則Q と規則C がある。

規則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 に対して、xx という記号列を x の反復という。たとえば、記号列 HJK の反復は、HJKHJK である。


では、問題を見ていこう。

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

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

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

問８　それ自身の反復の反復、すなわち xxxx をもたらすような x を見つけよ。

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

＊＊＊＊＊

問１～４でわかったことを再掲しておく。

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

（つづく）

Domino作曲（習作56）

久しぶりの作曲。

習作56（4:22）
カノンコードを使っています。

不動点パズル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 をもたらす）

（つづく）

不動点パズル02：随伴（問１～問３の解答）

（前回はこちら）

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

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

問題は以下の4問であった。

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


ここで、言葉で書いていくと文章が長くなりがちになるので、できるだけ記号を用いて表現したい。たとえば、「xがyをもたらす」というのを「x→y」と書くことにしよう。「もたらす」というのを「→」で表す。「x→y」のように記号で書いた表現を「式」と呼ぶ。そうすると、規則Qと規則Cの式はそれぞれ以下のように書ける。

規則Q　Qx→x
（任意の記号列xに対して、記号列Qxはxをもたらす）

規則C　x→yならば、Cx→yQy
（xがyをもたらすならば、Cxはyの随伴yQyをもたらす）

わかりやすくなるかどうか若干不安があるが、以降これでいこう。

この書き方は『スマリヤンのゲーデル・パズル』には載っておらず、このブログでの表記だ。また、解答方法もなるべく本の解答方法とは違う書き方（僕が考えた方法）をしていこうと思う。

＊＊＊＊＊

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

（解答）
規則Qより、Qx→xであるので、CQx→xQxが成り立つ。
xがCのとき（以下「x = C のとき」と表現する）、CQC→CQCとなる。

∴それ自身をもたらすような記号列はCQC

＊＊＊＊＊

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

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

x→xQx　・・・・・①

となるような記号列を探す。
随伴をもたらす記号列だから、xはCからはじまる記号列。そこで、x = Cx₁とすると、①は、

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

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

x₁→Cx₁　・・・・・②

が成り立たなければならない。②の式は規則Qにあてはまらないので、規則Cにあてはめるため、x₁ = Cx₂とすると、

Cx₂→CCx₂　・・・・・②’

と書ける。規則Cの条件を満たすようにするには、x₂ = QCC とすればいい（②’の式での出力先の記号列にはQがないので、x₂ = Qx₃とすると、x₃ = CC）。求める記号列はxであるため、

x = Cx₁ = CCx₂ = CCQCC
∴それ自身の随伴をもたらすような記号列はCCQCC

（考察）
・記号列CCQCCは、CCQCCの随伴CCQCCQCCQCCをもたらす。
・問１の解答途中で、CQx→xQxが成り立つことを確認した。CQx→xQxであるので、規則Cより、CCQx→xQxQxQxとなる。ここでx = CC としたのが問２の答えである。
・以下の規則は、本には載っていない（問題を解くためには使われている）

規則CQ　CQx→xQx（xの随伴）
（任意の記号列xに対して、記号列CQxはxの随伴xQxをもたらす）
規則CCQ　CCQx→xQxQxQx（xの随伴の随伴）
（任意の記号列xに対して、記号列CCQxはxの随伴の随伴をもたらす）

＊＊＊＊＊

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

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

x→xQxQxQx　・・・・・①

となるような記号列を探す。
随伴をもたらす記号列だから、xはCからはじまる記号列。そこで、x = Cx₁とすると、①は、

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

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

x₁→Cx₁QCx₁　・・・・・②

が成り立たなければならない。②の式は随伴をもたらすことを意味するので、x₁はCからはじまる記号列。x₁ = Cx₂とすると、

Cx₂→CCx₂QCCx₂　・・・・・②’

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

x₂→CCx₂　・・・・・③

が成り立たなければならない。③の式は規則Qにあてはまらないので、規則Cにあてはめるため、x₂ = Cx₃とすると、

Cx₃→CCCx₃　・・・・・③’

規則Cの条件を満たすようにするには、x₂ = QCCC とすればいい（③’の式での出力先の記号列にはQがないので、x₃ = Qx₄とすると、x₄ = CCC）。求める記号列はxであるため、

x = Cx₁ = CCx₂ = CCCx₃ = CCCQCCC
∴それ自身の随伴の随伴をもたらすような記号列はCCCQCCC

問４は次回にまわそう。

不動点パズル01：アーニーの処理系

（プロローグ）

アーニーは人の名前で、この本『スマリヤンのゲーデル・パズル』の著者スマリヤンさんの友人。実在するかどうかは知らない。

で、そのアーニーさんはいろいろな機械を作っていて、ここで紹介されているのは、アルファベットの大文字の記号列を操作する機械。

記号列というのは、アルファベット大文字の文字列のことで、別に意味があるとは限らない。BLPQは記号列だし、ARMも記号列。アルファベットの大文字を並べたものを記号列と呼んでいる。

このアーニーの機械は、ある記号列を入力すると、受け付けられれば、通常別の記号列を出力する。いま、この機械を使った問題（パズル）を解いているところだ。

この機械は規則にそって、ある記号列が入力されると、その記号列を操作して、別の記号列を出力する。まあ、実用性はほとんどない機械だけど、この機械の挙動を確認することで、ゲーデルの不完全性定理の理解が深まるという利点はあるかな。

この機械の規則を説明する前に、ちょっと、記号列の書き方や用語の説明をしておくね。

記号列とは、アルファベット大文字の文字列であるということは説明した。任意の記号列を表すために、x, y, zなどの小文字を使う。数学の方程式での未知数xのようなものだ。xが1文字だからといって、1文字の記号列を表すわけではない。（このブログではx₁のように添字をつけたものも使う。）

そして、任意の記号列の対xとyに対して、xyは、記号列xの後に記号列yを続けたものを意味する。たとえば、xが記号列BLDで、yが記号列HIJZだとすると、xyは記号列BLDHIJZになる。

記号列xを入力したときに記号列yが出力されるならば、xはyをもたらすという。

他にも用語は出てくるけど、まずはこれくらいにして、規則を説明していくね。

最初は、２つの規則からはじまっている。ページを進めていくと他の規則が追加されていって、どんどんややこしくなるよ（笑）

まずは１つ目の規則。規則Qだ。

規則Q　任意の記号列xに対して、記号列Qxはxをもたらす。

たとえば、QBLZはBLZをもたらす。記号列QBLZを入力したら、記号列BLZが出力されるということだ。

２つ目の規則は、規則C。

規則C　xがyをもたらすならば、Cxはyの随伴yQyをもたらす。

随伴という用語を説明するね。任意の記号列xに対して、記号列xQxはxと特別重要な関係にあるので、xの随伴と呼ばれている。特別重要な関係というのがどのような関係なのかは、まだ僕には読み切れていない。ここでは、記号列xの随伴とは、記号列xQxのことだ、くらいに思っておこう。

で、規則Cなんだけど、これがちょっとややこしい。もう一度規則Cを見てみよう。

規則C　xがyをもたらすならば、Cxはyの随伴yQyをもたらす。

規則Qのほうは、任意の記号列に対してQxはxをもたらすけれど、規則Cのほうは、「xがyをもたらすならば」という条件がついている。

規則Cが適用された例を挙げると、CQABはABQABをもたらす。QABはABをもたらすので、CQABはABの随伴であるABQABをもたらすということだ。規則Cと例を比べてみよう。

・xがyをもたらすならば、Cxはyの随伴yQyをもたらす。
・QABはABをもたらすので、CQABはABの随伴であるABQABをもたらす。

本は、まずはこの２つの規則を使った機械で問題を解いていくんだけど、もう少しこの機械を確認しておくね。

本には明言されていないけれど、このアーニーの機械に、規則の適用できない記号列が入力された場合、入力を受け付けないようにしておこう。たとえば、記号列ABを入力しようとした場合、この記号列ABは規則Qも規則Cも適用できない。そんなときは、受け付けられないとする。となると、入力できる記号列は、QかCからはじまる記号列となる。

規則Qは、任意の記号列に対してQx（Qからはじまる記号列）はxをもたらすけれども、規則Cには「xがyをもたらすならば」という条件があるので、Cからはじまる記号列すべてを受け付けできるわけではない。たとえば、CABは受け付けられない（ABは記号列をもたらさないため）。CQxならば、Qxはxをもたらすので、CQxはxQxをもたらす。

では、やっと問題に取り掛かろう。問題は４問ある。

問１　それ自身をもたらす（つまり、xを入力すると、xが出力される）ような記号列を見つけよ。

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

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

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

（つづく）

不動点パズル00：プロローグ

「アーニーの処理系の問題がよくわからない」

「いきなり何？」

「うん、この本の問題なんだけど――」

僕は読んでいた本を見せた。本のタイトルは『スマリヤンのゲーデル・パズル』。「論理パズルから不完全性定理へ」という副題がついている。

この本は副題のとおり、論理パズルなどの問題を解きながら、ゲーデルの不完全性定理のイメージや本質を理解しようという類をみない本だ。

以前に1度読んだことがあるが、問題を解かずに読んだだけであったためほとんど頭には入っておらず、今回は問題を解いていきながら読み進めていこうと思っている。いま読んでいたところは第９章で、「不動点パズル」という章題がついていた。

「――解答ページをみると、なるほどと思うんだけど、解き方というか、考え方がいまひとつつかめていない感じがするんだよね」

「答えがわかって納得できていれば、それでいいんじゃない？」

「うーん、それでもいいんだけど、納得できてもまだ理解できていない感じが強いんだよ。たとえば、キミに説明することができるかどうかあやしいし、次にもう一度同じ問題に取り組んだとしても解けるかどうかわからない。まあ、それができたとしても人生の役には立たないのかもしれないけど――」

人生の役には立たないのかもしれない――と、役に立つ可能性を否定はしなかったが、役に立つ可能性は極めて少ないと僕は思っている。不動点パズルが解けたところで、誰がどうなるわけではない。解答がわかっている問題であるので、何か新しいものを発見するというわけでもない。

ただ、僕にとっては少しだけ意味がある。理解することができれば、僕のなかにあるモヤモヤを少し消すことになる。「不動点パズル」もそうだが、その先にある「ゲーデルの不完全性定理」も、わかるようでわかっていないもののひとつであり、少しずつでもいいから理解を深めていきたいと思っている。

「――だから、ちょっとキミに聞いてもらいながら、このアーニーの処理系の問題、不動点パズルについて考えてみたいと思ったんだけど、いいかな？」

僕はキミの反応を待った。

（つづく）

盗人算より

ある数学読み物で、方程式の紹介をする導入部分において、「盗人算」について書かれていた。吉田光由の『塵劫記』に出ているものだという。そこには以下の問題が記載されていた。

盗賊団の会話が、橋の下から聞こえる。盗んできた反物を分配しようとしているようだ。「7反ずつ分けると8反余るし、8反ずつ分けると7反足りない。どうしたものかなあ」
さて、盗賊は何人で、反物は何反あるか。

『塵劫記』にはこれ1問しか出ておらず、答えも次の1行があるだけで、これ以上は書かれていないらしい。

盗賊は8足す7で15人、反物は15人掛ける8反に7反足りないから113反

盗賊の人数がわかれば反物が何反あるのかもわかるので、答えの後半はわかるとして、前半の盗賊の人数を求める部分、「8足す7で15人」というところの説明がほしい。

この数学の読み物では、このあとに方程式を立てて問題を解いている。盗賊の人数をx人として、「7反ずつ分けると8反余る」から反物は7x+8反ある。また「8反ずつ分けると7反足りない」ので、8x-7反とも表せる。7x+8反と8x-7反は同じ数であるので、

7x + 8 = 8x - 7

と方程式を立て、それを解いてx=15、つまり盗賊の人数は15人であることを確認していた。

そして、『塵劫記』には1問しか出ていないので、盗賊の人数や盗品の数が違った場合どうなるか、ということで、読み物では別の問題を作って確認していた。

盗賊団の会話が、橋の下から聞こえる。盗んできた反物を分配しようとしているようだ。「7反ずつ分けると6反余るし、9反ずつ分けると4反足りない。どうしたものかなあ」
さて、盗賊は何人で、反物は何反あるか。

同様に方程式を立てて解いてみると、

7x + 6 = 9x - 4
∴x = 5

盗賊の人数は5人で、反物は41反となる。

ここでふと思ったことは、問題の作り方にも注意が必要であるということだ。盗賊が5人であれば、「7反ずつ分けると6反余る」ということは言えないのではないか。6反余るのならば、「8反ずつ分けると1反余る」と言わないといけないのではないか。問題が間違っているとは言い切れないが、「余り」が盗賊の人数より少ないのは違和感を感じる（畳語？）。もっとも盗人の発話自体、実際にありそうな発話とは思えないけれど……。

読み物の方は盗人算を導入として、1次方程式、2次方程式、3次方程式、……という話につなげていて、盗人算がメインではなく、これ以上盗人算に触れることはなかったが、私の方はこの違和感のために、盗人算について少し考えさせられた。

『塵劫記』での盗人算の問題と解答は以下であった。

問：盗賊団の会話が、橋の下から聞こえる。盗んできた反物を分配しようとしているようだ。「7反ずつ分けると8反余るし、8反ずつ分けると7反足りない。どうしたものかなあ」
さて、盗賊は何人で、反物は何反あるか。
答：盗賊は8足す7で15人、反物は15人掛ける8反に7反足りないから113反

この答えにある「盗賊は8足す7で15人」というのはどこから来たのか。「8足す7で15人」として答えは合っているが、たとえば、「8足す7」の「8」は、7反ずつ分けたときの余りの「8」なのか、「8」反ずつ分けると7反足りない方の「8」なのかについては何の言及もない。盗人算とはどのようなものなのかを考えてみたい。

そこで、読み物にあった別の例を、違和感のないような問題に作り直し、『塵劫記』での問題と解答の形式にして比べてみる。

問：盗賊団の会話が、橋の下から聞こえる。盗んできた反物を分配しようとしているようだ。「8反ずつ分けると1反余るし、9反ずつ分けると4反足りない。どうしたものかなあ」
さて、盗賊は何人で、反物は何反あるか。
答：盗賊は1足す4で5人、反物は5人掛ける9反に4反足りないから41反

どうやら盗賊の人数の求め方は、「○反ずつ分けて余った反数＋（○+1）反ずつ分けて足りない反数」であるようだ。

少し一般化してみる。

割り算（除法）、余りについては次のように表現されることが多い。

m = qn + r

mは「割られる数」、nは「割る数」、qは「商」、rは「余り」と呼ばれる。盗人算に合わせられるように、自然数での除法を考える。r＜nとする。

上記を盗人算に対応させてみると、割られる数mは反物の総数、割る数nは盗賊の人数、商qは盗賊一人あたりの反数、余りrが余った反数となり、盗人算の問題は次のように表現できる。

q反ずつ分けるとr反余るし、q+1反ずつ分けるとa反足りない。盗賊はn人で、反物はm ( = qn + r ) 反とするとき、nを求めよ。

q+1反ずつ分けたときに足りない数をaとした。

もう少しこなれた感じで、盗人算の解答を含めて定理っぽく表現してみると、

m = qn + r で、m = (q + 1)n - a であるとき、n = r + a が成り立つ。
（m, n, q, r, a は自然数。r＜n, a＜n）

あるいはmodを使って、

m mod n = r で、m mod n = - a のとき、n = r + a

ともいえる。

証明は略。

3次方程式の解の公式の導出

3次方程式の解の公式（カルダノの公式）の導出についての覚え書き。（Webでの数式表記を詳しく調べていないので、分数やルートなどの表記部分がわかりにくくなっています。）

3次方程式は一般的に以下のように表される。

ax³ + bx² + cx + d = 0 （a ≠ 0）

変数変換
x = y - b / 3a を代入して、

a(y - b / 3a)³ + b(y - b / 3a)² + c(y - b / 3a) + d = 0

式を整理すると、

y³ - ((b² - 3ac) / 3a²)x + (2b³ - 9abc + 27a²d) / 27a³ = 0

となる。ここで、

p = - (b² - 3ac) / 3a²　　・・・①
q = (2b³ - 9abc + 27a²d) / 27a³　　・・・②

とすると、以下のyに関する3次方程式が得られる。

y³ + py + q = 0　　・・・③

• 変換後の3次方程式の左辺y³ + py + qには、2次の項がない（y²の係数が0）。3次方程式をより簡単な形に変換し、変換後の3次方程式の解を導くことで、変換前の3次方程式の解も導くことができる。
• この変換について、「立体完成」や「チルンハウス変換」「フェラーリの方法」などと呼ばれている。それぞれの変換名の詳細は調べていない。

y = u + vの導入
y = u + vとし、式③に代入する。

(u + v)³ + p(u + v) + q = 0

整理すると、以下になる。

(u³ + v³ + q) + (u + v) (3uv + p) = 0　　・・・④

ここで、以下の連立方程式、

u³ + v³ + q = 0　　・・・⑤
3uv + p = 0　　・・・⑥

を満たすu、vがあれば、y = u + vより、yを求めることができる。

• y = u + vの導入は、唐突な感がある。どのような意図でこのような変換をおこなったのかについては未確認。自分では思いつきそうにない。
• 方程式④から、連立方程式（⑤⑥）を立てることについても思いつきそうにない。
• 連立方程式の表記としては括弧（｛）があったほうがいいが、勉強不足。

連立方程式を解く

u³ + v³ + q = 0　　・・・⑤
3uv + p = 0　　・・・⑥

⑥より、

u= - p/3v

⑤に代入して、

(- p/3v)³ + v³ + q = 0

これを整理すると、

v⁶ + qv³ - (p/3)³ = 0

ここで、V = v³とすると、

V² + qV - (p/3)³ = 0

と、Vに関する2次方程式となる。
2次方程式の解の公式より、

V = - q ± √(q² + 4(p/3)³) = -(q / 2)±√((q/2)² + (p/3)³)
∴ v³ = -(q/2)±√((q/2)² + (p/3)³)

同様に、u³ = -(q/2)±√((q/2)² + (p/3)³)となる。u³とv³は対称であり、また、式⑤よりu³ + v³ = - qであるため、u³とv³の平方根の前にある±の符号は、片方が＋（プラス）であれば、もう片方は－（マイナス）である。よって、

u³ = -(q/2) + √((q/2)² + (p/3)³)
v³ = -(q/2) - √((q/2)² + (p/3)³)

よって、

u = ³√{-(q/2) + √((q/2)² + (p/3)³)}
v = ³√{-(q/2) - √((q/2)² + (p/3)³)}

y = u + vより、

y = ³√{-(q/2) + √((q/2)² + (p/3)³)} + ³√{-(q/2) - √((q/2)² + (p/3)³)}

• u³から三乗根をとるとき、3つの解が出てくる。三乗すると1となる3つ数を、1, ω, ω²)とすると、uの値は上記の他に、ωを掛けたものと、ω²を掛けたものの2つが存在する。
• WEBでの三乗根の表記のしかたは勉強不足。
• ここに挙げた公式、
  

  y = ³√{-(q/2) + √((q/2)² + (p/3)³)} + ³√{-(q/2) - √((q/2)² + (p/3)³)}

  は、式③のかたちの3次方程式についての解の公式であり、3次方程式の一般形についての解の公式ではない。しかし、変数変換で使ったx = y - b/3aや、式①②を使って一般形の解の公式を導くことができる。