What is the meaning of an undecidable problem in computer science?
Options
-
A.
A problem that requires constant time
-
B.
A problem that cannot be solved by any algorithm for all inputs
-
C.
A problem that requires linear time
-
D.
More than one of the above
-
E.
None of the above
Correct Answer (Detailed Explanation is Below)
B.
A problem that cannot be solved by any algorithm for all inputs
Detailed Explanation
- Undecidable Problem: There is no algorithm that correctly decides every possible instance and halts on all inputs.
- Important Difference: Undecidable does not simply mean difficult or time-consuming.
- Example: General Halting Problem and Post Correspondence Problem.
