Exhaustive search, Theory of Computation

A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be noted that an unsolvable problem might be partially solvable by an algorithm that makes a complete search for a solution. In such case the solution is eventually found whenever it is defined, but the search might continue forever whenever the solution is undefined. Similarly, an undecidable problem might also be partially decidable by an algorithm that makes an exhaustive search.

Posted Date: 3/18/2013 1:12:38 AM | Location : United States







Related Discussions:- Exhaustive search, Assignment Help, Ask Question on Exhaustive search, Get Answer, Expert's Help, Exhaustive search Discussions

Write discussion on Exhaustive search
Your posts are moderated
Related Questions
To see this, note that if there are any cycles in the Myhill graph of A then L(A) will be infinite, since any such cycle can be repeated arbitrarily many times. Conversely, if the


How useful is production function in production planning?



what are composition and its function of gastric juice

Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

turing machine for prime numbers

The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive