弗里德堡–穆奇尼克定理(英語:Friedberg–Muchnik Theorem)是可計算性理論中關於不可解度的定理。 基本介紹 中文名:弗里德堡–穆奇尼克定理外文名:Friedberg–Muchnik Theorem學科:可計算性理論領域:可計算性理論內容:不可解度的定理相關術語:克萊尼–波斯特定理 簡介,內容,相關定理,克萊尼–波斯特定理, 簡介弗里德堡–穆奇尼克定理(英語:Friedberg–Muchnik Theorem)是可計算性理論中關於不可解度的定理,聲稱存在一對互相不可計算的遞歸可枚舉不可解度。內容存在遞歸可枚舉不可解度A,B 互不可計算。相關定理克萊尼–波斯特定理是較弱的定理,可由弗里德堡–穆奇尼克作為推論得出。克萊尼–波斯特定理克萊尼–波斯特定理(英語:Kleene–Post Theorem)是可計算性理論中關於不可解度的定理,聲稱存在且可從停機問題計算出一對互相不可計算的不可解度。存在不可解度A,B,使且 A,B 互不可計算。弗里德堡–穆奇尼克定理是克萊尼–波斯特定理的強化形式。