【シプサ】4 判定可能性

体調が戻ってきたので、シプサを再開。

• 久しぶりなので、言葉や概念の定義を丁寧におってみる。
  
• 「本章の目的は、アルゴリズム的な解決可能性の限界を探求することである。」
  
  
  
  • この文はテーマの表明かと。「アルゴリズム的な解決」が何を意味するかは定義されていない。
    
  • なので、この章では、「アルゴリズム的な解決」の定義を与え、「その限界を探求する」、ということかな。
    
  
  
• 「アルゴリズム的に解くためには、」
  
  
  
  • 非アルゴリズム的に解くとはどういうことだろう?
    
  • 例えば数学の方程式の解を求める問題で、あてずっぽう(乱数)で正解になるまで数をためすとか?
    
  • ヒューリスティック、と呼ばれていることもそうなのかな?
    
  • ヒューリステヒックって何だ?
    
    
    
    • heuristic: 発見[習得]に役立つ; (自己)発見的学習の
      
    • いまいちわからん。Wikipediaへ。
      
    • Heuristic。なるほど、雰囲気はわかる。日本語の中では何なんだろう? 「発見的学習」なんて日頃使わないし。
      
    • 「試行錯誤」「丼勘定」「テキトー」「下手な鉄砲数打ちゃあたる」。。。ちがうなぁ、試行錯誤はheuristicの一手法にすぎないし。
      
    • Wikithonaryへ。heuristic。そうかギリシャ語のエウレカが語源なのね。
      
    • 「工夫」「善後策」「横紙破り」「徒手空拳」。。。ちがう。「裏技」、おっ裏技がいいかんじ。
      
    • 「見切り発車」「結果オーライ」「善処しました」「一定の成果を得た」。。。もう「裏技」でいいや。
      
    • しかしこんなのもある。Heuristic algorithm
      
    • 問題に対してアルゴリズムが立案できない状況で、なんらかの「裏技」をつかってよさ気なアルゴリズムを採用してしまう。そのアルゴリズムをHeuristic algorithmと言うようだ。
      
    
    
  
  
• 「本節では、アルゴリズムにより判定可能な言語について、いくつかの例を与える」
  
  
  
  • 「アルゴリズムにより判定可能な言語」って何?
    
  • アルゴリズム：とあるTuring機械の仕様
    
  • 判定可能な言語：??? これは未定義かな。なので読み進んで説明をまつ。
    
  
  
• 「ここではオートマトンと文法に関連する言語に注力する。」
  
  
  
  • なるほど。まずここで言っている「言語」は、相変わらず計算理論における言語であり、それはその言語で書かれていると言える文字列の全てからなる集合(巨大です)のことなんだな。
    
  • オートマトンと文法に関連する言語、ということは、その言語の中で、正規言語や文脈自由言語のことだ。
    
  
  
• 「たとえば、文字列が文脈自由言語(CFL)の要素であるかどうかを検査するアルゴリズムを紹介する。」
  
  
  
  • 「文字列がCFLの要素であるかどうかを検査する」というアルゴリズムを紹介する、ということ。アルゴリズムを紹介する、ということは、それを実現するTMを示す、ということであろう。
    
  • では、「文字列がCFLの要素であるかどうかを検査する」というのは何?
    
  • これは前章では認識機構としてのPDAの役目じゃなかったっけ?
    
  • ということは、もったいぶって言ってるけど、PDAをTMがシミュレートできるってことを言ってるのかも。
    
  • 後々明らかになるであろうということで先へ。
    
  
  
• 「オートマトンと文法に関連する別のある種の問題はアルゴリズムによって判定可能ではない。
  
  
  
  • これも「アルゴリズムによって判定可能」の定義がわからんので、現時点では何いってんだかわからない。
    
  
  
• 「有限オートマトンに関連する計算問題から初めよう」
  
  
  
  • 「有限オートマトンに関連する計算問題」って何だっけ?
    
  • 有限オートマトンは、次のようなものだったはず。
    
    
    
    • 有限の状態がある。状態には開始状態と受理状態と、どちらでもない状態がある。
      
    • 入力文字列というものがある。入力文字列を構成する文字の全てをあらいだして、それら全部を要素とする集合をアルファベットという。
      
    • 入力文字列を処理する。
      
    • 入力文字列を処理する、とは、開始状態にあるとして、入力文字列を先頭から1文字ずつ順に処理していく、ということ。
      
    • ひとつずつ順に処理していく、とは、それぞれの状態で、どういう文字だったらどの状態に移動する、というルールにしたがって入力文字列を消費しつつ状態を渡りあるく、ということ。
      
    • このルールを遷移関数と呼ぶ。
      
    • 入力文字列の処理が終わった時点で、受理状態にあれば、「かの有限オートマトンは、この文字列を受理する」と言う。そうでない場合は「拒否する」と言う。
      
    • なので、有限オートマトンの仕様は、5個組、「Q(状態集合)、 Σ(アルファベット集合)、遷移関数、q0開始状態、F(受理状態集合)」で特定できる。
      
    
    
  • で、有限オートマトンの「計算」って何だっけ??? わからないので一巻を見直す。
    
  • そうか、今のべた有限オートマトンの動作定義自体が、「有限オートマトンの計算」の定義なんだ。
    
  • では、「有限オートマトンに関連する計算問題」とは、有限オートマトンがある文字列を受理したり拒否したり、認識したり、というようなよしなし事、ということか。
    
  
  
