English

Adjective

1. (Of a formal language) Incapable of being algorithmically decided in finite time. A set of strings is undecidable if it is impossible to program a computer (even one with infinite memory) to determine whether or not specified strings are included.

Antonyms

• undecidable

Related terms

• noncomputable

Translations

• A decision problem is called (recursively) undecidable if no algorithm can decide it, such as for Turing's halting problem; see also under Decidable.
• "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation can be proved within the theory.
• Decidable
• List of undecidable problems