不可判定問題（undecidable problem）是2018年公布的計算機科學技術名詞。
基本介紹
- 中文名：不可判定問題
- 外文名：undecidable problem
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
定義
不存在一個算法在有窮時間內給出“是”或“否”答案的問題。
出處
《計算機科學技術名詞 》第三版。
不可判定問題
相關詞條
- 不可判定問題
不可判定問題（undecidable problem）是2018年公布的計算機科學技術名詞。定義不存在一個算法在有窮時間內給出“是”或“否”答案的問題。出處《計算機科學技術名詞 》第三版。1...
- 不可判定問題列表
這是一個不可判定問題列表。邏輯問題 大衛·希爾伯特的可判定性。二階Λ演算的類型推論和型別檢查。抽象問題 停機問題（決定圖靈機是否停機）決定圖靈機是否Busy beaver（最長運行的圖靈機有相用的停機問題）死亡率問題（mortality problem...
- 不可判定的遞歸論問題
不可判定的遞歸論問題(undecidable problemsin recursion theory)是指已被證明不具有可判定性的一類遞歸論問題。遞歸論本身的大部分問題都是不可判定的.其中最基本的問題是停機問題(參見“停機問題”).除此之外，根據瑞斯(Rice,H. G.)...
- 正規系統的不可判定性
正規系統的不可判定性是一種文法系統的不可判定特性。正規系統的判定問題是不可解的,由於以上問題是對所有的系統而言,故稱為一般正規系統的判定問題。中文名 正規系統的不可判定性 外文名 undecidability of normal system 適用範圍 數理...
- 波斯特對應問題
波斯特對應問題是指：是否存在算法，可以對任意的波斯特對應系統判斷它是否有解。通過半圖埃系統的不可判定性，可以證明波斯特對應問題是不可解的。波斯特對應問題是波蘭-美國數理邏輯學家波斯特(Post，E.L.)於1946年提出的一個判定問題，...
- 本質不可判定性
由算術系統的本質不可判定性還可以得到諸如ZF系統等重要理論的不可判定性。判定問題 判定問題是數理邏輯中的一個重要問題。它表現為尋求一種能行的方法、一種機械的程式或者算法，從而能夠對某些問題中的任何一個在有窮步驟內確定是否...
- 半群的字問題
群的字問題是一個不可判定性問題。所有有限群和一些可數無窮群，可以由有窮個產生元及這些產生元組成的有窮串(稱為字)上的有窮個等價關係(稱為定義關係)表示。例如半群〈z，0，+〉(z為整數集)可以由兩個產生元{p，n}與等價...
- 算法不可解性
算法不可解性是指對於某個問題構造一個算法，通過這個算法可以決定任意給定的整係數多項式有無整數零點，很長一段時間，很多可判定問題沒有得到解決，即問題本質是不可判定性。簡介 在計算機科學中，算法不可解性是指將某一個問題設計成...
- 不可解問題
不可解問題的判定以特定的不可解性為其研究對象，是數理邏輯的重要研究領域之一。圖靈在1936年（那時還沒電腦，我們的父親是在沒有設備支持的純理論基礎上提出來的，提出了第一個不可解問題的實例：The Halting Problem。The Halting ...
- 時間敏感下推系統可達性的驗證問題
目前，尚未有時間敏感下推系統可達問題可判定一般性結論，也沒有高效的驗證工具。為此，首先，擬採用將2計數器機器規約到該系統的方式，證明一般情況下時間敏感下推系統的可達性不可判定，並通過將各種適於程式分析和系統驗證的時間敏感下...
- 可判定問題
可判定問題是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。定義 存在一個算法在有窮時間內給出“是”或“否”答案的問題。出處 《計算機科學技術名詞 》第三版。公布時間 2018年，經全國科學技術名詞審定委員會審定發布。
- 七橋問題
1736年29歲的歐拉向聖彼得堡科學院遞交了《哥尼斯堡的七座橋》的論文，在解答問題的同時，開創了數學的一個新的分支——圖論與幾何拓撲，也由此展開了數學史上的新曆程。七橋問題提出後，很多人對此很感興趣，紛紛進行試驗，但在相當長...
- 決定性問題
德語“Entscheidungsproblem”，亦即“判定性問題”（Decision-problem），最早出自於大衛·希爾伯特的話：“在1928年的會議上，希爾伯特精確地描述了他的問題。首先，數學是否具有完備性？……其次，數學是否具有相容性？……再次，數學是否...
- 希爾伯特問題
第10到第12問題 （10）能否通過有限步驟來判定不定方程是否存在有理整數解？求出一個整數係數方程的整數根，稱為丟番圖（約210-290，古希臘數學家）方程可解。1950年前後，美國數學家戴維斯（Davis）、普特南（Putnan）、羅賓遜（...
- NP完全問題
P類問題 ：所有可以在多項式時間內求解的判定問題構成P類問題。判定問題 ：判斷是否有一種能夠解決某一類問題的能行算法的研究課題。NP類問題 ：所有的非確定性多項式時間可解的判定問題構成NP類問題。非確定性算法 ：非確定性算法將問題...
- NP(未解難題)
不嚴格的講，NP完全問題是NP類中“最難”的問題，也就是說它們是最可能不屬於P類的。這是因為任何NP中的問題可以在多項式時間內變換成為任何特定NP完全問題的一個特例。例如，旅行商問題的判定問題版本是NP完全的。所以NP中的任何問題...
- 哥德爾不完全性定理(數理邏輯術語)
該定理與塔爾斯基的形式語言的真理論，圖靈機和判定問題，被讚譽為現代邏輯科學在哲學方面的三大成果。哥德爾證明了任何一個形式系統，只要包括了簡單的初等數論描述，而且是自洽的，它必定包含某些系統內所允許的方法既不能證明真也不能...
- 悖論(邏輯學詞語概念)
這些難題涉及基本概念以及定義和推理的基本方法，這些以前通常被認為是沒有問題的。悖論在當代邏輯中獲得了新的作用，它們導致了新定理的發現（通常是負面的結果，例如不可證明性和不可判定性）。邏輯的幾個基本概念發展過程，之所以已經到...
- 上下文無關語言
可判定性性質 上下文無關語言的下列問題是不可判定的：等價：給定兩個上下文無關文法A 和 B，嗎？嗎？嗎？嗎？上下文無關語言的下列問題是可判定的：嗎？L(A) 是有限的嗎？成員關係：給定任何字 w，嗎？（成員關係問題甚至是...
- 非確定性多項式難題
可解問題也分為多項式問題(Polynomial Problem，P問題)和非確定性多項式問題(NondeterministicPolynomial Problem，NP問題)。P問題 P問題是一個判定問題類，這些問題可以用一個確定性算法在多項式時間內判定或解出。如果一個判定性問題的複雜...
- 不可定義性理論
該定理與關於的判定問題的不可解性有一定聯繫。 80年代以來，在模型論中對於模型的範疇性，也就是它的完備理論的範疇性，有較多的研究，從性質上說，這是一種關於可定義性的廣義研究。例如，有理數域不是埲 -範疇的，其含義是：...
- 能行性和一般遞歸
根據丘奇的論題，便可以對判定問題作進一步的討論。判定問題分問答題與求作題兩種。要求回答"是""否"的叫做問答題，要求用一個自然數回答的叫做求作題。例如，"3整除 5嗎？"是問答題,"求m,n之積"是求作題。問題又分個別題與...