• 「言語によりさまざまな計算問題を表現することを選んだ点に注意しよう」
  
  
  
  • あれ? どこで選んだっけ?
    
  • というか、ここで言う「言語」は、計算理論における言語か、いわゆる普通の意味での言語なのか???
    
  • たぶん、次の文章(P183)のことを指していると思われる。
    「2番目は、Turing機械がヘッドを動かす方法やテープにデータを格納する方法まで記述するが、それを自然言語で記述する方法である。したがって、より高いレベルの記述だが、実装まで考慮した記述である。このレベルでは、状態や遷移関数の詳細な記述を与えない。3番目は、実装の詳細を無視して、アルゴリズムを記述するために自然な言語を用いた高レベルの記述である。」
    
  • なので、ここの「言語により」というのは「非形式的な記述によって」ということと解釈しておく。
    
  
  
• 「たとえば、特定の決定性有限オートマトンが与えられた文字列を受理するかどうかを検査するようなDFAに対する受理問題は、言語A[DFA]として表現できる。この言語はDFAとそれが受理する文字列の組を符号化したもの全体で、
  A[DFA] = {<B, w> | Bは入力文字列wを受理するDFA}
  で定義される。」
  
  
  
  • なんじゃこりゃ? これ、計算理論としての言語と、TMを記述するための言語がごっちゃになってないか???
    
  • 考える。
    
  • わかった。まさにごっちゃにしているのだ。メタをやってやがるのです。自分の言葉で書いて、確認する。
    
    
    
    • この文章、ひっくり返して読んだ方がわかりやすい。
      
    • まず、Bと呼ばれるあるDFAが存在するとする。Ｂが関係する問題をTMで扱いたいとする。すると、TMで扱えるのは文字列だけなので、Bを文字列で表現しなければならない。その文字列を<B>と呼ぶことにしたのだった。ところで、DFAにおける計算は入力文字列の処理であった。なので、Bが関係する問題をTMで扱うには、入力文字列もTMで扱う必要があるであろう。それも表現を考えなければならない。子細は別にして、とある入力文字列wの表現を<w>と呼ぶことにしたのだった。
      
    • すると、Bにある入力文字列wを計算させるということは、<B, w>という表現(=文字列)でも必要十分であろう。
      
    • ここまでが、自然な言語でアルゴリズムを記述する、という方の意味での言語。
      
    • 続けよう。するとここまでの考えでは<B,w>というのは、Bは固定だが、wはいろいろなものがありえる。で、計算した結果、認識したり(=受理したり)、認識しなかったり(=拒否したり)する。
      
    • すると、文字列たる<B,w>がわらわらいるのだが、それの計算結果が受理なものだけ集めて集合にしちゃえ、と考える。ここで「計算理論の言語」が出てくる。
      
    • で、A[B] = {<B, w> | 「DFAであるBは固定として、wはいろいろで、Bはwを認識する」というような文字列}
      
    • さて、ここで、wが固定でBがいろいろ、というのももちろんあり。
      
    • で、A[w] = {<B, w> | Bは入力文字列wを受理するDFA}
      
    • この集合には、wを受理するDFAがすべて含まれていることになる。
      
    • そして、この集合自体が計算理論における言語であって、この言語をTMで取り扱うことが可能である。どこまで取り扱えるかは別として、やろうとすることはできる。
      
    • それは、うまく行けば、判定可能なTMを構築できるだろう。次善としては、認識可能なTMまでかもしれない。最悪は、認識不可能であり事実上取り扱えない、ということか。
      
    • で、A[w]に対して、TMを構築できて、それが判定可能であるとする。ということは、任意の表現<B, w>について、それが受理するか否かがそのTMで有限のステップというか何というかで判定できるということだ。
      
    • ということは、どういうことかというと、これが前半の文「特定の決定性有限オートマトンが与えられた文字列を受理するかどうかを検査するようなDFAに対する受理問題は、言語A[DFA]として表現できる。」ということがわかったということ。
      
    
    
  
  
• 「同様に、他の計算問題についても、言語に対する所属を検査するという言葉で定式化できる」
  
  
  
  • 計算理論の言語は文字列の集合であり、それを認識したり生成したりする機構をいろいろと考えて、その性質を調べたりしてきた。その際、文字列が受理するかどうかということ自体を計算の定義とした。
    
  • すると、計算問題というのは、様々な認識機構や生成機構と入力文字列との話題になるわけだ。
    
  • するとそれは、「とある機構と、とある入力文字列」というオブジェクトの表現として、また文字列で表現できてしまう。
    
  • すると、計算問題というのは、機構達や入力文字列達について、かくかくしかじかが成立しますか〜ということを問うていると一般的に考えられるので、それは、それが成立する表現を集めた述語的な集合を考えることができる。で、それは文字列の集合だから言語である(ここがメタ)。なので、その言語を機構で調べることができる。
    
  • というようなことじゃないかなぁ。
    
  
  
• なんとなく分かってきた。
  
• 先送りしたことを確認。
  
  
  
  • 「アルゴリズムにより判定可能な言語」
    
    
    
    • ああ、これはそのまんまだったんだな。
      
    • TMにて判定可能となる言語、のことだろう。
      
    • DFAが認識可能な言語が正規言語(という名で呼んでおりその性質は知れている)、PDAが認識可能な言語が文脈自由言語(という名で呼んでおりその性質は知れている)、ということに対して、TMにて判定可能な言語たちってどんなものたち? ということだろう。
      
    
    
  • 「たとえば、文字列が文脈自由言語(CFL)の要素であるかどうかを検査するアルゴリズムを紹介する。」
    
    
    
    • これはまだよくわからない。
      
    • ただ、CFLを調べていた時点では、アルゴリズムという概念が定義されていなかったので、もちろんPDAやCFGを使ってアルゴリズム的な思考はしているわけだが、それをTMでシミュレートすることによってアルゴリズムの定義にしたがって、表現しますよ、ということだと思われる。
      
    
    
  
  

2ページしか進んでいない。なんと。でも、まあ面白かったからいいかな。
こつこつ。