弗里德堡–穆奇尼克定理

弗里德堡–穆奇尼克定理（英語：Friedberg–Muchnik Theorem）是可計算性理論中關於不可解度的定理。

基本介紹

• 中文名：弗里德堡–穆奇尼克定理
• 外文名：Friedberg–Muchnik Theorem
• 學科：可計算性理論
• 領域：可計算性理論
• 內容：不可解度的定理
• 相關術語：克萊尼–波斯特定理

簡介

弗里德堡–穆奇尼克定理（英語：Friedberg–Muchnik Theorem）是可計算性理論中關於不可解度的定理，聲稱存在一對互相不可計算的遞歸可枚舉不可解度。

內容

存在遞歸可枚舉不可解度A,B 互不可計算。

相關定理

• 克萊尼–波斯特定理是較弱的定理，可由弗里德堡–穆奇尼克作為推論得出。

克萊尼–波斯特定理

克萊尼–波斯特定理（英語：Kleene–Post Theorem）是可計算性理論中關於不可解度的定理，聲稱存在且可從停機問題計算出一對互相不可計算的不可解度。

存在不可解度A,B，使且 A,B 互不可計算。

弗里德堡–穆奇尼克定理是克萊尼–波斯特定理的強化形式。