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

邏輯問題

抽象電腦(Abstract machine)問題

  • 停機問題(決定圖靈機是否停機)
  • 決定圖靈機是否Busy beaver(最長運行的圖靈機有相用的停機問題)
  • 死亡率問題(mortality problem)
  • 萊斯定理指出所有partial方程的非凡屬性,決定機器計算partial方程與其屬性是否未決定。

矩陣問題

  • 矩陣的致命問題:表達,一個有限集合的n × n矩陣的整數項,是否能有規律地倍增,重複出現,生成零矩陣。(已知一組15個或更多的3 × 3的矩陣及2組的45 × 45矩陣是未決定問題)
  • 決定一個有限集合的上三角形3 × 3矩陣與非負整數項能否組成一個自由半群
  • 決定兩個有限生成的Mn(Z)子半群是否有相同的元素。

組合群論(combinatorial group theory)問題

  • Word problem for groups
  • 共軛問題
  • 群同構問題(Group isomorphism problem)

拓撲學問題

  • 決定兩個有限單形(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]

其它問題

相關條目

參考

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.