$ E_{\text{TM}} = \{ \langle M \rangle \mid L(M) = \varnothing \} $ is undecidable.

Question

In this proof, we need to convert the input from $ \langle M,w \rangle $ to $ M_{1} $ as $ E_{\text{TM}} $’s input is only a Turing Machine. However, I couldn’t understand the construction of $ M_{1} $, mainly I couldn't understand what “On input $ x $” means for $ M_{1} $? Where does this $ x $ come from? How will this input $ x $ be given to $ M_{1} $?

Answer 1

You can use the basic halting problem proof to show this. A Turing Machine can print out its own description, and can simulate an arbitrary Turing machine on arbitrary input. So assume you had a Turing machine $T$ that could decide your problem. Then build a Turing machine $T'$ that prints out its description and simulates $T$ on that input. Then if $T$ says the language of $T'$ is empty, then accept any string. Otherwise, accept no strings. This contradicts the output of $T$ so $T$ cannot exist.