Jump to content

Undecidable

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by LC~enwiki (talk | contribs) at 00:07, 3 June 2002. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

In computability theory, a decision problem is undecidable if there is no algorithm that can always give the correct answer.

If there is an algorithm that answers YES when the correct answer is YES, and runs forever when the correct answer is NO, then the problem is both undecidable and partially decidable.

If there is an algorithm that always answers correctly, both for YES and NO answers, then the problems is decidable, and is not undecidable.

A formal language is said to be undecidable if the decision problem "is a given string in this language" is undecidable.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Undecidable&oldid=84828"