Question

please answer and I will rate!

3. Let L = {M M is a Turing machine and L(M) is empty), where L(M) is the language accepted by M. Prove Lis undecidable by finding a reduction from Arm to it, where Ayv-<<MwM is a Turing machine and M accepts w). Answer:

Answer 1

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

Firstly we will 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.

first step:

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 belongs to L(N) ,

hence, L(N) is non empty set

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) is empty set

This proves that $\langle M,w\rangle$ is belongs to   $A_{TM}$ iff N

EL.

Hence the reduction is valid.

Therefore, using the fact that $A_{TM}$ is undecidable,

it proves that $\overline{L} .$ is undecidable.

---------------------------------------------------------------------------------

2)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 will 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.

-----------------------------------------------------------------------------------------------

From both step we conclude that  L is undecidable.

This completed the required proof .