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

這是一個不可判定问题列表。 大衛·希爾伯特的可判定性。 二階Λ演算的类型推论和型別檢查。 停机问题（決定圖靈機是否停機） 決定圖靈機是否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 是图灵可判定的，这和停机问题中证明的结论矛盾。 图灵机 判定器 递归集合...

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

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

\sigma } ，有時會說 σ {\displaystyle \sigma } 在 T {\displaystyle T} 中是不可判定的，而這裡的「不可判定」跟決定性問題中的「不可判定」是不同的。 若理論 T {\displaystyle T} 中的每項公設都不能由 T {\displaystyle T}...

问题。时间将可能重新从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...

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

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

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

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

權宜問題（raise a question of privilege）是一項議事程序，旨在保障與會者的基本議事權利，對於議場內足以干擾個人或全體的突發事件，可以立即要求主席解決，通常用於維護議事環境的秩序與舒適，屬於權利動議的一種。根據《羅伯特議事規則》，權宜問題毋需附議，不可...

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

，N满足ZF、然而不满足AC。寇恩的这两项工作和哥德尔在1930年代的工作一起，证明了CH独立于ZFC而AC独立于ZF，因此CH是ZFC上的一个不可判定问题。 凭借CH的独立性证明，寇恩于1966年获得菲尔兹奖章，并于1967年获得美国国家科学奖章。直至今天，寇恩的菲尔兹奖章依然是数理逻辑界获得的唯一一枚菲尔兹奖章。...

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

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

B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}} ，它可以用上下文无关语言的泵引理证实为非上下文无关的。 上下文无关语言的下列问题是不可判定的： 等价：给定两个上下文无关文法 A 和 B， L ( A ) = L ( B ) {\displaystyle L(A)=L(B)} 吗？...

经济计算问题是针对使用经济计划（英语：economic planning）作为生产要素基于市场的分配方式的替代品的批评。首先由路德维希·冯·米塞斯在他1920年的文章《社會主義國家的經濟計算》中提出，后由弗里德里希·哈耶克加以拓展。在他第一篇文章中，米塞斯描述了资本主义下的价格体系的天性并描述了社会...

的语言的判定问题是 PSPACE-完全的。实际上，甚至有些上下文有关文法的固定文法识别问题也是 PSPACE-完全的。 上下文有关文法的空虚（emptiness）问题（给定上下文有关文法 G， L ( G ) = ∅ {\displaystyle L(G)=\emptyset } 吗？）是不可判定的。...

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