【シプサ】5 帰着可能性 (その2)

こつこつ。

• 計算履歴を用いた帰着可能性
  
  
  
  • 「A[TM]をある特定の言語に帰着可能であることを証明するための重要な手法」
    
  • 「判定不可能性を示そうとする問題が何かの存在を調べることを含むとき、この手法はしばしば役に立つ」
    
  • 計算履歴とは、開始状況と「なんらかの状況」をつなぐような計算状況の列のこと。なんらかの状況が受理状況であるならば受理計算履歴と呼ぶ。拒否状況ならば拒否計算履歴と呼ぶ。計算履歴は有限の列であり、停止しない動作については存在しない。
    
  
  
  
• 線形境界付きオートマトン (linear bounded automaton)
  
  
  
  • テープが有限というのはわかるのだけれど、
    
  • 「テープ・アルファベットを入力アルファベットに比べて大きくとることによって、使用できるメモリを定数倍まで増加できる」
    
  • というのがわからない。。。
    
  • 定義がこれほど理解できないのは由々しきこと。掟破りだがWikipediaへ。
    
    
    
    • 「チューリングマシンと異なるのはLBAのテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する」
      
    • ぬ、テープの長さは動的なのか?
      
    • Linear Bounded Automata によると「Definition. A linear bounded automaton (lba) is a multi-track Turing machine which has only one tape, and this tape is exactly the same length as the input.」とな。シプサの定義ともWikipediaの定義とも違う。
      
    • これらを繋ぐ説明 Linear-Bounded Automata 。これでわかった。
      
    • すなわち、入力文字列長さnはもちろん可変。そのk倍のテープ長であることになる。ここでkはオートマトン毎に固定。なので、実際のテープ長であるknは入力につれて動的。
      
    • これを実現する方法として、いまのところ、三つの方法をみた。
      
      
      
      • k=1として、テープアルファベットの数をます。あたかもknのテープ長があるようになるようにテープアルファベットを増すということ。
        
      • ひとつのテープとしてはk=1として、複数テープ(k本)用意する方法。
        
      • ひとつのテープの長さをknとする方法。
        
      
      
    
    
  • ここではあたりまえだがシプサの定義で進める。
    
  
  
  
• LBA Mが、q個の状態とg個のテープアルファベットをもつとき、長さnの入力文字列において、q*n*(g^n)個の異なる計算状態が存在しうる。ユニークな計算状態はこれで尽きている。
  
• このとりうる状態の数が有限で、ループに関する考察をするというのが、ポンピング補題との関連を感じる。
  
  
• A[LBA] = {<M, w> | Mは文字列wを受理するLBA}
  
• 「A[LBA]は判定可能である」
  
  
  
  • これは簡単。存在しうる計算状態の数が有限なので、そのステップを超えたときそれはループということだから拒否してよい。
    
  
  
  
• E[LBA] = {<M> | LBA M は L(M) = 空集合}
  
• あるLBAがあたえられたとき、それがまったく何も受理しないLBAかどうかを判定するアルゴリズムがあるかどうか、ということ。
  
• 「E[LBA]は判定不可能である」
  
• それは無い、ということ。
  
  
  
  • 結構むずかしい。
    
  • もやもや考えると徐々にわかってきた。
    
  • しかしもう業務なので、次回、整理することにする。
    
  
  

こつこつ。