Discussion
If there exists a Turing machine M which when applied to any problem in the class terminates if the correct answer is yes and may not terminate otherwise is said to be .................. .
Answer: C
Such a class is said to be Partially solvable.
A problem is partially solvable (semi-decidable) when a Turing machine exists that halts and answers yes on every yes-instance, but may run forever on a no-instance. The halting problem itself is of this kind: simulating the machine eventually confirms that it halts, but never confirms that it does not.
A problem is solvable when some Turing machine halts on every instance with the right answer, and unsolvable when none does. 'Stable' and 'unstable' are not terms of computability theory.
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