Encyclopedia > Undecidable

  Article Content

Undecidable language

Redirected from Undecidable

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 partially decidable. A problem can be both undecidable and partially decidable. One example of this is the halting problem.

If there is an algorithm that always answers correctly, both for YES and NO answers, then the problem 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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Wheatley Heights, New York

... 65 years of age or older. The median age is 35 years. For every 100 females there are 95.1 males. For every 100 females age 18 and over, there are 89.3 males. Th ...

 
 
 
This page was created in 28.4 ms