不可判定问题列表

维基媒体列表条目

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

逻辑问题

抽象电脑(Abstract machine)问题

矩阵问题

  • 矩阵的致命问题:表达,一个有限集合的n × n矩阵的整数项,是否能有规律地倍增,重复出现,生成零矩阵。(已知一组15个或更多的3 × 3的矩阵及2组的45 × 45矩阵是未决定问题)
  • 决定一个有限集合的上三角形3 × 3矩阵与非负整数项能否组成一个自由半群
  • 决定两个有限生成的Mn(Z)子半群是否有相同的元素。

组合群论(combinatorial group theory)问题

拓扑学问题

  • 决定两个有限单形(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]

其它问题

相关条目

参考

  1. ^ Stallworth, Daniel T. and Fred W. RoushAn Undecidable Property of Definite Integrals页面存档备份,存于互联网档案馆Proceedings of the American Mathematical Society Volume 125, Number 7, July 1997, Pages 2147-2148
  2. ^ S&R

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.