COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Indefinite
|
|
|
Undecidable
|
|
|
Intractable
|
|
|
Impossible
|
Detailed explanation-1: -An undecidable problem is one that should give a “yes” or “no” answer, but yet no algorithm exists that can answer correctly on all inputs.
Detailed explanation-2: -Undecidable Problems. These problems are the theoretically impossible to solve-by any algorithm. The halting problem is a decision problem (with a yes or no answer) that is undecidable. A computer cannot tell if it is in an infinite loop or it will at some point stop!
Detailed explanation-3: -An unsolvable problem is one for which no algorithm can ever be written to find the solution. An undecidable problem is one for which no algorithm can ever be written that will always give a correct true/false decision for every input value.
Detailed explanation-4: -Emptiness problem of Turing machine is undecidable.
Detailed explanation-5: -Examples – These are few important Undecidable Problems: Whether a CFG generates all the strings or not? As a CFG generates infinite strings, we can’t ever reach up to the last string and hence it is Undecidable.