- 「アルゴリズム的に解決不可能な問題がある」
- うーん。ここで「アルゴリズム的に解決不可能な問題がある」という文章自体何言ってるんだかわからない。
- この文章の説明も、本節で実施するのだろうと考えて先に進む。
- うーん。ここで「アルゴリズム的に解決不可能な問題がある」という文章自体何言ってるんだかわからない。
- 解決不可能な問題の一例。
- 2つのものがある。計算機プログラムPと、その仕様書S。
- この2つを入力として動くプログラムUをつくりたい。その仕様は、S通りにPが動作することを検証する、ということ。
- 実は、このプログラムUはつくることができない。
- 2つのものがある。計算機プログラムPと、その仕様書S。
- とすると、「アルゴリズム的に解決不可能な問題」というのは、アルゴリズムが存在できない問題、ということかな。
- A[TM] = {<M,w> | MはTMであり、Mはwを受理する} なるA[TM]という言語は、判定不可能である。
- まず「言語Aは判定可能である」とは、「言語Aについて判定可能なTuring機械が構成できる」ということであり、これは「任意の入力について、それが言語Aに属する場合は受理し、そうでない場合は拒否するTuring機械を構成できる」ということであり、それは「言語Aを判定可能なアルゴリズムが存在する」ということである。
- 「言語Aは判定不可能である」ということは、「言語Aを判定可能なアルゴリズムは存在しない」ということである。
- 次にここでの言語Aとは何か。
- ある文字列wについて、それを受理する(認識可能)TMの表現文字列(含むwの表現)を集めた言語のことだろう。すると、「wを受理する」ということの述語集合のようなものである。
- では、その述語集合たる言語が判定可能であるとはどういうことか。
- その述語集合を判定可能なアルゴリズムが存在する、ということである。
- それはどういうことか?
- 例えば、どのようなwと、どのようなTMに対しても、それらの組み合わせが受理するか拒否するかを判定するようなアルゴリズムが存在する、ということである。
- こう書いてみると、そりゃ無理だろう、と思う。。。
- すると判定不可能ということは、
- 「どのようなwと、どのようなTMに対しても、それらの組み合わせが受理するか拒否するかを判定するようなアルゴリズム」は存在しない。
- よくわからないのは、何にでも通用する全知全能なスーパーアルゴリズムが存在しない、ということをいっているのか、どのようなwとどのようなTMの特定の組み合わせについても、それをアルゴリズムで判定することはできない、といっているのかだ。
- ああ、わかった。正規言語は判定可能なのだから、前者ということだ。
- ところで、「MはTMであり、Mはwを受理する」ってどういうことだっけ?
- wは何らかの対象を文字列で表現したものであった。通常は、それに対して「何か」を計算というか「何か」を検証するためにTMを構成する。その計算の結果として、受理したり拒否したりループしたりする。
- なので、「MはTMであり、Mはwを受理する」というTMを集める、というのはかなり乱暴な話だね。静的な考えというか。集合論的ではある。
- まず「言語Aは判定可能である」とは、「言語Aについて判定可能なTuring機械が構成できる」ということであり、これは「任意の入力について、それが言語Aに属する場合は受理し、そうでない場合は拒否するTuring機械を構成できる」ということであり、それは「言語Aを判定可能なアルゴリズムが存在する」ということである。
- 「...まず、A[TM]がTuring認識可能であることを確認しよう」。了解。
- 認識可能って何だっけ?
- 対象言語の文字列はいずれにせよ受理になるということだけは保証されているということだ。よって、処理にステップ数がかかっているときに、それがループしているのか、それが受理になるのか、拒否になるのかはわからない、ということ。
- ということはA[TM]が認識可能、ということは、とあるTMがwを受理するなら、計算を続けていればいずれは受理となるアルゴリズムは存在する、ということ。
- さて、A[TM]用のTMを作ってみよう。
- U = 「入力<M,w>に対して、(ただし、MはTM、wは文字列)：
1. 入力wに対してMをシミュレートする。
2. Mが受理状態に入るならば受理し、Mが拒否状態に入るならば拒否する。」 - これを万能Turing機械という。
- 「他の任意のTuring機械の記述を用いてその機械をシミュレートする能力がある」
- U = 「入力<M,w>に対して、(ただし、MはTM、wは文字列)：
- さて、これはTMをシミュレートするTMなわけで、ということは結果的な状態は、受理、拒否、ループの3つである。
- 認識可能って何だっけ?
- で、これが判定可能であるかどうかは、ループがループであることを決定する方法があるかないか、ということに依存している。
- このあるかないかのことを「停止問題」とも呼ぶ。
- よって、万能Turing機械が判定可能かどうかは、停止問題のアルゴリズムが存在するかどうか、である。
- 停止問題が判定可能かどうかをしらべる前に、「Turing認識可能でない言語が存在する」ことを確認する。
- 「Turing認識可能でない言語が存在する」とはどういうことか。
- 本来、何か問題を解決しようとしたり、何かを計算しようとして、TMを使う。
- そのとき、問題を表現するための文字列があり、それを計算し、認識したり判定したりするためのTM(の仕様)がある。
- その文字列達を集合論的にながめると、文字列を要素とする集合をなしていると考えられる。それが言語である。
- これを逆に考えて、何らかのルールにしたがって文字列を作り出して言語を成し、それを扱うTMができるかどうかということも考えられる。
- このときに、常にかならずその言語を認識可能なTMを構築できることが理論的に保証されているのかどうか、ということである。
- その何らかのルールというのが、単に文字列をいろいろ生成するためのルールであるのではなく、今、計算したい問題の対象の有意な表現であったとしたら、その問題にアルゴリズムが存在するのかどうか、ということである。
- で、Turing認識可能でない言語が存在する、ということは、「アルゴリズムが存在しない問題が存在する」ということであもある。認識可能⊃判定可能なので、等価な表現ではないが。
- 本来、何か問題を解決しようとしたり、何かを計算しようとして、TMを使う。
- 準備として、すべてのTuring機械の集合が加算であることを示す。
- 「Turing機械Mは文字列<M>に符号化できるので、すべてのTuring機械の集合は加算である」
- なぜいいきれる?
- まず、Mを表現するためのアルファベットをΣとする。ひらがな、でもよいだろう。すると、Σ*は加算である。
- なぜかというと、Σ*の要素を、長さ0、長さ1、長さ2、...という風に分類するとそれぞれの長さに属する要素は有限でしかない。よってそれらとNの一対一対応が可能である。ゆえに加算。
- すると、Mの表現というのは、Σ*からTMの表現じゃないものを省いただけなので、加算。そりゃそうだ。
- なぜいいきれる?
- 「つぎに、すべての言語の集合が非可算であることを示そう。」
- すべての言語の集合って何だ?
- 。。。 わからん。進もう。
- すべての言語の集合って何だ?
- 「すべての無限長の二進文字列の集合は非可算である」
- これは自明でしょう。それは実数と一対一対応だから。
- これは自明でしょう。それは実数と一対一対応だから。
- LをアルファベットΣ上のすべての言語の集合とする、Lは非可算である。
- なるほど。これが「すべての言語の集合」ということか。これはわかる。そして、特性列をつかえば、無限長二進文字列の集合とLとは一対一対応になるのがわかるので、Lは非可算。
- なるほど。これが「すべての言語の集合」ということか。これはわかる。そして、特性列をつかえば、無限長二進文字列の集合とLとは一対一対応になるのがわかるので、Lは非可算。
- TMの集合は加算無限、言語の集合は非可算無限なので、言語の方がはるかに大きい。すると、これら2つの集合をつなぐ一対一対応は存在しない。
- あれ?しかし、このことからだけではTMに認識されない言語があるとはいえないんじゃないの?
- 超強力TMが存在して、非可算個の言語をひとつで認識可能だったらいいじゃん、というのがある。
- まあ、いいや、たぶんそんなことできないから。(妥協)
- 「Turing機械Mは文字列<M>に符号化できるので、すべてのTuring機械の集合は加算である」
- 停止問題の判定不可能性を確認する。
- 「HをA[TM]に対する判定装置とする。」
- HはUみたいなものだけど、Uかどうかはわからなくて、とにかくA[TM]を判定できるTMであると宣言してみる、ということ。
- HはUみたいなものだけど、Uかどうかはわからなくて、とにかくA[TM]を判定できるTMであると宣言してみる、ということ。
- すると、任意のTMたるMと任意の文字列たるwについて、
H(<M,w>) =
受理 Mがwを受理するとき
拒否 Mがwを受理しないとき (拒否するとき、ではない！)
というのは悪くない。 - このHをサブルーチンとするTMを考える。その定義は次のとおり。
- D=「入力<M>に対して：
1. 入力<M,<M>>に対してHを動作させる。
2. Hが出力するものの逆を出力する。すなわち、Hが受理するならば拒否し、Hが拒否するならば受理する」 - <M,<M>>をやることは自由だが、それが本来のMの機能からして意味がある(受理するにしても拒否するにしても)文字列であることは少ないように思う。
D(<M>) =
受理 Mが<M>を受理しないとき (拒否するとき、ではない！)
拒否 Mが<M>を受理するとき - さて、DもTMであるから、Dに<D>を入力することもできる。すると、
D(<D>) =
受理 Dが<D>を受理しないとき
拒否 Dが<D>を受理するとき - これは矛盾である。ゆえにHは存在しない。
- ふむ。背理法はわかった。
- 証明のステップを振り返る。
- Mがwを受理するときにだけ、Hは<M,w>を受理する。
- Mが<M>を受理するときにだけ、Dは<M>を拒否する。
- Dが<D>を受理するときにだけ、Dは<D>を拒否する。
- Mがwを受理するときにだけ、Hは<M,w>を受理する。
- 表で確認する。
- 入力を<M>に限り、Hの動作を表にする。
- Hの前にUを表にする。
＜Ｍ１＞ ＜Ｍ２＞ ＜Ｍ３＞ ＜Ｍ４＞ ．．．
Ｍ１ 受理 受理
Ｍ２ 受理 受理 受理 受理
Ｍ３
Ｍ４ 受理 受理
．
．
． - ほいで、H。
＜Ｍ１＞ ＜Ｍ２＞ ＜Ｍ３＞ ＜Ｍ４＞ ．．．
Ｍ１ 受理 拒否 受理 拒否
Ｍ２ 受理 受理 受理 受理
Ｍ３ 拒否 拒否 拒否 拒否
Ｍ４ 受理 受理 拒否 拒否
．
．
． - するとDもTMだからこの中にいる。Dは＜Ｍ，＜Ｍ＞＞が受理するとき拒否するので、この表から＜Ｄ，＜Ｍ＞＞を算出していく、
＜Ｍ１＞ ＜Ｍ２＞ ＜Ｍ３＞ ＜Ｍ４＞ ．．．
Ｍ１ ＊受理＊ 拒否 受理 拒否
Ｍ２ 受理 ＊受理＊ 受理 受理
Ｍ３ 拒否 拒否 ＊拒否＊ 拒否
Ｍ４ 受理 受理 拒否 ＊拒否＊
．
．
．
Ｄ 拒否 拒否 受理 受理
．
．
． - すると入力が＜Ｄ＞のときに困ってしまう。
＜Ｍ１＞ ＜Ｍ２＞ ＜Ｍ３＞ ＜Ｍ４＞ ．．．＜Ｄ＞．．．
Ｍ１ ＊受理＊ 拒否 受理 拒否 何か
Ｍ２ 受理 ＊受理＊ 受理 受理 何か
Ｍ３ 拒否 拒否 ＊拒否＊ 拒否 何か
Ｍ４ 受理 受理 拒否 ＊拒否＊ 何か
．
．
．
Ｄ 拒否 拒否 受理 受理 ？
．
．
． - どう困るかというと、？のところは、それ自身の否定でなければならなくて、そんなものは存在しないから困るということ。
- これにて停止問題を判定可能なTMは存在しないことがわかった。
- A[TM]は認識可能だが、判定不可能である。
- 続いて、Turing認識不可能な言語について調べる。
- 「任意の言語に対して、それがTuring認識可能かつ補Turing認識可能であるとき、かつそのときに限り、その言語は判定可能である。」
- これは簡単にわかる。
- これが了解できれば、A[TM]が判定可能でないのだから、A[TM]の補集合はTuring認識可能ではない。
- 「HをA[TM]に対する判定装置とする。」
- この本が言っていることはわかった。
- ここで述べられていること自体は面白いことだ。
- でも、それが私に具体的にどう意味があるのかはまだわからない。
- まずは演習をやってみて、何か感じるかだろう。その次は先々の章をやるにあたって、これが意味をもつかだろう。
結構タフだった。道のりは長い。。。
次回は演習。
0 件のコメント:
コメントを投稿