可判定性

一个语言，是一个集合，且其补集为 。
当是图灵机可识别时，语言则称为半可判定。
当语言不是图灵机可识别，则为不可判定语言。
当且仅当和都是图灵机可识别的时候，L才能称为可判定语言。

In mathematics and computer science, the Entscheidungsproblem (pronounced[ɛntˈʃaɪ̯dʊŋspʁoˌbleːm], German for 'decision problem') is a challenge posed by David Hilbert in 1928. The Entscheidungsproblem asks for an algorithm that takes as input a statement of a first-order logic (possibly with a finite number of axioms beyond the usual axioms of first-order logic) and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.