不可判定问题列表

这是一个不可判定问题列表。

逻辑问题

• 大卫·希尔伯特的可判定性。
• 二阶Λ演算的类型推论和型别检查。

抽象电脑（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.