形式システムの文字列を自然数によって表現すること １

『ゲーデル、エッシャー、バッハ』という本には、ＭＩＵシステムと呼ばれる形式システムが紹介されている。これは３個の記号「Ｍ，Ｉ，Ｕ」と、文字列を並べる４つの規則が提示されているものだ。出発点となる公理は一つだけで、その文字列から書き換え規則によって得られる文字列がどのようになるかを考える。まとめておくと次のようになる。


記号　　Ｍ，Ｉ，Ｕ
公理　　ＭＩ
規則
　Ⅰ　ｘＩが定理ならば、ｘＩＵは定理である。
　Ⅱ　Ｍｘが定理ならば、Ｍｘｘは定理である。
　Ⅲ　任意の定理において、ＩＩＩはＵで置き換えることが出来る。
　Ⅳ　任意の定理において、ＵＵは除くことが出来る。


ここで「定理」と呼ばれているのは、上の規則によって書き換えが可能な文字列のことを呼んでいる。「公理」とは、前提なしに・無条件に「定理」とされる文字列で、これを出発点に規則によって書き換えが出来るものがこのシステムの「定理」となる。この本では、パズルとして「ＭＵ」が定理となるかどうかを考察せよという問題が提出されている。この問題に解答するには、もし「ＭＵ」が定理ならば、実際にそれを導く書き換えの文字列を構成することによって解決する。しかし、これが「定理」でなかった場合は、「いくらやっても出来なかった」ということを示すだけでは、それが「定理」ではないということを示したことにはならない。合理的な理由によって、それが決して「定理」にならない、すなわち上の書き換え規則では導出できないのだということを示さなければならない。



「ＭＵ」が定理であれば、それは偶然にそのような文字列の構成を見つけられる可能性があるが、これが「定理」でない場合は、このシステムの全体の構造を把握して、そこから「ＭＵ」が定理でないことを導かなければならない。実際には「ＭＵ」は定理ではないので、そのような説明が出来る。この説明の考察に伴って、「ＭＵシステム」の記述を、文字列から数字の表現に転換するということがこの本では説明されている。このアイデアが、ゲーデルが自然数の形式的表現の文字列に「ゲーデル数」を割り当てたアイデアとよく似ている。ここからゲーデルの発想の雰囲気が感じ取れないかと思う。

さて「ＭＩＵシステム」によって導出される定理の様子をちょっと見てみよう。書き換え規則の適用によって得られる文字列を並べてみると次のようになるだろう。


１　ＭＩ　……　公理
２　ＭＩＩ　……　規則ⅡにおいてｘとしてＩを用いた。
３　ＭＩＩＩＩ　……　規則ⅡにおいてｘとしてＩＩを用いた。
４　ＭＵＩ　……　規則Ⅲによって最初のＩＩＩをＵで置き換えた。
５　ＭＵＩＵ　……　最後の文字がＩだったので規則Ⅰを適用してＵを付け加えた。
６　ＭＵＩＵＵＩＵ　……　規則ⅡにおいてｘとしてＵＩＵを用いた。
７　ＭＵＩＩＵ　……　規則Ⅳを適用してＵＵを取り除いた。


この文字列において、規則が正しく適用されている２から７までの文字列はすべて「定理」になる。４によって「ＭＵＩ」を作ることが出来たので、このＩを取り除くことが出来れば「ＭＵ」は「定理」となる。しかし、「ＭＩＵシステム」ではこのＩを取り除くことが出来ない。

「ＭＵ」が「定理」になるかどうかを考察するには、このシステムの構造がどうなっているかを把握しなければならない。個々の規則の適用が正しいかどうかということではなく、どのような特徴を持った「定理」が導出されるかという、構造に関する考察が必要になる。この本では、どのような性質が「遺伝的性質」を持っているかというような問題設定をして、システム全体の構造を把握しようとしている。

まずすぐに分かることは、この規則においてはＭの書き換えについては何も語っていないということだ。規則Ⅰでは、先頭のｘについては不変のままである。ⅡにおいてもＭはそのままだ。ⅢとⅣはＩとＵに関する規則であってＭは無関係だ。また公理はＭＩだけであって、Ｍはここにしか登場しない。つまり、Ｍはこのシステムにおいては文字列の先頭に登場し、文字列の先頭だけにしか登場しない。この性質はすべての「定理」に受け継がれる「遺伝的性質」だ。

Ｉについては、その追加規則はⅡにおけるｘがｘｘに書き換えられるところで追加されるだけである。ＵはⅠとⅢにおいて一つずつ追加することが可能だが、Ｉについては、書き換え前の２倍の数になるような追加しかこのシステムでは許されていない。つまり書き換え後のＩの数は必ず偶数になるということだ。しかもこの偶数にも制限がある。

出発点となる公理「ＭＩ」ではＩは一つしかない。だから、この公理を書き換えれてＩを追加すればそれは２になる。以下、どのようにがんばってみても、Ｉの数は

　　１、２，４，８，１６，３２，……

のような２のべきの数にしかならない。Ｉが３個の文字列は公理ではないので、それ以前の文字列から導出しなければならないが、Ｉは常に２倍の個数になるという性質が「遺伝的性質」としてあることを考えると、Ｉが３個になるようなその前の文字列は、Ｉを１．５個持っていなければならないが、個数における小数点は意味を持たない。つまり、Ｉが３個になるような文字列はこのシステムでは構造的に追加をして生成することが出来ない。同様に、Ｉが５個、６個、７個、９個、……となるような、２のべきではない個数のＩを持つ文字列は、このシステムからはＩの追加だけによっては導出できない。Ｉが常に２倍の個数になるように文字列が書き換えられるという性質を逆にたどると、その先祖としてＩが小数点の個数を持つような文字列を想定しなければならなくなるからだ。

さて、Ｉを追加する規則に関してはこのような性質があるので、Ｉを３個作ることが出来ない。しかし、Ｉにはそれを取り除く規則のⅢもある。これを利用すればＩが３個になるような文字列を作ることが出来るだろうか。これは、Ｉの追加によって出来るＩの個数は２のべき乗の個数になるので、これから３の倍数を引いた数がちょうど３の倍数になることがあるかどうかということを考察することから解答できる。これは、

　　２×２×…（ｎ個の２）…×２－３×ｍ

という計算が３の倍数になることがあるかどうかという問題になる。もしこのようなことが成立して、あるｈに対して

　　２×２×…（ｎ個の２）…×２－３×ｍ＝３×ｈ

となったとするとおかしなことになる。上の式を少し書き換えると

　　２×２×…（ｎ個の２）…×２＝３×ｍ＋３×ｈ
　　　　　　　　　　　　　　　　＝３×（ｍ＋ｈ）

となる。そうすると左辺は２のべき乗で２という素因数しかないのに、右辺では３という素因数が出てきてしまう。これは素因数分解の一意性に反するものになる。

以上の考察から得られる結論は、このシステムでは、連続して３つＩが並ぶような文字列は生成が出来ないということだ。もし３つ続けてＩが並ぶような文字列があれば、そのＩをＵで置き換えることが出来る（Ⅲの規則）。そうすれば、そのようなことを繰り返せば、いつかはＩを含まない文字列を作ることが出来るだろう。そうすればⅣの規則によってＵは取り除くことが出来るので、どこかで「ＭＵ」という文字列が定理として登場する可能性がある。

しかしＩという文字は、このシステムの文字列から取り去ることが出来ない。公理に入っている最初のＩは決して消えることなくどの定理にも少なくとも一つは含まれてしまう。そのような「遺伝的性質」をこのシステムは持っている。Ｉが決して消せない文字であるなら、Ｉを含まない「ＭＵ」という文字列は、このシステムでは決して「定理」となることはないであろう。

以上の考察は、すべて日本語によって進められた論理の展開だ。「ＭＵ」が「定理」になるかどうかという考察は、「ＭＩＵシステム」という形式システムの中では、それが「定理」になるのなら、いつかは生成されるということで解決される。しかし、それが「定理」にならないときは、いくらシステムで文字列を生成しても、システムの中ではその問題の解決が出来ない。システムの外から、システムそのものを考察するという視点が必要になる。「メタ的」な考察と呼ばれるこのような思考は、システムについて語る、システムの言語ではないもっと豊かな内容を持った言語が必要だ。

このシステムを考察するのに、普通の日本語は十分豊かな内容を持っていると言えるだろう。上のようにして「ＭＵ」が「定理」ではないことが示される。この考察の中では、途中で整数の性質の考察も含まれていた。これは、上のシステムそのものの考察を、整数の性質を考える自然数論で表現する可能性を示唆する。「ＭＩＵシステム」では、上の考察を表現することは出来ないが、Ｍ，Ｉ，Ｕの文字列に適当に数字を振り分けて、文字列の書き換えという規則の展開を、自然数の計算の解釈して表現することを考えてみる。これがゲーデルのアイデアの核心に近づくものになるのではないかと思う。

自然数論というのは、文字列の書き換え規則というシステムそのものを考察できるくらいに豊かな内容を持っていると言えるのではないかと思う。自然数論によって「ＭＩＵシステム」が考察できるなら、自然数論そのものも形式システムとして展開できれば、そのシステムそのものに対する考察も自然数論の中で行えるだろう。これがゲーデルのアイデアはないかと思われる。

しかし、単純な「ＭＩＵシステム」と違って、自然数論はその内容が豊かで強力なために、自己言及としてちょっと具合の悪いところが出てきてしまうというのがゲーデルの定理が示すものでもあるのではないだろうか。「ＭＩＵシステム」には、完全とか不完全とかいうことを考察の対象にするほどの豊かな内容はないのではないかと思う。そこから導かれる「定理」はごく単純なものばかりで、もしその解釈が求められたとしても、その解釈において正しいとされる文字列はすべて「定理」となるのではないかと思う。もし「定理」とならない正しい文字列を含む解釈があれば、それはその解釈が「ＭＩＵシステム」に比べて、複雑すぎる解釈になっているのだろう。それは、システムが単純であるから、おそらくすぐに見て取れるに違いない。

自然数論は、形式システムとして記述するには複雑で内容が豊かなために、完全か不完全かという問題がはっきりと出てきてしまうのではないかと思う。

次回は、「ＭＩＵシステム」に実際に数を割り当てて、文字列の解釈を自然数の計算で表すというゲーデルのアイデアを感じ取る考察をしてみたいと思う。その方法が、どのようにしてゲーデルの証明につながっているのか、単純なシステムでの類似性としてその理解を深めていけないかということを考えてみたい。