可計算性理論

基礎知識

編輯

計算機模型

編輯

原始遞歸和遞歸函數

編輯

可計算性

編輯

程序的編碼

編輯

元計算程序

編輯
 

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

 

且若兩者都停機,則

  .

萊斯定理

編輯
 

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