不可判定问题列表

這是一個不可判定问题列表。

逻辑問題

• 大衛·希爾伯特的可判定性。
• 二階Λ演算的类型推论和型別檢查。

抽象電腦（Abstract machine）問題

• 停机问题（決定圖靈機是否停機）
• 決定圖靈機是否Busy beaver（最長運行的圖靈機有相用的停机问题）
• 死亡率问题（mortality problem）
• 萊斯定理指出所有partial方程的非凡屬性，決定機器計算partial方程與其屬性是否未決定。

矩陣問題

• 矩陣的致命問題：表達，一個有限集合的n × n矩陣的整數項，是否能有規律地倍增，重複出現，生成零矩陣。（已知一組15個或更多的3 × 3的矩陣及2組的45 × 45矩陣是未決定問題）
• 決定一個有限集合的上三角形3 × 3矩陣與非負整數項能否組成一個自由半群。
• 決定兩個有限生成的M_n(Z)子半群是否有相同的元素。

組合群論（combinatorial group theory）問題

• Word problem for groups
• 共軛問題
• 群同構問題（Group isomorphism problem）

拓扑学問題

• 決定兩個有限單形（simplicial complex）是否表現同胚空間。
• 決定兩個有限單形（simplicial complex）是否（同胚至）流形。
• 決定有限單的基本群是否密着。

可解答性問題

• 對於某些類別的方程，問題決定；兩個相用的方程，零的方程，是否不定積分的函數也包括在其中。例如，請參考Stallworth and Roush^[1]。(這些問題並非總是不可判定的。這取決於class。例如，Risch algorithm，一个对于属于超越初等函数一个领域，其任何函数的初等积分之有效决定步骤。)
• “分解問題決定the definite contour multiple integral of an elementary meromorphic function is zero over an everywhere real analytic manifold on which it is analytic。”這被希爾伯特第十問題判定為矛盾而解決。^[2]

其它問題

• 波斯特对应問題（Post correspondence problem）
• 某些形式語言的word problem
• 決定王氏砖块是否能铺满平面
• 判断標記系統是否停机
• 计算某个字符串的柯氏复杂性
• 希爾伯特第十問題：決定不定方程（又稱為丟番圖方程）的可解答性。
• 決定上下文有关语言会否生成对应字母表的所有字符串；或判断其是否有歧义。
• 兩個上下文有关语言能否生成同樣的字符串，或一個语言生成另一個语言生成的子集，或是否有某个字符串两个语言都生成。
• 給予一個為初始點的有理坐標是週期性，決定位於basin of attraction是否開集，或是否在平分線函數迭代為兩個綱比或三個綱比。
• 決定Λ演算方程是否有正則形式。

相關條目

• 黑盒
• 图灵机
• 图灵归约
• 交互式证明系统
• 隨機預言機