不可判定問題列表

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

邏輯問題

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

抽象電腦（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,一個有效的decision procedure for the elementary integration of any function which belongs to a field of transcendental elementary functions。)
• “分解問題決定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是否開集,或是否在平分線函式疊代為兩個綱比或三個綱比。
• 決定Λ演算方程是否有正則形式。