歡迎來到圖靈機（Turing Machines）的世界！
別擔心，如果這章內容一開始看起來有點嚇人！圖靈機（TM）是計算機科學中最基礎且優美的概念之一。它是由艾倫·圖靈（Alan Turing）在 1930 年代所設計，旨在回答一個宏大的哲學問題：
「什麼才叫做『可計算』（Computable）？」
這份筆記將為你拆解艾倫·圖靈的理論機器，解釋它的組成部分，以及為什麼它定義了現代電腦能力的極限。理解圖靈機是掌握計算理論（Theory of Computation）核心的關鍵。
3.13.3 圖靈機的構造
圖靈機是一個簡單的抽象計算模型。雖然它看起來很基本，但在理論上，它有能力執行現代數位電腦能做的任何計算。它被視為一台擁有單一固定程式的電腦。
類比：裝配線上的機器人
試著將圖靈機想像成一個在無限長的裝配線上工作的極簡機器人：
- 它在一條長長的輸送帶（即紙帶，tape）上運作。
- 它可以使用機械臂（即讀寫頭，read-write head）來讀取、寫入和擦除符號。
- 它會根據當前的內部狀態（即狀態，state），嚴格遵守一套規則（即轉移規則，transition rules）來執行動作。
圖靈機的五大基本元件
圖靈機的單一固定程式是由以下五個理論部分所定義：
1. 無限長的紙帶（Infinite Tape）
這充當了圖靈機的記憶體以及輸入/輸出空間。它被劃分為一個個帶格（marked-off squares）。
- 紙帶上儲存了一系列的符號。
- 關鍵在於，紙帶被視為向一側無限延伸（雖然概念上常被表示為向兩側無限延伸，但考試重點在於單向模型）。
2. 有限的符號字母表（Finite Alphabet of Symbols）
這是指能寫入紙帶上的有限字符集合（例如 '0'、'1'，以及一個代表「空白」的特殊符號）。
注意：本課程大綱並不區分輸入字母表（初始數據中允許的符號）和紙帶字母表（機器能使用的所有符號）。
3. 感應讀寫頭（Sensing Read-Write Head）
這是實際工作的核心部件，它可以：
- 讀取（Read）目前所在的帶格中的符號。
- 寫入（Write）（或重寫）一個新符號到該帶格中。
- 移動（Travel），沿著紙帶一次移動一格（向左或向右）。
4. 有限的狀態集合（Q）
機器始終處於有限個內部配置中的其中一種，這些配置稱為狀態（states）。
- 起始狀態（Start State）是計算開始時所處的特定狀態。
- 停機狀態（Halting States）是指沒有對外轉移路徑的狀態。當圖靈機進入這些狀態之一時，計算就會停止。
5. 轉移規則（Transition Rules / The Program）
這些規則決定了機器的行為。它們通常透過轉移函數（transition function）或狀態轉移圖（state transition diagram）來定義。
圖靈機的表示與追蹤
轉移規則的格式
圖靈機的每一步都由規則引導。規則基於機器當前的情況（當前狀態與讀取的符號）並定義後續的動作。
規則的格式如下：
(當前狀態, 讀取的符號) \(\rightarrow\) (新狀態, 要寫入的符號, 移動方向)
例如，一條規則可能是：
\((q_1, 0) \rightarrow (q_2, 1, R)\)
解釋：如果機器處於狀態 \(q_1\) 且讀到一個 '0'，它會轉變到狀態 \(q_2\)，將 '0' 改寫為 '1'，並將讀寫頭向右（R）移動。
轉移函數 vs. 狀態轉移圖
你必須理解，轉移函數（形式規則的清單）與狀態轉移圖（視覺化的地圖）是描述圖靈機程式的等價方式。
- 圖表：狀態用圓圈表示，轉移路徑用帶有標籤的箭頭表示。這通常更容易視覺化追蹤。
- 函數：一份完整且明確的清單，列出所有可能的移動方式。
手動追蹤簡單的圖靈機
追蹤是按順序執行圖靈機步驟以確定最終輸出的過程。你必須隨時掌握三件事：
- 當前狀態（Current State）。
- 紙帶內容（Tape Contents）。
- 讀寫頭位置（Head Position）。
常見錯誤提醒：請務必依照規則規定的正確順序執行動作：
先寫入新符號，接著移動讀寫頭，最後變更狀態。
本節重點（小結）：
該過程是決定性的（deterministic）：對於任何給定的（狀態, 符號）組合，只有一個明確的下一步。機器會一直運行，直到進入停機狀態為止。
圖靈機的重要性與能力
什麼是可計算的？
圖靈機之所以重要，是因為它提供了通用（形式化）計算模型。它為我們提供了對「演算法」一詞精確且數學化的定義。
如果一個問題可以透過演算法解決，我們稱該問題為可計算的（computable）。如果圖靈機能解決某個問題，它就是可計算的；若不能，則該問題是不可計算的（至少無法透過演算法解決）。
通用圖靈機（Universal Turing Machine, UTM）
雖然標準圖靈機被硬編碼成只能解決一個特定問題（例如加法），但艾倫·圖靈引入了一種機器，它可以解決任何特定圖靈機所能解決的問題。
UTM 的定義
通用圖靈機（UTM）是一種特殊的圖靈機，它能夠模擬任何其他圖靈機（M）的行為。
UTM 的工作原理
UTM 不再將自身的程式固定在內部，而是利用它的紙帶作為儲存指令的空間，這使得它就像一台可程式化的電腦。UTM 的紙帶包含：
- 被模擬機器 M 的描述（即 M 的轉移規則、字母表和狀態）。
- 機器 M 預期要處理的輸入數據。
UTM 讀取 M 的描述，並將 M 的規則應用於輸入數據上。這實際上就是執行在硬體上的軟體。
為什麼 UTM 很重要？
UTM 證明了單一機器（UTM 硬體）可以執行無數種專用機器（被模擬的圖靈機）的工作。這個概念為現代的儲存程式概念（Stored Program Concept）（馮·紐曼架構）鋪平了道路，即機器碼指令（程式描述）與處理數據儲存在同一個記憶體中。
快速複習箱：TM vs UTM
- 標準 TM：程式固定，只能解決一個問題。
- UTM：可程式化，只要紙帶上提供了機器的描述及輸入，就能解決任何問題。
章節總結：重點摘要
1. 結構：圖靈機包含五個部分：無限紙帶、有限字母表、讀寫頭、有限狀態、轉移規則。
2. 運作：圖靈機的行為由其當前狀態和讀取的符號定義。它以決定性的方式運作，直到抵達停機狀態（沒有對外轉移路徑的狀態）。
3. 重要性：圖靈機為可計算性提供了正式定義。如果一個問題無法被圖靈機解決，它就是不可計算的。
4. UTM：通用圖靈機是一個革命性的概念，它展示了單一機器可以模擬任何其他機器，形成了現代可程式化電腦的理論基礎。