Advanced Turning Machine

Minor Variations on the Turing Machine Theme

• 標準模型

  

• 多個變體

  

  • 證明這些變體 也具備一樣的力量

    
    

    • 代表他們接受相同的語言

      

• 模擬

  

  • configuration 是存在對應的

    
    

• Turing machine with stay

  

  • Example

    

  • 定理

    

  • proof
    • I

      

    • II

      

      • right move

        

      • stay move

        
        

        • Example

• with Multiple Track tape

  
  

• with Semi-infinite tape

  

  • standard 模擬 semi-infinite tape: trivial
  • semi-infinite tatpe 模擬 standard:

    
    

    • with two track

      

    • transition

      

    • Time

      
      

    • At the border

      
      
      

• off-line machine

  

  • off-line simulation standard

    
    
    

  • reverse

    

    • using 4 track

      
      

    • 每次都要回到 reference point
  • 結果

    

Turing Machines with More Complex Storage

• 多磁帶 圖靈機

  
  transition
  

  • multitape simulate standard

    

    • 使用單磁帶
  • reverse

    

    • using multi-track tape

      
      

  • 結論

    

• 速度差異

  

  • 作法

    

• MultiDimensional 圖靈機

  

  • simulation

    
    
    
    

  • 結果

    

• Non-deterministic 圖靈機

  

  • 作法

    

  • 接受字串

    

  • 模擬

    
    

  • 追蹤

    
    
    

    • 實際做法

      
      
      

  • 結果

    

  • 時間花費上 standard要花更多時間

    

• A Universal Turing Machine

  • 限制

    

    • 只能執行一個程式
    • 真實的計算機是可以執行多個程式的
  • 解決方法

    

  • 定義

    

  • 三個tape

    

• encode M as symbol

  

  • alphabet encoding

    
    
    
    

    • 轉移之間的間隔是兩個0

• tape 1

  

  • 可以用01表示圖靈機
  • 圖靈機的集合相當於一個語言

    
    

• Countable Sets

  • 可數集合

    
    

  • Example
    • 偶數

      

    • 有理數

      
      
      
      

• 定義

  

  • 長相

    

  • Enumeration machine

    
    

  • 觀察

    

    • 如果集合存在列舉過程 則可數
  • Example

    

    • 失敗

      

    • 成功

      
      

• 所有圖靈機的集合是可數的

  

  • 圖靈機可以被編碼成01字串
  • 列舉作法

    

• Uncountable Sets

  

  • Example

    

  • proof

    
    

    • Encoding

      

    • 假設是可數的

      
      
      

    • 沿著對角構建一個新字串

      
      

    • 得到矛盾
  • 結果

    

• 應用

  

  • 一個語言是他的子集

    

  • 不可數

    
    

    • 語言的數量超過圖靈機
  • 結論

    

    • 存在一些語言無法用圖靈機描述

      

• Linear Bounded Automata LBAs

  

  • input 磁帶空間被限制

    

  • 威力