decidable

Definition from Wiktionary, a free dictionary

Contents 1 English 1.1 Adjective 1.1.1 Antonyms 1.1.2 Derived terms 1.1.3 Related terms 1.1.4 Translations 1.2 References

[edit] English

[edit] Adjective

decidable (comparative more decidable, superlative most decidable)

1. capable of being decided.
2. (computer science) describing a set for which there exists an algorithm that will determine whether any element is or is not within the set in a finite amount of time.

   It is easy to show that the set of even numbers is decidable by creating the relevant Turing machine.

3. (logic) in intuitionistic logic, a proposition P is decidable in a given theory if it can be proven from the theory that "either P or not P", i.e. in symbols: .^[1]

[edit] Antonyms

• undecidable

[edit] Derived terms

• semi-decidable

[edit] Related terms

• decidability

[edit] Translations

[edit] References

• Notes:

1. ^ http://plato.stanford.edu/entries/logic-intuitionistic/