アーニーは人の名前で、この本『スマリヤンのゲーデル・パズル』の著者スマリヤンさんの友人。実在するかどうかは知らない。
で、そのアーニーさんはいろいろな機械を作っていて、ここで紹介されているのは、アルファベットの大文字の記号列を操作する機械。
記号列というのは、アルファベット大文字の文字列のことで、別に意味があるとは限らない。BLPQは記号列だし、ARMも記号列。アルファベットの大文字を並べたものを記号列と呼んでいる。
このアーニーの機械は、ある記号列を入力すると、受け付けられれば、通常別の記号列を出力する。いま、この機械を使った問題（パズル）を解いているところだ。
この機械は規則にそって、ある記号列が入力されると、その記号列を操作して、別の記号列を出力する。まあ、実用性はほとんどない機械だけど、この機械の挙動を確認することで、ゲーデルの不完全性定理の理解が深まるという利点はあるかな。
この機械の規則を説明する前に、ちょっと、記号列の書き方や用語の説明をしておくね。
記号列とは、アルファベット大文字の文字列であるということは説明した。任意の記号列を表すために、x, y, zなどの小文字を使う。数学の方程式での未知数xのようなものだ。xが1文字だからといって、1文字の記号列を表すわけではない。（このブログではx1のように添字をつけたものも使う。）
そして、任意の記号列の対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をもたらすだろうか。
（つづく）
0 件のコメント:
コメントを投稿