Undecidable

From Wikipedia, the free encyclopedia

Look up undecidable in Wiktionary, the free dictionary.

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 and Undecidable problem.
• "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.

Other uses

• Undecidable figure
• Undecidable language
• Undecidable problem
• Undecidable set

Also

• List of undecidable problems

[edit] See also

• Decidable

This disambiguation page lists articles associated with the same title. If an internal link led you here, you may wish to change the link to point directly to the intended article.