P/NP问题和停机问题

快捷方式: 差异，相似，杰卡德相似系数，参考。

P/NP问题和停机问题之间的区别

P/NP问题 vs. 停机问题

P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和相对独立地提出了下面的问题，即复杂度类P和NP是否是恒等的（P. 停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个 s \in S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不自洽性和不完备性，类似的命题有理发师悖论、全能悖论等。.

一阶逻辑

一阶逻辑是使用於数学、哲学、语言学及電腦科學中的一种形式系统。 過去一百多年，一階邏輯出現過許多種名稱，包括：一阶斷言演算、低階斷言演算、量化理論或斷言逻辑（一個較不精確的用詞）。一階邏輯和命題邏輯的不同之處在於，一階邏輯有使用量化變數。一個一階邏輯，若具有由一系列量化變數、一個以上有意義的斷言字母及包含了有意義的斷言字母的純公理所組成的特定論域，即是一個一階理論。 一階邏輯和其他高階邏輯不同之處在於，高階邏輯的斷言可以有斷言或函數當做引數，且允許斷言量詞或函數量詞的（同時或不同時）存在。在一階邏輯中，斷言通常和集合相關連。在有意義的高階邏輯中，斷言則會被解釋為集合的集合。 存在許多對一階邏輯是可靠（所有可證的敘述皆為真）且完備（所有為真的敘述皆可證）的演繹系統。雖然一階邏輯的邏輯歸結只是半可判定性的，但還是有許多用於一階邏輯上的自動定理證明。一階邏輯也符合一些使其能通過證明論分析的元邏輯定理，如勒文海姆–斯科倫定理及緊緻性定理。 一階邏輯是數學基礎中很重要的一部份，因為它是公理系統的標準形式邏輯。許多常見的公理系統，如一階皮亞諾公理和包含策梅洛-弗蘭克爾集合論的公理化集合論等，都可以形式化成一階理論。然而，一階定理並沒有能力去完整描述及範疇性地建構如自然數或實數之類無限的概念。這些結構的公理系統可以由如二階邏輯之類更強的邏輯來取得。.

P/NP问题和一阶逻辑 · 一阶逻辑和停机问题 · 查看更多 »

图灵机

图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.

P/NP问题和图灵机 · 停机问题和图灵机 · 查看更多 »