2008年 10月 20日 ( 1 )

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

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


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


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

More
[PR]
by ksyuumei | 2008-10-20 10:24 | 論理