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

Ask an Expert

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

Write your message here..

Related Questions

Constract Context free, constract context free g ={ a^n b^m : m,n >=0 and n... constract context free g ={ a^n b^m : m,n >=0 and n

Mapping reducibility, (c) Can you say that B is decidable? (d) If you someh... (c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

Finite automata, design an automata for strings having exactly four 1''s design an automata for strings having exactly four 1''s

NP complete, I want a proof for any NP complete problem I want a proof for any NP complete problem

Generalization of the interpretation of local automata, The generalization ... The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

Automaton for finite languages, We can then specify any language in the cla... We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

Non deterministic finite state automaton, Automaton (NFA) (with ε-transitio... Automaton (NFA) (with ε-transitions) is a 5-tuple: (Q,Σ, δ, q 0 , F i where Q, Σ, q 0 and F are as in a DFA and T ⊆ Q × Q × (Σ ∪ {ε}). We must also modify the de?nitions of th

Xx, Ask queyystion #Minimum 100 words accepted# Ask queyystion #Minimum 100 words accepted#

Recognition problem, The Recognition Problem for a class of languages is th... The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

Third model of computation, Computer has a single LIFO stack containing ?xe... Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev