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

『ゲーデル、エッシャー、バッハ』で解説されているMIUシステムについて、これを文字列ではなく数字で表現することの意味を考えてみたいと思う。これは、ゲーデルの証明におけるゲーデル数の表現の解説として受け取ることが出来る。形式システムとして文字列で表現されている自然数論を、数の間に成立する関係を文字列の表現にしてしまおうというアイデアの構造を理解するための解説として考えてみようと思う。文字列の解釈として、ある意味では自然言語での表現の意味に受け取れる自然数論を、数の間に成立する命題として解釈してしまおうというアイデアを直感的に理解するために、MIUシステムと自然数論の間に成立する同型写像を見てみよう。

さて、MIUシステムは次のように語られていた。


記号  M,I,U
公理  MI
規則
 1 xIが定理ならば、xIUは定理である。
 2 Mxが定理ならば、Mxxは定理である。
 3 任意の定理において、IIIはUで置き換えることが出来る。
 4 任意の定理において、UUは除くことが出来る。


このM,I,Uという3つのアルファベットで表現される文字列を、3つの異なる数字で表現して、数字の表現のシステムにおいても、MIUシステムが持つ構造が同じ形で反映されるように表現してみよう。M,I,Uの3つの異なるアルファベットに、3つの異なる数字を与えるのは、これは異なってさえいれば、つまり区別が出来れば何でもいい。これがゲーデル数に当たるものになる。



この本では

   M …… 3
   I …… 1
   U …… 0

の3つの数字を使っている。MIUシステムでは、使われる文字はこの3つだけなので、数字も3,1,0以外は使う必要がない。上のMIUシステムの定義の中の3つの文字をこの3つの数字に置き換えると次のような表現になる。


記号  3,1,0
公理  31
規則
 1 x1が定理ならば、x10は定理である。
 2 3xが定理ならば、3xxは定理である。
 3 任意の定理において、111は0で置き換えることが出来る。
 4 任意の定理において、00は除くことが出来る。


これは、単に文字列を書き換えただけなのでもちろん構造はMIUシステムと同じになる。しかし、この表現ではゲーデルのアイデアを感じることは出来ない。なぜ文字を数字にするかということの本質がこれでは見えてこないからだ。この定義では、数字は単に文字の代わりを務めるだけのものに過ぎない。数字本来の性質は使われていない。数字本来の性質とは、それが計算できるということで、上の定義の中の文字列の表現が、数字の計算として表現できたとき,ここにゲーデルが使ったアイデアの一端が見えてくる。

上の公理を31(さんいち)という文字列として読まずに、31(さんじゅういち)という数字として読み、規則を文字列の書き換えとして読まずに、計算規則として書き換えると次のようになる。


1 <10m+1>が作られている
      ↓
  <10×(10m+1)>を作ることが出来る
 (文字列の後ろに1があればということが(10m+1)で表現されている。そしてそのときに文字列の後ろに0を付け加えることが出来るということが(10×)というかけ算で表現されている。)

2 <3×10^m(10のm乗と読む)+n>が作られている
      ↓
  <10^m×(3×10^m+n)+n>を作ることが出来る
 (3の後ろに文字列がm個つながっているということを(3×10^m+n)で表現している。nはm個の文字列、つまりm桁の数として考えられている。このnが文字列の表現ではxに当たるものになる。規則ではこのときさらに後ろに文字列xを付け加えることが出来ることを語っている。それは、m桁ずらすために(10^m×)というかけ算をし、その後ろにm桁の数nを加えることで表現している。)

3 <k×10^(m+3)+111×10^m+n>が作られている
      ↓
  <k×10^(m+1)+n>を作ることが出来る
 (文字列の間に111があったときということを、10^mの位置にある(つまり(m+1)桁目の位置から3つ1が並んでいる)考えている。その1の前には3を先頭にするkという数字が並んでいる。後ろにはm桁の数nが並んでいる。規則では111という3桁の1を取り除くので、計算としてはm桁の数nと(m+1)桁目からの数kとが並ぶ数字になる。)

4 <k×10^(m+2)+n>が作られている
      ↓
  <k×10^m+n>を作ることが出来る。
 (4の規則では二つ並んでいる0を取り除くことが出来る。それは(10^(m+2))が10^mになることで10のべき乗が二つ減ることで表現されている。上の計算の表現での前件は、m桁の数nの前に0が二つついていると解釈することが出来る。)


