ゆるゆるゲーデル、エッシャー、バッハ(略してGEB)本、読書会中
ゲーデル、エッシャー、バッハ―あるいは不思議の環 20周年記念版(略してGEBげぶ)本、読書会中*1
一体何に関する本なのだという疑問を持ちつつゆるゆる読書会中だ。ゆるゆるゲーデル、エッシャー、バッハ(GEBげぶ本)読むので、「ゆるげぶ読書会」と呼ぶ。主催者の白石さん命名。
第1章はMUパズルというのが紹介されている。それは形式システムである。
Wikipediaに解説が載っている。https://en.wikipedia.org/wiki/MU_puzzle
Nr. | Formal rule | Informal explanation | Example |
1. | xI → xIU | Add a U to the end of any string ending in I | MI to MIU |
2. | Mx → Mxx | Double the string after the M | MIU to MIUIU |
3. | xIIIy → xUy | Replace any III with a U | MUIIIU to MUUU |
4. | xUUy → xy | Remove any UU | MUUU to MU |
- 最後の文字がIであるような文字列を持っているなら、そのあとにUを付け加えてよい。
- 文字列Mxを持っている時は、文字列Mxxを持ちものに加えてよい
- もし所有しているある文字列の中にIIIが現れるなら、そのIIIをUに置き換えてよい
- もし所有する文字列のあるものがUUを含むなら、UUを省略してよい(51ページから52ページ)
上記のルールに従って、”MI”という文字列を”MU”にできるかというのが問いである。
規則に従って作り出される文字列をここでは「定理」と呼ぶ。規則だけを利用して作られた文字列について、定理を証明したという。最初の与えられた「定理」の事を「公理」とよぶ。上記の問題は公理からMUという定理を証明できるかという問題になる。
人間はあーだこーだと考えて、MIからMUを作ることはできないなあということを知る。IやUは2の倍数分増えるが、Iは3の倍数分しか減らないのでIをゼロにすることは決してできない。厳密な証明ということではないが、直感的に無理そうだということがわかる。
一方で、初期値MIを入れてMUになったら停止するようなプログラムを書くことは難しくない。このパズルが解ければそのプログラムは停止するが、そのプログラムが停止するかどうかをあらかじめ知ることはプログラムではできない。
形式システムの外側に人間がいるというのがポイントになる。
MIUシステムというのは、機械方式(Mechanical mode M方式)、知的方式(Intelligent mode I方式)、もうひとつの方式(Un-mode U方式)からなる。
定理性を検定する、いつでも有限時間で終わる方法があれば、その方法はその形式システムにおける「決定手続き」と呼ばれる。MIUシステムには残念ながら決定手続きはない。
第1章は叙述ミステリーを読んでいるような気分である。なんだかよく分からないトリックを弄された気分である。簡単にプログラムできるけど決して解けない(実行が終わることがない)プログラム。それが止まらないことをなぜ我々人間は知ることができるのだろうか。それこそが機械が到達しえない知性なのではないだろうか。そのような示唆を著者が与えているようなきがする。
まだ最初の章を読んだだけなので「げぶ本」のトリックにやられている可能性はあるが、このミステリーをゆっくりと楽しんでみたい。読書会すごい。読書会面白いと思った。