Question

We showed that since the problem concerning a machine halting on its own index is unsolvable, the general halting problem for Turing machines is unsolvable. Does this imply that any superset of an unsolvable problem is unsolvable? Provide a proof or a counterexample.

Answer 1

from the given question i am saying that yes any super set of an unsolvable problem is unsolvable.
Halting problem of turing machine is called as a NPC(Non Polynomial Complexity) problem.
And any superset of a NPC problem is a NPC.

The Halting Problem actually cannot be solved, as demonstrated by a “proof by contradiction.” This is a non-technical summary of the proof as a computer programmer might express it.

Example to prove that :
Let HPM be the Turing machine that is supposed to solve the Halting Problem. Let UM be the “Unsolvable Machine,” or the one that will cause the HPM to fail. The UM itself is an adaptation of a UTM, and its actions depend on the instructions of the HPM.

If the HPM could succeed, it would look like this: The HPM would read the UM’s encoded instructions, plus whatever input the UM would read, and after a finite number of steps, the HPM would report either “Yes, the UM will halt” or “No, the UM will not halt”.

When put to the test, however, this UM will behave as a UTM, and will read the HPM’s encoded instructions as its input, then read its own UM code as the secondary input, and finally emulate the HPM’s processes until the HPM makes its report.

If the UM process shows that the HPM would report “Yes, the UM will halt,” then the UM’s instructions are to instead begin a loop, repeating the message that it will never halt, in direct contradiction of what the HPM expects.

If the UM determines that the HPM would report “No, the UM will not halt,” then the UM will instead write the message that it is halting, and do so – again, its instructions cause it to contradict the HPM.

The HPM is not allowed to be “clever” enough to report that the UM is programmed to do the opposite of what it predicts; the only valid responses are the predictions “will halt” or “will not halt”. If the HTM cannot make its prediction in a finite number of steps, then it also fails to meet the criteria.

By calculating what the HTM predicts it to do, and then doing the opposite, the UM can foil any proposed Turing machine that is supposed to be able to solve the Halting Problem.