歡迎來到機器與計算建模的世界！
哈囉各位電腦科學家！這一章聽起來可能非常理論化，但實際上它探討的是構成每一台電腦、手機和電子遊戲背後運作的基礎規則。
我們將探索如何使用簡單的理論機器來代表複雜的現實世界系統。理解這些基本的構建模組至關重要，因為它們定義了電腦可以做什麼以及不能做什麼。如果起初覺得這些概念有些棘手，別擔心——我們會透過日常生活的例子將一切拆解開來！
第一節：什麼是計算建模？
理解模型的必要性
在電腦科學中，計算模型 (Computational Model) 是對現實世界中的流程、系統或物件進行簡化後的表達。我們使用這些模型來研究複雜系統，而無需直接建立實體或進行實驗。
你可以把它想像成在製造實體汽車之前先製作模型車。模型車（即模型）能幫助工程師以低廉且快速的方式，了解物理原理、效能以及設計上的缺陷。
計算建模的主要目的：
- 預測：預測接下來會發生什麼（例如：天氣預報）。
- 理解：幫助我們觀察複雜系統如何互動（例如：模擬交通流量）。
- 測試：安全地嘗試各種不同情境（例如：在模擬器中測試飛行控制）。
- 設計：在撰寫正式程式碼之前先制定計劃。
重點摘要：模型將複雜的世界簡化為電腦可以處理的易用規則。
第二節：有限狀態機 (FSMs)
認識最簡單的機器模型
其中一個最常見且最容易理解的計算模型就是有限狀態機 (Finite State Machine, FSM)。FSM 是一種在任何給定時間內，只能處於數量有限且固定之情況（稱為狀態, states）的機器。
機器會根據接收到的特定輸入 (inputs) 在這些狀態之間移動。這種移動稱為轉移 (transition)。
FSM 的三個核心組件：
- 狀態 (States)：機器當前的情況或條件。狀態的數量永遠是有限的 (finite)。
- 輸入 (Inputs)：觸發機器做出反應的訊號或數據。
- 轉移 (Transitions)：規範機器在接收到特定輸入時，應轉換至哪個狀態的規則。
現實世界範例：交通燈
交通燈是有限狀態機的完美範例。
想像一個控制單一車道交通的交通燈。
狀態：
- 狀態 1：紅燈（停止）
- 狀態 2：紅燈與黃燈（準備出發）
- 狀態 3：綠燈（行駛）
- 狀態 4：黃燈（準備停止）
轉移（促使它移動到下一個狀態的原因）：
- 如果燈號是紅燈，輸入（時間流逝）會導致轉移至紅燈與黃燈。
- 如果燈號是綠燈，輸入（時間流逝）會導致轉移至黃燈。
請注意，燈號不能直接從紅燈跳轉到綠燈——它必須遵循設定好的轉移路徑！
✅ 快速複習：FSMs
FSM 非常適合用於模擬具有固定規則和有限選項的系統，例如簡單的使用者介面、驗證檢查（如檢查密碼是否有效），或是控制系統。
第三節：通用模型 —— 圖靈機
艾倫·圖靈與計算的極限
雖然 FSM 對於簡單系統很有用，但在 1930 年代，數學家艾倫·圖靈 (Alan Turing) 開發了一種理論模型，它能夠執行現代電腦所能完成的任何計算任務，無論該任務多麼複雜。這個模型被稱為圖靈機 (Turing Machine, TM)。
圖靈機並非你能買到的實體電腦；它是一個思想實驗，用來精確定義什麼是計算，以及機器能解決哪些問題。
圖靈機由什麼組成？
圖靈機出人意料地簡單，卻強大得不可思議。它由三個主要部分組成：
- 無限長的紙帶 (Infinite Tape)：這充當機器的記憶體。它被劃分為多個格子，每個格子存放一個符號（通常是 1 或 0，或空白）。關鍵在於，紙帶的長度是無限的，意味著機器永遠不會用盡記憶體。
- 讀寫頭 (Read/Write Head)：該裝置一次位於紙帶的一個格子上。它可以：
- 讀取當前格子中的符號。
- 寫入一個新符號到當前格子中。
- 向左或向右移動一個格子。
- 狀態暫存器 (State Register)：這保存了機器的當前狀態（類似於 FSM 中的狀態）。狀態決定了讀寫頭下一步要做什麼。
逐步過程：機器讀取符號並查看其當前狀態。基於這兩者（符號 + 狀態），它遵循規則：1) 寫入一個新符號，2) 移動讀寫頭（向左/向右），以及 3) 轉換到一個新狀態。它會重複此過程，直到進入「停止 (HALT)」狀態。
為什麼圖靈機很重要？
現今的任何電腦系統，從速度最快的超級電腦到最簡單的智慧型手機，其功能都等同於圖靈機。
- 能夠模擬任何其他圖靈機的機器稱為通用圖靈機 (Universal Turing Machine, UTM)。
- 這個概念證明了一種單一的、標準類型的機器可以解決每一個可計算的問題。這就是為什麼你的筆記型電腦可以執行遊戲、試算表和網頁瀏覽器——因為它是一台 UTM！
💭 你知道嗎？圖靈完備性 (Turing Completeness)
如果一種程式語言或計算裝置的功能強大到足以執行圖靈機所能進行的任何計算，它就被稱為圖靈完備 (Turing Complete)。幾乎你所聽過的每一種通用程式語言（如 Python 或 Java）都是圖靈完備的。
第四節：可解性與計算的極限
機器可以解決哪些問題？
圖靈機模型幫助我們判斷一個問題是可計算的 (computable)（即機器可以解決），還是不可計算的 (non-computable)（即不可能透過演算法解決）。
要使一個問題成為可計算的，我們必須能夠建立一套有限且明確無誤的步驟（即演算法），讓圖靈機可以遵循並達到解決方案，最終停止 (halt)。
常見陷阱：停機問題 (The Halting Problem)
不可計算問題中最著名的例子之一就是停機問題。
停機問題詢問的是：是否有可能寫出一個通用演算法，能夠觀察任何其他程式及其輸入，並正確判斷該程式最終是會執行完畢（停機）還是會陷入無限迴圈永遠執行下去？
艾倫·圖靈證明了這樣的演算法是不存在的。機器不可能可靠地預測 *每一個* 其他任意程式是否會停機。這為電腦能做的事情設定了一個根本性的極限！
記憶小撇步：電腦很強大，但它們也有極限！停機問題證明了電腦無法完美預測所有其他程式的未來行為。
重點摘要
我們使用計算模型（如 FSM 和圖靈機）來定義、簡化和測試現實世界的系統。
- 有限狀態機 (FSM) 使用有限數量的狀態和預先定義的轉移來模擬簡單的流程。
- 圖靈機 (TM) 是計算的理論定義，使用無限長的紙帶和讀寫頭。它證明了一種簡單的機器就能執行任何可解的任務。
- 停機問題證明了計算是有極限的；有些邏輯問題在本質上是不可計算的。
請繼續練習如何在簡單的情境（如電燈開關或密碼鎖）中識別狀態和轉移。你已經掌握了定義現代計算的核心概念！做得好！