# Turing Machine

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

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

On Computable Numbers, with an Application to the Entscheidungsproblem

## Deterministic Turing Machine (DTM)

DTM 由一個 7 tuple 所定義
$$(Q, \Sigma, \Gamma, \delta, p_0, b, F)$$其中這 7 tuples 的定義為
- $Q:$ 非空的 States 的集合
- $\Sigma:$ 非空的 Symbols 的集合, $\Sigma\subseteq\Gamma\backslash\{b\}$
- $\Gamma:$ 非空的 Tape Symbols 的集合
:::info
Tape Symbols 就是 symbols 序列


:::
- $\delta:$ 轉換函式
- 定義為 $\delta: Q\times \Gamma\rightarrow \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\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 \Gamma\rightarrow 2^{\Gamma\times(R/L)\times Q}$
- 意思為當前的 state 及 symbol 會轉換成 $(Q, \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

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