Remove ads
这是一个不可判定问题列表。
- 停机问题（决定图灵机是否停机）
- 决定图灵机是否Busy beaver（最长运行的图灵机有相用的停机问题）
- 死亡率问题（mortality problem）
- 莱斯定理指出所有partial方程的非凡属性，决定机器计算partial方程与其属性是否未决定。
- Word problem for groups
- 共轭问题
- 群同构问题（Group isomorphism problem）
- 对于某些类别的方程，问题决定；两个相用的方程，零的方程，是否不定积分的函数也包括在其中。例如，请参考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]
- 波斯特对应问题（Post correspondence problem）
- 某些形式语言的word problem
- 决定王氏砖块是否能铺满平面
- 判断标记系统是否停机
- 计算某个字符串的柯氏复杂性
- 希尔伯特第十问题：决定不定方程（又称为丢番图方程）的可解答性。
- 决定上下文有关语言会否生成对应字母表的所有字符串；或判断其是否有歧义。
- 两个上下文有关语言能否生成同样的字符串，或一个语言生成另一个语言生成的子集，或是否有某个字符串两个语言都生成。
- 给予一个为初始点的有理坐标是周期性，决定位于basin of attraction是否开集，或是否在平分线函数迭代为两个纲比或三个纲比。
- 决定Λ演算方程是否有正则形式。
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.
Remove ads