跳转到内容

不可判定问题列表

维基百科,自由的百科全书

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

逻辑問題

抽象電腦(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.