Undecidable

From Wikipedia, the free encyclopedia

Undecidable has more than one meaning:

In mathematical logic:

  • 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.
In other languages