不可判定問題列表

這是一個不可判定問題列表。

邏輯問題

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

抽象電腦（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。(這些問題並非總是不可判定的。這取決於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。」這被希爾伯特第十問題判定為矛盾而解決。

其它問題

• 波斯特對應問題（Post correspondence problem）
• 某些形式語言的word problem
• 決定王氏磚塊是否能鋪滿平面
• 判斷標記系統是否停機
• 計算某個字符串的柯氏複雜性
• 希爾伯特第十問題：決定不定方程（又稱為丟番圖方程）的可解答性。
• 決定上下文有關語言會否生成對應字母表的所有字符串；或判斷其是否有歧義。
• 兩個上下文有關語言能否生成同樣的字符串，或一個語言生成另一個語言生成的子集，或是否有某個字符串兩個語言都生成。
• 給予一個為初始點的有理坐標是週期性，決定位於basin of attraction是否開集，或是否在平分線函數迭代為兩個綱比或三個綱比。
• 決定Λ演算方程是否有正則形式。

相關條目

• 黑盒
• 圖靈機
• 圖靈歸約
• 交互式證明系統
• 隨機預言機

參考

Brookshear, J. Glenn. Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. 1989.  Appendix C includes impossibility of algorithms deciding if a grammar contains ambiguities, and impossibility of verifying program correctness by an algorithm as example of Halting Problem.

Halava, Vesa. Decidable and undecidable problems in matrix theory. TUCS technical report 127. Turku Centre for Computer Science. 1997.  [1] （頁面存檔備份，存於網際網路檔案館）

B. M. E. Moret, H. D. Shapiro. Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. 1991.  Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."

Weinberger, Shmuel. Computers, rigidity, and moduli. Princeton, NJ: Princeton University Press. 2005.  Discusses undecidability of the word problem for groups, and of various problems in topology.