| 範疇 | 子範疇 | 描述 |
|---|---|---|
| 圖靈機 | 確定性圖靈機 | 運算理論中常見的運算模型 |
| 運作原理 | 讀取分為若乾個格的帶，格內包含符號 (如 1, 0) | |
| 基本作業 | 可進行三種作業之一： | 讀取器操作 |
| – 讀取符號，並將讀取器移右一格 | – 寫入符號 | |
| 狀態轉移 | – 移右讀取器，不寫入符號 | |
| 輸入 | 輸入符號串編碼在帶上 | |
| 接受 | 進入指定狀態時接受輸入 | |
| 拒絕 | 進入指定狀態時拒絕輸入 | |
| 描述數 | 編碼圖靈機的行為的數字串 | |
| 可計算數 | 由圖靈機以小數形式印出的數 | |
| 通用圖靈機 | 模擬任意圖靈機 | |
| 停機問題 | 判定描述數是否會停止圖靈機 | |
| 康託爾對角線法 | 證明停機問題無解 | |
| 人工智慧 | 模擬人腦思考過程 |
圖靈機：運算理論的基石
圖靈機是一種抽象機器，由艾倫·圖靈於 1936 年提出，作為研究可計算性的模型。圖靈機的概念在運算理論中扮演著至關重要的角色，因為它定義了計算的極限。
圖靈機的基本架構
圖靈機由以下組成：
- 無限長的帶狀紙帶：帶狀紙帶被劃分為方格，每個方格可以儲存一個符號。
- 讀寫頭：讀寫頭可以在帶狀紙帶上移動，讀取或寫入符號。
- 狀態寄存器：狀態寄存器儲存著圖靈機當前的狀態。
- 動作表：動作表是一個映射，定義了圖靈機在每個狀態下，根據讀寫頭所讀取的符號，應該執行的動作，包括寫入符號、移動讀寫頭和切換狀態等。
圖靈機的運作
圖靈機根據以下步驟運作：
- 讀取帶狀紙帶上讀寫頭所在方格的符號。
- 根據動作表，執行對應當前狀態和讀取符號的動作。
- 更新狀態寄存器中的狀態。
- 重複步驟 1-3，直到達到終止狀態。
圖靈的可計算性
圖靈機定義了可計算性的概念。任何可以由圖靈機計算的函數都稱為可計算函數。圖靈證明瞭，存在不可計算的函數，也就是不能由圖靈機計算的函數。
圖靈機與現代電腦
雖然圖靈機是一個抽象模型，但它與現代電腦之間存在著密切的關係。馮紐曼架構，這是大多數現代電腦的基礎，就是以圖靈機為基礎的。
圖靈機的應用
圖靈機在運算理論和電腦科學中具有廣泛的應用，包括：
| 應用 | 描述 |
|---|---|
| 計算可計算性 | 用來確定函數是否可計算 |
| 設計編譯器 | 用於將程式碼轉換為機器碼 |
| 模擬其他運算模型 | 可以用來模擬其他運算模型，例如有限狀態自動機 |
| 研究運算複雜度 | 用於研究不同運算問題的難度 |
小結
圖靈機是運算理論中一個重要的概念，它定義了計算的極限，並為現代電腦的發展奠定了基礎。通過研究圖靈機，我們可以深入瞭解運算的本質及其在電腦科學中的應用。
延伸閲讀…
搞懂「通用圖靈機」的終站——它的誕生與意義│《電腦簡史》 …
從圖靈機到人工智慧，沒有「數學」怎能召喚電腦降世！