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

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

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

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

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

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

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

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

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

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

本質上是量子的演算法，或者使用量子計算的某些特性，例如量子疊加、或量子糾纏等。 使用經典計算機對於不可判定問題仍然無法使用量子計算機判定。量子演算法的有趣之處在於它們可能比經典演算法更快地解決一些問題，因為量子演算法利用的量子疊加及量子糾纏可能無法解決在經典計算機上進行有效的模擬（參閱量子計算優越性）。...

在计算机科学和数理逻辑中，自然数集合的图灵度或者不可解度是对此集合的算法不可解性的度量。图灵度在可计算理论中是根本性的概念，在可计算理论里，自然数集合通常被看作一个判定问题，而图灵度则给出了解决与此集合相连的判定问题的困难程度。 如果两集合 A , B {\displaystyle A,B} 有同一不可解度（也即两者互相图灵可计算），则称两集合为图灵等价，记作...

古格里·錢頓（Gregory Chaitin）在算法信息论中构造了一个不确定命题，即「Chaitin随机数Ω的第n个字节是否为0」这样的命题在ZFC内是不可判定的。 计算逻辑中的停机问题不可解，亦是哥德尔不完备定理的一种表现形式。 以下列出的误解都是针对第一条定理而产生的。 该定理并不意味着任何公理系统都是不完备的。例...

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

问题已经被证实是不可判定的。Novikov和Boone在1950年代证实，给出在一个有限出现群中的一个字，没有有效的过程来判定这个字所表示的元素是否是这个群的单位元素。这个结果被用来证实很多其他问题是不可判定的，比如两个有限单形（simplicial complex）是否表现同胚空间的问题...

问题原则涉及到法院系统是否是裁判问题的适当场合（appropriate forum）。法院系统仅有权审理和决定可诉的法律问题，而无权决定不可诉的政治问题。 对于涉及政治性较强的问题，法院有时会将其认定为政治问题，从而导致其无法在法庭通过诉讼解决，既不可诉。在因政治原则而认定为不可...

不可计算函数（uncomputable function） 不可计算问题（uncomputable problem） 不可决策语言（undecidable language） 不可判定问题（undecidable problem） 无向图（undirected graph） 均一环路复杂度（uniform circuit complexity）...

问题。时间将可能重新从1970年1月1日开始计算，这将可能引起世界范围的计算机故障。这被称为2038年问题。 此外，是否存在10000年问题。还是一个遥不可及的问题。 有觀點認爲過了公元2000年之後，「千年蟲」的問題就會自動消失。然而，若然沒有對編程方式作合適的修訂，問題...

co-RE則是所有RE語言其補集（complement）的總集合。某種意義上我們可以說，co-RE包含的語言，其裡面的問題要證明為錯誤，只要有限的時間；但是可能要無限的時間，才能證明這問題正確。 RE裡面的每個成員都屬於遞歸可枚舉集合，因此同時也是丟番圖集。 不可判定問題列表 Complexity Zoo: Class RE...

\mathrm {DTIME} (2^{2^{2^{n}}})\cup \cdots \end{matrix}}} 這名稱最早是為了探討可計算函數和不可判定問題，由László Kalmár所提出；most problems in it are far from elementary。Some natural...

{\displaystyle \Omega } 的前 n {\displaystyle n} 个位数，解决图灵的停机问题对於长度不超過 n {\displaystyle n} 的程式。由于停机问题是不可判定问題， Ω {\displaystyle \Omega } 沒有办法被计算出來。 算法进行如下。 给出 Ω...

就是，计算机程序。他明確地給出一個例子，宇宙的表現能被在有限時間中輸出會收斂的不停機程式描述，縱使時間本身的收斂性是不能被停機程式預測（停机问题中的不可判定问题）。 泰格馬克回覆說所有宇宙中的物理自由度、物理常數和定理等自由變量的變化的数学构成主义形式測量在弦論地景尚未被建構，因此這個不該被視為反駁的理由。...

停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止。 波斯特对应问题（Post's correspondence problem）。 不可解度的概念定义了不可解的集合之间的相对计算难度。例如，不可解的停机问题...

有，任給一個自然數，也存在著一個方法，在有限步驟內，可以判定這個數是不是質數。 雖然人們很早就有了演算法的樸素概念，但對於到底什麼是可行的計算，仍沒有精確的概念。一個問題的可解與不可解究竟是什麼含意，當時的人們還不得而知。然而為了研究第十問題，必須給予演算法精確化的觀念。這點還有賴於數理邏輯學對可計算性理論的發展，才得以實現。...

各函式之間的關係。但會遺漏這次沒有執行到的程式碼。靜態函式呼叫圖則是設法表示所有可能執行情形下，所有函式之間的關係。準確的靜態函式呼叫圖是不可判定问题，因此靜態函式呼叫圖是多半只是近似情形。函式呼叫圖上有所有函式之間的呼叫關係，但有可能其中有一些呼叫是永遠不會執行到的。...

有數學方法可以得到一程式是否會有執行期間的錯誤的結果。上述的結論是由庫爾特·哥德爾、阿隆佐·邱奇及阿蘭·圖靈在1930年代研究停機問題所得的結果。不過如同許多不可判定问题一様，在實務仍會設法找到有用的近似解。 以下是一些形式化靜態分析的實現方式： 模型檢查（英语：Model...

依赖类型增加了类型系统的复杂度。由于确定两个依赖于值的类型的等价性需要涉及具体的计算，若允许在依赖类型中使用任意值的话，其类型检查将会成为不可判定问题；换言之，无法确保程序的类型检查一定会停机。 由于Curry-Howard同构揭示了程序语言的类型论与证明论的直觉逻辑之间的紧密关联性，以依赖类...

其解法如下：可以将任何图灵机转变成一组密铺整个平面的王氏平铺，当且仅当此图灵机永不停止。而停机问题（测试图灵机是否最终停止的问题）的不可判断性导致了王氏平铺问题的不可判定性。 结合王浩的观察以及伯杰的不可判断性结果，可以推测存在一组有限多個的王氏砖，可以密铺整个二维平面，但只能非周期性密铺。此密铺类似彭罗斯平铺（英语：Penrose...

certificate）。 大部份的驗證工作都是不可判定問題，因此沒有辦法找出通用的驗證演算法。不過，這些工具會在指標性問題上展現其分析能力。這些可以驗證所有強健案例的混合系統驗證法帶來一個可能的理論性結論：混合系統中的許多問題雖然是不可判定的，但至少是準可判定的。...

下例利用從停機問題至某個語言的轉換，以證明該語言是不可決定的。設H(M,w)是問題：「判定給定的圖靈機M會否在輸入字串w後停機（接受或拒絕此字串）」。此語言已知是不可決定的。又設E(M)是問題：「給定圖靈機M，判定它所接受的語言是否空（意即M是否接受任何字串）」。我們可以藉由從H歸約成E以顯示E也是不可決定的。...

在可计算性理论中，可以说明，判定型问题和搜索型问题在可计算性的意义下是等价的。而在计算复杂性中，Khuller和Vazirani在1990年代证明了在P≠NP的假设下，平面图4-着色问题的判定型问题是在P中的，而寻找其字典序第一的着色是NP难的。 所以在可计算性理论中，只关注判定型问题...