Discussion
Which among the following is/are correct statement/statements ?
(i) A class of problems with two outputs "yes" or "no" is said to be decidable (solvable) if there exists some definite algorithm which always terminates (halts) with one of two outputs "yes" or "no". Otherwise, the class of problems is said to be undecidable.
(ii) A decision problem is a problem that requires a yes or no answer.
(iii) Undecidable problem can be solved by a computer or a computer program of any kind.
Answer: A
The correct statements are (i) and (ii) only.
A decision problem is one whose answer is yes or no (ii). It is decidable if some algorithm always halts with the correct yes or no answer for every input, and undecidable otherwise (i).
Statement (iii) contradicts the definition: an undecidable problem, such as the halting problem, cannot be solved by any computer program in general. So options including (iii) are wrong.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development