第八章：無限集合
無限是一個充滿悖論與驚奇的概念。在本章中，我們將探討不同「大小」的無限，以及這些概念在計算機科學中的終極應用——停機問題。
8.1 無限基數
集合 A 和集合 B 具有相同的基數，記作 |A| = |B|，若且唯若存在一個從 A 到 B 的雙射。
對於有限集合，這意味著它們的元素數量相同。對於無限集合，這會產生反直覺的結果。
可數無限
如果一個集合與自然數集 N 存在雙射，則稱其為可數無限，基數記為 $\aleph_0$ (阿列夫零)。
- 偶數集合 {0, 2, 4, ...} 雖然是 N 的一部分，但其基數與 N 相同。
- 甚至整數集 Z 和有理數集 Q 也是可數的。
🧪 希爾伯特大旅館模擬器
想像一家有無限多個房間（房間號 1, 2, 3...）的旅館，而且所有房間都住滿了客人。這是一個「可數無限」的直觀模型。
💡 提示：點擊「新客人到達」，觀察旅館如何在不趕走舊客人的情況下容納新客人。
8.2 停機問題與不可數性
並非所有無限集合都是可數的。實數集 R 就是不可數的。這可以透過康托爾對角化法 證明。
康托爾對角化法示意
假設我們列出了所有無限長的 0/1 序列（類似於實數的二進位表示）。我們總是可以構造一個不在列表中的新序列：
新序列在第 n 個位置上與第 n 個序列不同（紅色格子）。這意味著我們永遠無法列出所有實數。
停機問題
圖靈利用類似的邏輯證明了停機問題是不可判定的：不存在一個程式能判斷所有程式是否會停止。
證明概要：
假設存在一個函數 `halts(f)` 能判斷程式 f 是否會停止。
定義一個程式 `Turing(f)`：
`if halts(f): loop_forever`
`else: stop`
現在運行 `Turing(Turing)`：
若它停止，則進入無窮迴圈。若它不停止，則停止。矛盾！
因此，`halts` 函數不可能存在。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)