---
# System prepended metadata
title: 【數學理論】 11. 不完備、不一致、非保守、無法判定，數學信仰崩塌的盡頭 — 圖靈機停機問題（Turing Machine Halting Problem）
tags: [【數學理論】]
---
---
title: 【數學理論】 11. 不完備、不一致、非保守、無法判定，數學信仰崩塌的盡頭 — 圖靈機停機問題（Turing Machine Halting Problem）
tags:
- 【數學理論】
url: https://hackmd.io/Zu9VEt8ESZ2goTBTo4LWIg
lastSync: 2025-05-25T08:46:08.764Z
hackmd:
url: https://hackmd.io/Zu9VEt8ESZ2goTBTo4LWIg
title: 【數學理論】 11. 不完備、不一致、非保守、無法判定，數學信仰崩塌的盡頭 — 圖靈機停機問題（Turing Machine Halting Problem）
lastSync: 2025-05-25T08:52:38.292Z
---
不完備、不一致、非保守、無法判定，數學信仰崩塌的盡頭
===
圖靈機停機問題（Turing Machine Halting Problem）
---
在[**上一篇**](https://hackmd.io/@lewisjjj800/rkcL9IxMgx)我們介紹了**哥德爾不完備定理**，回顧一下：
>[!Important] **哥德爾第一不完備定理 (Gödel's First Incompleteness Theorems)**
>任何**一致**的形式系統，只要蘊涵**皮亞諾公理**，就可以在其中構造在系統中不能被證明的真命題，因此通過推理演繹不能得到所有真命題，即：一致的**該形式系統是不完備的**。
>[!Important] **哥德爾第二不完備定理 (Gödel's Second Incompleteness Theorems)**
>任何一致的形式系統，只要蘊涵皮亞諾公理，它就不能用於證明其本身的**一致性**。
這一篇我們就要來看看**希爾伯特綱領**中的**保守性**以及**可判定性**。
**保守性**比較簡單，我們先來看**保守性**的證明。
---
## 非保守性的證明
首先，我們先來回顧一下 **希爾伯特綱領**中的**保守性**概念是什麼。
>[!Note] **保守性 (Conservation)**
> 如果某個形式系統 $P'$ 是在 $P$ 上擴展出來的，而且 $P'$ 在某個語言中不會證出 $P$ 所無法證明的語句（例如對算術語句），那麼我們就說 $P'$ 對 $P$ 是**保守的**。
我們使用前一篇提到的 $T$ 以及 $\text{Con}(T)$：
- $T$ 是**蘊含皮亞諾公理的形式系統**
- $\text{Con}(T)$ 是「$T$ 是一致的」這件事的形式化語句
現在，我們來考慮一個**擴展系統**：
$$
T + \text{Con}(T)
$$
這代表：
- **原系統**：$T$
- **擴展系統**：$T$ 加上一條新公理：「$T$ 是一致的」（也就是 $\text{Con}(T)$）
看起來似乎沒什麼大不了，我們只是加了一句人類理性認為應該「是真的」話。
但，問題來了。
根據**哥德爾第二不完備定理**我們可以知道：
$$
T\space無法證明自身是一致的。
$$
此時，當我們在 $T$ 加上一條新公理：「$T$ 是一致的」
就代表我們現在確定在 **擴展系統** $(T + \text{Con}(T))$ 中 $T$ 就是一致的。也就是：
$$
T + \text{Con}(T) \vdash \text{Con}(T)
$$
但是**哥德爾第二不完備定理**說：我們無法從 $T$ 證明 「$T$ 必是一致的」。也就是：
$$
T \not\vdash \text{Con}(T)
$$
所以**擴展系統**推導出了**原系統**無法證明的語句。
因此對於**蘊含皮亞諾公理的形式系統** $T$ ，若該形式系統通過加入公理（如 $\text{Con}(T)$）來證明 $T$ 的一致性，則該系統通常不是 $T$ 的保守擴展，因為它能證明 $T$ 無法證明的陳述（如 $\text{Con}(T)$）。
因此，**蘊含皮亞諾公理的形式系統**存在某些擴展是非保守的，如剛剛舉例的：「**擴展系統**推導出了**原系統**無法證明的語句」。
---
真是完大蛋了，目前希爾伯特綱領中的四條性質中的三個已經被我們證實了：**不完備、不一致、非保守**，那最後一個**可判定性**呢？
**可判定性**就要利用 **圖靈機（Turing Machine）** 了。
---
## **圖靈機（Turing Machine）**
要介紹一下什麼是**圖靈機（Turing Machine）**，就要先介紹**圖靈（Turing）**。
> photo credit by: https://images.app.goo.gl/piHGsU3Mgk6bXe7v5
放錯了，不是這個圖靈，下面這個才是。
> photo credit by: https://www.computerhistory.org/timeline/1949/
艾倫·圖靈（Alan Turing）是英國電腦科學家、數學家、邏輯學家、密碼分析學家和理論生物學家，被譽為電腦科學與人工智慧之父。
他於1936年提出一種將人的計算行為抽象化的數理邏輯機，也就是**圖靈機（Turing Machine）**。
>[!Note] **圖靈機（Turing Machine）**
>
>圖靈機是一個理論上的「最簡形式電腦模型」，它由以下幾個部分組成：
>
>| 組件 | 功能 |
>|------------|--------------------------------------|
>| 無限長的紙帶（Tape） | 儲存資料與結果（類似記憶體） |
>| 讀寫頭（Head） | 可以讀取與寫入 tape 上的符號，並左右移動 |
>| 狀態機（State Register） | 記錄目前的內部狀態 |
>| 遷移函數（Transition Function） | 根據當前狀態與符號，決定接下來的行為（寫入、移動、改變狀態） |
而圖靈證明了：**任何可被電腦執行的演算法，圖靈機都能模擬。這就稱為「圖靈完備（Turing Completeness）」**。
>[!Note] **圖靈完備（Turing Completeness）**
>如果一個計算系統被稱為圖靈完備（Turing Completeness），代表它能夠模擬通用圖靈機（Universal Turing Machine）的行為，從而計算任何可計算的函數（在給定無限記憶體和無限時間的情況下）。換句話說，圖靈完備的系統可以解決所有「可計算問題」（computable problems），只要這些問題在理論上能夠被圖靈機解決。
>
>而如果一個計算系統(例如程式)要成為圖靈完備，通常需要具備以下能力：
>
>- 條件分支：能夠根據條件執行不同的操作（例如 `if-else` 語句）。
>- 重複或循環：能夠執行無限次的重複操作（例如 `while` 迴圈或遞迴）。
>- 記憶體操作：能夠讀取和寫入任意數量的資料（理論上需要無限記憶體，實際中受硬體限制）。
>- 狀態轉換：能夠在不同的狀態之間切換，模擬圖靈機的有限狀態控制器。
這些能力確保系統可以模擬圖靈機的紙帶、讀寫頭和狀態轉換規則。
而大多數現代程式語言（如 Python、C、Java、JavaScript）都是圖靈完備的，因為它們支援條件分支、迴圈和記憶體操作。此外，Minecraft的紅石電路同樣也是圖靈完備的，因為我們可以利用紅石電路達到邏輯閘、遞歸等效果。
下面就是我畫的一個**圖靈機**展示圖：
可以看到有一個**無限長的紙帶**。
還有一個**讀寫頭**，**讀寫頭可以在表帶上左右移動**，並且可以**讀取當前格子上的數字以及寫入一個數字**。
右上角是**狀態機**，代表**這台圖靈機所有可能的狀態**。
左上角則是**遷移函數**，他會**根據讀寫頭上的字母以及讀寫頭讀取到的數字來改變**。
舉個例子：
上圖我們可以看到，當前的狀態是 **「D,0」**。
那麼根據狀態 **「D,0」**，左上角的遷移函數會決定 **狀態是「D,0」** 時的下一步要怎麼走。如下圖：
根據**遷移函數**我們知道當 **狀態是「D,0」** 時，讀寫頭要變成 **「A」**，並且寫下一個 **「1」**。如下圖：
並且**讀寫頭**要往**右邊**移動一格。如下圖：
>這邊我讓**紙帶往左**代表**讀寫頭向右**，為得就是 **讀寫頭** 保持不動。
那這樣我們可以看到，現在有一個新的狀態是 **「A,1」**，如下圖。
就這樣，圖靈機可以持續根據**狀態**以及**讀寫頭**來繼續跑下去。
下面稍微展示一下：
你可能發現了上圖最後出現了 **停機** ，而我們根據右上角的狀態機可以看到，這八個格子裡的左上角對應了狀態機上的字母 **A、B、C、D**，唯獨有一個獨立出來的符號 **H** 。
而這個 **H** 代表的是 **停機 (Halt)** ，也就是讓這台圖靈機停下來的意思。
那除了 **停機** 這個特別的情況以外，還會有一個情況叫作 **死循環**。
上圖可以看到，這台圖靈機只會在 **「D,0」** 以及 **「A,0」** 兩個狀態之間循環，好像進入死胡同一樣，這種情況就被稱作 **死循環 (Loop)**。
那問題來了：我們有辦法光看**一個圖靈機的所有狀態**，就能判斷這台圖靈機最後是否會**停機**或是進入**死循環**嗎？
這個問題看起來好像不難對不對？接下來我們來考慮一個例子。
---
## 蘭頓的螞蟻
**蘭頓的螞蟻（Langton's ant）** 由克里斯托夫·蘭頓 (Christopher Langton) 在1986年提出，它由全白的方格畫布和一隻「螞蟻」構成，是一個二維圖靈機。
>[!Note] **蘭頓的螞蟻（Langton's ant）**
>有一個全白的方格畫布，在其中一格正方形有一隻「螞蟻」。它的頭部朝向上下左右其中一個方向，螞蟻可以在畫布上的方格中填上黑色或白色。而這隻螞蟻只有兩個狀態：
>- 若螞蟻在**白格**，右轉90度，將該格填上**黑色**，變成**黑格**，**向前移一步**。
>- 若螞蟻在**黑格**，左轉90度，將該格填上**白色**，變成**白格**，**向前移一步**。
很簡單對吧？現在假如畫布只有 $100 \times 100$ 的大小，而只要螞蟻最後觸碰到邊界，那螞蟻就**暫停**。那請你猜猜看，這個只有兩個狀態的螞蟻，最後會：
- 碰到邊界？(**停機**)
- 按照一條封閉的路徑循環？(**死循環**)
>有興趣的可以暫停一下猜猜看。
我們可以利用 `python` 來撰寫這個程式，然後可視化，程式如下：
:::spoiler 點擊以查看程式碼
```python=
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
# Langton's Ant parameters
grid_size = 100
steps = 12000
dirs = [(0, -1), (1, 0), (0, 1), (-1, 0)]
direction_symbols = ['↑', '→', '↓', '←']
# 初始化格子與螞蟻位置
grid = np.zeros((grid_size, grid_size), dtype=int)
x, y = grid_size // 2, grid_size // 2
d = 0
frames = []
positions = []
# 顏色對應：白、黑
color_map = {
0: [1.0, 1.0, 1.0],
1: [0, 0, 0],
}
# 模擬 Langton's Ant 移動
for step in range(steps):
# 若螞蟻走到邊界，停止模擬
if x == 0 or x == grid_size - 1 or y == 0 or y == grid_size - 1:
print(f"這隻螞蟻在走到第 {step} 步時停了下來, 停在 ({x}, {y}) 這個位置上")
break
rgb_grid = np.zeros((grid_size, grid_size, 3))
for val in [0, 1]:
mask = grid == val
rgb_grid[mask] = color_map[val]
frames.append(rgb_grid.copy())
positions.append((x, y, d, step))
if grid[y, x] == 0:
d = (d + 1) % 4
grid[y, x] = 1
else:
d = (d - 1) % 4
grid[y, x] = 0
dx, dy = dirs[d]
x += dx
y += dy
# 設定動畫圖形
fig, ax = plt.subplots()
im = ax.imshow(frames[0], interpolation='none')
ant_marker, = ax.plot([], [], 'ro')
direction_text = ax.text(0, 0, '', color='black', fontsize=12, ha='center', va='center')
step_text = ax.text(0.98, 0.02, '', color='blue', fontsize=10, ha='right', va='bottom', transform=ax.transAxes)
# 關閉坐標軸數字
ax.set_xticks([])
ax.set_yticks([])
def update(i):
grid_frame = frames[i]
x, y, d, step = positions[i]
im.set_array(grid_frame)
ant_marker.set_data([x], [y])
direction_text.set_position((x, y))
direction_text.set_text(direction_symbols[d])
step_text.set_text(f"Step: {step}")
return [im, ant_marker, direction_text, step_text]
ani = animation.FuncAnimation(fig, update, frames=len(frames), interval=30, blit=True)
# 儲存成 GIF 與 MP4
ani.save("langtons_ant.gif", writer='pillow')
ani.save("langtons_ant.mp4", writer='ffmpeg')
```
:::
接下來我們來看看透過程式，將**蘭頓的螞蟻**可視化後的結果：
執行完程式後，會輸出以下字串：
```
這隻螞蟻在走到第 11655 步時停了下來, 停在 (0, 73) 這個位置上
```
你猜到了嗎？這個只有兩個狀態的螞蟻，會在畫布上畫出一個極其複雜的圖案，然後需要花大約 **11000步** 才會以**104步為周期**，進入一條無限重複的「**高速公路**」，朝一個固定的方向移動，最後一共走了 **11655步** 碰到邊界才停了下來。
---
## 停機問題（Halting Problem）
藉由剛剛的例子，我們發現，就算只有兩個很簡單的**狀態**，也很難光看**狀態**來判斷一個具有規則作動的圖靈機，最後會不會**停機**，還是進入**死循環**。
但是，**是否有一個程式或是演算法，可以判定這台圖靈機能否會停機？**
這，就是圖靈機的**停機問題（Halting Problem）**
>[!Note] **停機問題（Halting Problem）**
> **給定一台圖靈機 `M` 和輸入 `x`，是否存在一個演算法 `H(M, x)` 可以告訴我們：`M` 在輸入 `x` 時是否會最終停機？**
你可能會想：**判斷停不停機可以幹嘛？**
那如果我說：**判斷一台圖靈機是否會停機的這個演算法，可以解決這個世界上許多數學難題呢？**
舉個例子，我們考慮**哥德巴赫猜想（Goldbach's conjecture）**
>[!Note] **哥德巴赫猜想（Goldbach's conjecture）**
>**哥德巴赫猜想**是數論中存在最久的未解問題之一。這個猜想最早出現在1742年普魯士數學家克里斯蒂安·哥德巴赫與瑞士數學家萊昂哈德·歐拉的通信中。用現代的數學語言，哥德巴赫猜想可以陳述為：
>- **任一大於2的偶數，是否都可表示成兩個質數之和？**
假如我們用程式來模擬 **哥德巴赫猜想** ：
>[!Tip] **我們設計一個程式：`G_C`**
>讓這個程式 **`G_C`** 從 $n = 4$ 開始，檢查**每個偶數是否能表示為兩個質數的和**。若找到**某個偶數無法表示為兩個質數的和（反例），則「停機」**。
> 前面有說**程式語言**是**圖靈完備**的，代表程式語言可以模擬圖靈機，所以這邊用**程式來模擬**等於**用圖靈機來模擬**。
那假如我們可以找到**一套演算法**來判斷 「**程式`M`** 以及給定的輸入 $n = 4$」是否會**停機**。
那就代表我們可以解決**哥德巴赫猜想**。
當然還有，**黎曼猜想（Riemann Hypothesis）**。
>[!Note] **黎曼猜想（Riemann Hypothesis）**
> 黎曼 $\zeta$ 函數：$\zeta(s)$ 的所有非平凡零點（複數零點）是否都具有實部 $Re(s)=\frac{1}{2}$？
那我們設計一個程式：**`R_H`** 來模擬 **黎曼猜想** ：
>[!Tip] **我們設計一個程式：`R_H`**
>讓這個程式 **`R_H`** 檢驗 $\zeta(s)$ 的零點，檢查是否存在非平凡零點的實部 $Re(s)=\frac{1}{2}$。遍歷可能的複數 $s$ 若找到反例則 **「停機」**。
當然還有很多難題，例如：**質數間隙問題（Twin Prime Conjecture）、$P = NP$ 問題、柯拉茲猜想（Collatz Conjecture）**，這些難題具有以下特點：
- **可計算性**：這些難題的驗證過程（檢查解或反例）是可計算的，可以用圖靈機或程式模擬。
- **停機條件**：程式設計為在找到解（例如反例或證明）時停機，表示問題解決。
- **不確定性**：若猜想為真，程式可能永不停止，類似於停機問題中的不可預測性。
因此，假如你真的找到一套演算法可以判斷一台圖靈機是否可**停機**，代表你**有辦法解決大部分數學界的難題**，如果你真的有辦法，那我想號稱 **數學界的諾貝爾獎的菲爾茲獎（Fields Medal）** 絕對非你莫屬，甚至**菲爾茲**本人都要**親自從棺材裡爬起來替你頒獎**。
但是，真的有這麼簡單嗎？
---
## 不可判定性的證明
現在，我們**假設存在一個停機判定器 `H(M, x)`**：
- `H(M, x)` 是一個函數，`H(M, x)` 輸入為程式 `M` ，而 `M` 的輸入為 `x`。也就是 `H(M(x))`
- `H(M, x)` 會根據以下結果回傳 `True` 或是 `False`：
- 如果 `M(x)` 最終會**停機**，回傳 `True`
- 如果 `M(x)` 永遠不會停(**死循環**)，回傳 `False`
接下來，我們定義一個反常行為的程式 `D`，它接受一個程式 `M` 為輸入，且判斷 `H(M, M)` 回傳的結果，並執行行為如下：
```python
def D(M):
if H(M, M) == True:
while True:
pass # 進入"死循環"
else:
return "停機"
```
用中文說就是：
讓 `M` 輸入自己，也就是 `M(M)`，那如果：
- 如果 `H(M, M)` 判斷 `M(M)` 會**停機**，那 `D(M)` 就進入**死循環**。
- 如果 `H(M, M)` 判斷 `M(M)` 會進入**死循環**，那 `D(M)` 就馬上**停機**。
你可能會想說：**哪有程式可以輸入自己的？**
事實上可以哦！以下舉個例子：
```python=
def process_self(code):
"""處理程式自身的原始碼，例如計算長度或檢查內容"""
print(f"程式原始碼長度：{len(code)} 字元")
# 模擬簡單分析，例如檢查是否有特定關鍵字
if "process_self" in code:
print("找到函數 'process_self'，模擬處理自身")
else:
print("未找到預期內容")
# 模擬停機：完成處理後停止
return True
def main():
"""主程式：讀取自身原始碼並作為輸入"""
try:
# 讀取當前程式的原始碼
with open(__file__, 'r', encoding='utf-8') as file:
code = file.read()
print("程式正在輸入自己（讀取原始碼）...")
# 將原始碼作為輸入傳給 process_self
result = process_self(code)
if result:
print("程式成功處理自身並停機")
except Exception as e:
print(f"錯誤：{e}")
if __name__ == "__main__":
main()
```
上面這個程式的處理邏輯是這樣：
1. 程式讀取自身檔案。
2. 將原始碼作為輸入，傳遞給內部函數處理。
3. 輸出處理結果並停止。
我們把程式儲存為 `self_input.py`，運行後就會輸出：
```python
程式正在輸入自己（讀取原始碼）...
程式原始碼長度：674 字元
找到函數 'process_self'，模擬處理自身
程式成功處理自身並停機
```
所以輸入自己是可以的。
接下來，問個問題：`D(D)` **會停機嗎？**
>[!Caution] `D(D)` **會停機嗎？**
>如果 `H(D, D) == True`：
>- 代表 `D(D)` 會**停機** → 根據定義，`D(D)` 應該進入**死循環**，**矛盾**！
>
>如果 `H(D, D) == False`：
>- 代表 `D(D)` 進入**死循環** → 根據定義，`D(D)` 應該**停機**，**矛盾**！
因為上面兩種情況都會導致邏輯崩潰，所以 **停機判定器 `H(M, x)`** 根本不可能存在。
也就是說，**不存在任何一種演算法可以判定一台圖靈機是否可以停機！**
因此，**可判定性不成立**。
---
## 自我指涉 (Self-reference)
聰明的你可能發現了，無論是 **哥德爾不完備定理** 還是本篇介紹到的 **圖靈機停機問題**，都有一個共通點，就是我們都可以找到一個方法讓**他們都讓自己引用自己，引發矛盾**。
這種**自己引用自己**的情況就叫：**自我指涉 (Self-reference)**
例如我們在[**這一篇**](https://hackmd.io/@lewisjjj800/rkXv5Ixzel#%E7%BE%85%E7%B4%A0%E6%82%96%E8%AB%96%EF%BC%88Russell%E2%80%99s-Paradox%EF%BC%89)提到的**理髮師悖論（Barber Paradox）**：
>[!Important]**理髮師悖論（Barber Paradox）**
> 在某個村莊裡，有一位理髮師，他為**所有不自己刮鬍子的人刮鬍子。那這位理髮師該不該幫自己刮鬍子？**
> - 如果他幫自己刮鬍子，那**他就不屬於「不自己刮鬍子」的人，他就不該幫自己刮鬍子。**
>- 如果他不幫自己刮鬍子，那**他就符合「不自己刮鬍子」的條件，他應該幫自己刮鬍子。**
>
>理髮師幫自己刮鬍子也對，不刮也對，這就導致了矛盾。
還有**說謊者悖論（Liar paradox）**：
>[!Important]**說謊者悖論（Liar paradox）**
>有一個人說：「**我正在說謊。**」
> - 如果實際上他**真的在說謊**，那麼他所說的就是**真的**，但如果他所說的就是**真的**，那麼**他就是在說謊**。
> - 如果實際上他**沒有在說謊**，那麼他所說的就是**假的**，但如果他所說的就是**假的**，那麼**他沒有在說謊**。
這些悖論之所以是悖論，因為他們都涉及了**自我指涉**，他們都**直接或是間接來引用自己**，從而引發**矛盾**。
而日常生活中充滿了**自我指涉**，例如下面這句話：
>「我是不是太常懷疑我是不是太常懷疑自己了？」
你在懷疑自己是不是很常懷疑自己時，那你就已經開始懷疑自己了。
還有著名的**德羅斯特效應（Droste effect）**，我們看下面這張圖：
> photo credit by: 由 Designer: Jan MissetUploader: Alf van Beem - 自己的作品, 公有領域, https://commons.wikimedia.org/w/index.php?curid=30739029
上面這張圖是荷蘭著名廠牌德羅斯特（Droste）可可粉的包裝盒，包裝盒上的圖案是一位護士拿著一個放著杯子及紙盒的托盤，而托盤上的紙盒就是**德羅斯特可可粉的包裝盒**。這是一種**自我遞歸**的表現。
或者是假如你是一台機器人，然後你內部有一串代碼：
```python=
if self.cleaning_state == "confused":
self.debug(self.status)
```
也就是：**當我不知道自己在幹嘛的時候，我就會開始檢查我自己在幹嘛。**
---
## 結論
我們會發現，生活周遭中有很多**自我指涉**的例子，有時候甚至會變成一個**笑點**來娛樂我們。
然而，數學發展了幾千年的歷史，好不容易有人想要將數學來**公理化**，希望：
1. 數學的真命題都可以被證明。
2. 數學是沒有矛盾的。
3. 衍生出的新理論證明，也可以從舊理論證明出來。
4. 數學問題是可以被判定真偽的。
但卻因為一個**笑點**毀了。這就好像是上帝給我們開了一個玩笑。
但是，縱使如此，熱愛數學的我們依舊熱愛數學。
因為朋友跟戀人會背叛你，但是數學不會。因為數學不會就是不會。
---
## 後記
過去的日子裡我撰寫了許多談論**數學理論**的專欄，大多都是從我的經驗出發，接著開始講述一個個我熱愛的**數學理論**。
而**哥德爾不完備定理**正是我想要開始撰寫這個專欄的契機，因為**哥德爾不完備定理**真的是我見過最有趣又富含哲理的數學了。因此在最一開始要撰寫這個專欄時，我就在想這個以**數學理論**為名的系列，最後要以**哥德爾不完備定理**做為結尾。
現在，寫完了長達三篇的**哥德爾不完備定理**介紹，很難想像我真的一步步寫到這裡。
當然未來我還是會繼續寫下去，會開啟其他系列，繼續富足我的研究之路。
那就請看到這邊的你，繼續期待下一篇吧！
我是Lewis，我們[**下一篇**](https://hackmd.io/@lewisjjj800/rky7sneLex)專欄見！