このように表現を変えると、M,I,Uという3つの文字列を、単に数字という文字に置き換えたのではなく、自然数の計算として解釈した構造の表現になっている。つまり、MIUシステムで文字列の書き換えとして考えていたものが、数における計算として理解され、その計算結果がどうなるかということがMIUシステムの構造を考えることと同じものになる。MIUシステムの構造が自然数の計算として写像されていることになる。文字列の形式システムが自然数論の中に取り込まれた。

このアイデアの解説は次のように書かれている。ここで「310システム」と呼ばれているのは、数の計算として表現されたMIUシステムと同型のシステムを指す。


「この「310システム」にも、延長規則と短縮規則が絶えずつきまとっていることに注意。これらの規則はただ数の領域に移されただけなので、ゲーデル数が大きくなったり小さくなったりする。そこで行われていることを注意深く眺めれば規則を発見できるが、その着想は整数の10進法で表示された数字を右や左にずらすことと、10のべきの乗法や除法に結びつけるということに過ぎず、深遠なものではない。この簡単な知見は次のように一般化できる。

中心命題:
10進法で表示されたいかなる数においても、ある数字をどのようにずらし、変更し,除去し,あるいは挿入するかを教える字形的規則があれば、加法、減法そのほか10のべきに対する算術的演算を含み、この規則に対応する算術的規則によっても同じように表現できる。

 もっと簡単に言えば……

<数字を処理する字形的規則は、実際は数に作用する算術的規則である。>」


このアイデアは、ゲーデルの証明において重要な部分を占めるものとなるだろう。形式システムにおける公理や推論規則による文字列の書き換えは、「字形的規則」として語られる。その「字形的規則」において、それを数値化し(ゲーデル数化する)、数字の位置をずらしたり、書き換えるという規則にすることが出来れば、それは計算として記述できるということを上の命題は語っている。

形式システムにおける証明の問題は、文字列の書き換えの中である規則に従ったものを「証明可能である」といい、その規則に従わないものを「証明可能ではない」という。これは、文字列を数値化することが出来れば、「計算可能である」あるいは「計算可能ではない」という言い方にすることが出来る。計算体系を持つ自然数論の中に写像出来る。

ゲーデルは、このアイデアによって自然数論における「証明可能性」を自然数論の中の「計算可能性」に置き換えて、「証明可能である」ということを「計算可能だ」という命題に置き換えた。これは、実際に証明可能だということが言える文字列に関しては、その書き換えに対応する計算を記述できるので、「計算可能だ」ということが言えるようになるだろう。問題は、すべての文字列に対して「証明可能」かどうかが判定できるかどうかということが「完全性」という問題では重要になってくることだ。「証明可能である」ことが分かっている文字列に関しては「計算可能である」ことが分かる。それが任意の文字列に対して成立するかどうか。任意の数字に対して,それが計算可能であるかないかが判定できるかどうか。

この問題を考えるときに、「証明可能でない」ということが判る文字列が見つかったらどうなるだろうか。MIUシステムにおいてはMUは証明できないことが分かっている。310システムとして考えると30は証明できない。つまり、計算規則によって算術的な計算は出来ない数字になる。

この「計算可能でない」という性質は、かけ算と足し算だけの算術的計算によって表現することは出来ない。表現できてしまうと「計算可能」になり矛盾するからだ。「計算可能でない」性質は計算として表現することは出来ないが、メタ的な命題としては表現できる。自然数論ではなく自然言語としての日本語では表現できる。これを自然数論の中に埋め込む方法があるだろうか。もしこれが出来れば、「計算可能でない」性質が「計算可能」になる。パラドックス的な状況が見えてくるだろう。そうすれば、システムに矛盾がなければ、このような状況が起こることは考えられない。そうすると、そのように「計算可能」でないことが「計算可能」になる表現は、実はどちらにも決定できないものかもしれない。

ゲーデルは、自分自身に対して「私は証明できない」と解釈できる表現を作ったと言われている。このような表現が本当に出来るのかどうか、MIUシステムでメタ的な表現を自然数論の算術的表現として作れるかどうかを考えることで比喩的に理解できないだろうかを考えたい。MIUシステムにおいて,そこでの証明可能性を算術的計算を解釈することで決定できるかどうか。そして、それが決定できたとき、証明不可能性も算術的に表現できるかどうか。そのあたりのことを考えてみたいと思う。
[PR]
by ksyuumei | 2008-10-27 10:24 | 論理


<< 図と地という視点 関数・写像の考え方とゲーデルの定理 >>