Peter Linz Edition 5 Exercise 12.1 Question 1 (Page No. 307)

Question

If the halting problem were decidable, then every recursively enumerable language would be recursive. Consequently, the halting problem is undecidable.

Describe in detail how $H$ in given Theorem can be modified to produce $H^{\prime} $.

Comments

If the halting problem were decidable,then every recursively enumerable language would be recursive but we know that there is at least one language that is recursive enumerable but not recursive ,hence we arrive at the contradiction

Therefore halting problem must be undecidable!