Turing Machine

為一描述所有可計算的函式的數學模型，也就是此模型可計算所有演算法上可計算的問題。

提出此模型當初是用來證明沒有有效的通用解法來解決 Entscheidungsproblem，也就是 decision problem。

On Computable Numbers, with an Application to the Entscheidungsproblem

Deterministic Turing Machine (DTM)

DTM 由一個 7 tuple 所定義

$$(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,p_0,b,F)$$其中這 7 tuples 的定義為

• $Q:$ 非空的 States 的集合
• $\mathrm{\Sigma }:$ 非空的 Symbols 的集合,
  $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\mathrm{\setminus }\{b\}$
• $\mathrm{\Gamma }:$ 非空的 Tape Symbols 的集合

Tape Symbols 就是 symbols 序列

• $\delta :$ 轉換函式
  • 定義為
    $\delta :Q\times \mathrm{\Gamma }\to \mathrm{\Gamma }\times (R/L)\times Q$
  • 意思為當前的 state 以及 tape symbol 經過轉換函式會向 tape 的左或右移動得到新的 state 跟複寫原本的 tape symbol
  • 以下圖為例，其表示式為
    $\delta (q_0,S_0)=(q_1,X_0,R)$
    
• $p_0:$ 初始 State,
  $p_0\in Q$
• $b:$ 空白的 Symbol,
  $b\in \mathrm{\Gamma }$
• $F:$ 最後的 States 的集合,
  $F\subseteq Q$

Non-Deterministic Turing Machine (NTM)

NTM 跟 DTM 最主要的差別在於 DTM 只要給定當前的 state 及 symbol 經由轉換函式就會決定下一個唯一的 state 及新的 symbol。但在 NTM 給定當前的 state 及 symbol 並不會決定下一個唯一的 state 及新的 symbol，而是會有很多可能的 state 及 symbol。

• $\delta :$
  • 定義為
    $\delta :Q\times \mathrm{\Gamma }\to 2^{\mathrm{\Gamma }\times (R/L)\times Q}$
  • 意思為當前的 state 及 symbol 會轉換成
    $(Q,\mathrm{\Gamma },\{R,L\})$ 的集合

既然每次給定 NTM 一個 state 及 symbol 其轉換結果並非單一而是集合，那我們要怎麼知道 NTM 最後計算的結果 (i.e 最後的 state)?

這裡定義三種情況:

1. 當一直轉換得到的集合有一最後的 state 為 accept 則經由 NTM 計算的結果為 accept
2. 當一直轉換得到的集合所有最後的 state 都是 reject 則經由 NTM 計算的結果為 reject
3. 當一直轉換卻都不會得到最後的 state 是 accept 也不會得到全部最後的 state 為 reject 則為 loop

Decision Problem

是否存在一個演算法可以決定任意 mathematical statement 是對或錯的問題。

Halting Problem

是否能判斷任意一個程式能在有限的時間之內結束執行的問題。