跳至內容

可計算性理論

維基教科書,自由的教學讀本

基礎知識

[編輯]

計算機模型

[編輯]

原始遞歸和遞歸函數

[編輯]

可計算性

[編輯]

程序的編碼

[編輯]

元計算程序

[編輯]

存在元計算程序 使得對任何編號為 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 定理

[編輯]

設模型 ,若 可數且不同構於 則:

  1. 為非遞歸模型;
  2. 為非遞歸函數。

第二不完備性定理

[編輯]

設 T 為延伸 PA 的遞歸可枚舉理論,若 則 T 為不相容理論。

算數階級

[編輯]

不動點定理

[編輯]

為一遞歸函數,則存在 n 使對任意 x

且若兩者都停機,則

.

萊斯定理

[編輯]

為自然數的一遞歸子集, 若對所有 滿足 均有 , 則 .