可計算性理論
外觀
基礎知識
[編輯]計算機模型
[編輯]原始遞歸和遞歸函數
[編輯]可計算性
[編輯]程序的編碼
[編輯]元計算程序
[編輯]
存在元計算程序 使得對任何編號為 n 的程序 P, 與 計算的函數完全一致。 |
停機問題
[編輯]
定義函數 如下:
則 不是遞歸函數. |
證明. 設 h 為遞歸函數, 則存在程序 P 計算 h.
設計程序 Q(n) 如下. 運行程序 P(n, n), 若返回 0 則停機, 若返回 1 則進入無限循環.
令 m 為 Q 的編號. 假定 P(m, m) 返回 1, 說明 Q(m) 停機, 但是 Q(m) 停機當且僅當 P(m, m) 返回 0, 自相矛盾.
同理,假定 P(m, m) 返回 0, 說明 Q(m) 無限循環, 但是 Q(m) 無限循環當且僅當 P(m, m) 返回 1, 自相矛盾.
以此推定, h 不是遞歸函數. (證畢)
遞歸集合和遞歸可枚舉集合
[編輯]第一不完備性定理
[編輯]
設 T 為延伸 PA 的理論,若 T 相容且遞歸可枚舉,則 T 為不完備理論。 |
符號證明
[編輯]模型論證明
[編輯]Tennenbaum 定理
[編輯]
設模型 ,若 可數且不同構於 則:
|
第二不完備性定理
[編輯]
設 T 為延伸 PA 的遞歸可枚舉理論,若 則 T 為不相容理論。 |
算數階級
[編輯]不動點定理
[編輯]
設 為一遞歸函數,則存在 n 使對任意 x
且若兩者都停機,則 . |
萊斯定理
[編輯]
設 為自然數的一遞歸子集, 若對所有 滿足 均有 , 則 或 . |