Standard Turning Machine

The Standard Turing Machine

• 語言的層級

  
  

• 圖靈機

  

  • tape

    

  • 做甚麼

    

  • Example

    
    

• Input string

  

  • 輸入不能是空的

    

• turing machine的定義

  

  • 狀態轉移

    

    • program

      
      

• Turing machine 是 deterministic

  

• Transition function

  
  

• 暫停

  

• final state

  

  • 最終狀態沒有向外延伸的轉移

• 接受與否

  

• Example

  

  • accept

    
    
    
    
    

  • reject

    
    

  • infinite loop

    
    
    
    
    
    

• 

  • 輪流標記一個a 一個y
  • 全部標記完後 把所有的y parser掉

    

• configuration

  

  • move

    
    

  • 如何表示

    

  • init

    

• accepted language (接受的語言)

  

• 標準圖靈機

  

Computing Functions with Turing Machines

• 函數

  
  

  • 可能存在多個參數

• 整數域

  

  • 較偏好unary

• 什麼樣的函數 是圖靈可計算的

  
  

  • Example

    
    
    

  • 0 被用於當作分隔符號

    

  • Turing machine

    

  • counting Example

    

• Example

  

  • 作法

    

  • 答案

    

• Example

  

  • 圖靈機的輸入與輸出

    

  • match x的1 跟y的1

    

Combining Turing Machines for Complicated Tasks

• 流程圖

  
  

• 微指令

  

• a*b

  

Turing’s Thesis

• 圖靈的論文

  
  

• 電腦科學法則

  

• 演算法的定義

  

  • 其實就是圖靈機

    

• QUIZ