COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Undecidable problems are problems for which more than one algorithm solves the problem and computer scientists have not yet chosen the algorithm they believe is best
|
|
|
Undecidable problems are problems for which an algorithm can be written that will produce the same output for at least two possible inputs
|
|
|
Undecidable problems are problems for which an algorithm can be written that produces a correct output for all inputs but in an unreasonable time
|
|
|
An undecidable problem is a problem for which no algorithm can be constructed that always produces a correct output
|
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: -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.
Detailed explanation-3: -Explanation: Problems cannot be solved by any algorithm are called undecidable problems. Problems that can be solved in polynomial time are called Tractable problems.
Detailed explanation-4: -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.