这是一个不可判定问题列表。
逻辑问题
抽象电脑(Abstract machine)问题
- 停机问题(决定图灵机是否停机)
- 决定图灵机是否Busy beaver(最长运行的图灵机有相用的停机问题)
- 死亡率问题(mortality problem)
- 莱斯定理指出所有partial方程的非凡属性,决定机器计算partial方程与其属性是否未决定。
矩阵问题
组合群论(combinatorial group theory)问题
- 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