決定性問題和递归论

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

決定性問題和递归论之间的区别

決定性問題 vs. 递归论

在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。. 递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论（effective descriptive set theory）有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。.

停机问题

停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个 s \in S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不自洽性和不完备性，类似的命题有理发师悖论、全能悖论等。.

停机问题和決定性問題 · 停机问题和递归论 · 查看更多 »