不可判定问题是可计算性理论和计算复杂性理论中定义的一类决定性问题，此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表：对于停机问题，没有算法能够正确判定任意程序是否会终止运行。 决定性问题是一类根据从一个无限集合中选取的输入值，得出是或否的回答的问题...

這是一個不可判定问题列表。 大衛·希爾伯特的可判定性。 二階Λ演算的类型推论和型別檢查。 停机问题（決定圖靈機是否停機） 決定圖靈機是否Busy beaver（最長運行的圖靈機有相用的停机问题） 死亡率问题（mortality problem） 萊斯定理指出所有partial方程的非凡屬性，決定機...

在可計算性理論與計算複雜性理論中，決定性問題，亦稱判定問題，（英語：Decision problem）是一個在某些形式系統回答「是」或「否」的問題。 舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與 y...

则称为半可判定。 当语言 L {\displaystyle L} 不是图灵机可识别，则为不可判定语言。 当且仅当 L {\displaystyle L} 和 L ¯ {\displaystyle {\bar {L}}} 都是图灵机可识别的时候，L才能称为可判定语言。 指一个询问真 / 假的问题...

波斯特对应问题（英語：Post correspondence problem）是美国数学家埃米尔·波斯特（Emil Post）于1946年提出的一个不可判定问题。 已知字母表 A {\displaystyle A} 是包含至少两个字符的有限集合。 A {\displaystyle A} 上的一个字符串是指由...

艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个...

languages）。不在R中的问题都被称为不可判定问题。 P类问题，或称多项式时间问题，是指能被某一图灵机于多项式时间内解决的问题的集合。P是 Polynomial 的缩写。许多一般意义上的“简单”计算问题皆属于P。例如判断某数是否为另两个数的最大公因数、最大匹配（：最大匹配）问题等。2002年发现质数的判定问题也属于P...

在可计算性理论中，总是停机的机器也叫做判定器（Sipser，1996年）或全图灵机（Kozen，1997年）是对所有输入总是停机的图灵机。 因为它总是停机，这个机器有能力判定给定字符串是否是一个形式语言的成员。可由这种机器判定的语言类精确的是递归语言的集合。但是由于停机问题，判定任意图灵机是否在任意输入上停机的问题自身是不可判定的判定问题(參見哥德爾不完備定理)。...

不可判定问题是更加困难的，例如停机问题，而它们无法在任何给定时间内解决。 上面所有的讨论，假设了P表示“容易”而“不在P中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总是真的，原因包括如下几点： 它忽略了常数因子。一个需要101000n时间的问题...

Machine），又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为具備在一次运算之內解答特定问题的黑盒子（又稱為预言者）的图灵机；該问题可以是任何复杂度类，甚至可以是不可判定问题，像是停机问题。 一部預言機可以視為是與一個預言者（oracle）相連接的圖靈機。所謂預言者的概念，是一個可以回答特定問題...

就判定了语言 S。 Q.E.D. 根据上述定理直接可得下述引理： 定理： HALTING 的补语言是图灵不可识别的。 证明： 很显然 HALTING 是图灵可识别语言，若它的补语言也是图灵可识别的， 则根据上述定理知 HALTING 是图灵可判定的，这和停机问题中证明的结论矛盾。 图灵机 判定器 递归集合...