Question

3. Let L= {MM is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove L is undecidable by finding a reduction from Arm to it, where Arm={<M,w>| M is a Turing machine and M accepts w}

Answer 1

ANSWER :

Prove that L = \{M | L(M) = \emptyset\} is undecidable in two steps as follows:

Prove that \overline{L} i.e. the complement of L is undecidable by reducing from A_{TM} .
Prove that if L is decidable then so is \overline{L} . Therefore, using the contrapositive, \overline{L} being undecidable proves that L is undecidable.
To prove the first step, the reduction is as follows:

Let \langle M,w\rangle be an instance of A_{TM} . Design a machine N, which has \langle M,w\rangle hardcoded in its own description, and behaves as follows:
On input T , it first checks whether x = w . If not, N rejects and halts. Otherwise, it starts a simulation of M on w , using the Universal simulation of Turing machines. If the simulation leads to acceptance, N accepts. If the simulation leads to rejection, N rejects. If the simulation doesn't halt, clearly N will not halt either.

Output N as an instance of \overline{L} . This is the reduction. Note that this can be carried out by a Turing machine, as it simply needs to hardcode \langle M,w\rangle into the description of Universal Turing machine, and it already gets \langle M,w\rangle as the input. Therefore all that remains to be proven is that the reduction is valid.

Let \langle M,w\rangle be a positive instance of A_{TM} . In this case, when the input of N is w , it will run the simulation of M on w. The simulation will lead to acceptance, therefore w \in L(N) , hence L(N) \neq \emptyset .
Let \langle M,w\rangle be a negative instance of A_{TM} . In this case, N already rejects all inputs other than w . On input w , it will run a simulation of M on w. The simulation will either lead to rejection or not halt, and in both cases N doesn't accept w. Therefore N doesn't accept any input, hence L(N) = \emptyset .

This proves that \langle M,w\rangle \in A_{TM} \iff N \in \overline{L} . Hence the reduction is valid. Therefore, using the fact that A_{TM} is undecidable, it proves that \overline{L} is undecidable. This completes the first step.

For the second step, let L be decidable. Then there is a Turing machine M which halts on each input and accepts if and only if the input is in L. Create another Turing machine M' which will behave exactly the same as M except it wil have the accept and reject states switched. Therefore M' will also halt on each input and accept if and only if the input is not in L i.e. is in \overline{L} . This proves that \overline{L} is decidable. This completes the second step.

The two steps together imply that L is undecidable. The proof is complete.

Hope it helps... Thank you:)