定义

决定性问题 指的是在一个数量为无限大的输入集合中，可产出任何是或非解答的问题之集合。因此传统上定义决定性问题，乃依其解答为 是 的输入之集合。在此情形下，一决定性问题亦等于一形式语言。

形式上，决定性问题是一自然数子集 A 。借由使用哥德尔数，也可学习诸如形式语言的其他集合。非正规的定义决定性问题，就是判别一个给予的数字是否在此集合内。

一决定性问题若其 A 是一个递归集合，则称做 可决定的 （decidable）或 有效可解 （effectively solvable）。若其 A 是一递归可枚举集合则称为 部分可决定的 （partially decidable）、 半可决定的 （semidecidable）、 可解的 （solvable）或 可证明 （provable）。除此之外，此问题称为 不可决定的 。

例子

一个经典可决定的决定性问题是质数问题。借由测试每一个可能的因数，有可能 有效决定 一个自然数是否为质数。尽管存在很多效能更佳的质数判定方法，任何有效方法的存在就已足够建立可决定性。

重要的不可决定的决定性问题包括停机问题，其他请见不可决定的问题列表。在计算复杂性理论中，完备的决定性问题通常用来判别其他决定性问题的复杂度类别。重要的实例包括SAT问题与其数变种，还有无向与有向图可达性问题。

历史

德语“ Entscheidungsproblem ”，亦即“判定性问题”（Decision-problem），最早出自于大卫·希尔伯特的话：“在1928年的会议上，希尔伯特精确地描述了他的问题。首先，数学是否具有完备性？……其次，数学是否具有相容性？……再次，数学是否具有判定性？这些问题的意思是，是否存在这样一种确定的方法，在理论上可适用于任何假设，并且能够保证对无论是否正确的假设都能给出一个正确的结果”（Hodeges，p. 91）。希尔伯特相信“在数学上没有‘ignorabimus’”，亦即“我们将无从得之”。需要了解更多信息请参见大卫·希尔伯特和停机问题。

与函数问题的等价性

参考

Hodges, A., Alan Turing: The Enigma , Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for some more history that led to Turing"s work.

Kozen, D.C.（1997）, Automata and Computability , Springer.

Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability , MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1

Sipser, M.（1996）, Introduction to the Theory of Computation , PWS Publishing Co.

Robert I. Soare (1987), Recursively Enumerable Sets and Degrees , Springer-Verlag, ISBN 0-387-15299-7

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。