Decidability

Question

The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ is

a) Decidable b) Semi decidable c) not even semi-decidable

Comments

C) Undecidable

---

It will not be turing recognizable hence undecidable.

Answer 1

$L$ is describing an undecidable and not even semi-decidable problem. We can prove this by reducing complement of halting problem to $L$. Complement of halting problem $H'$ can be stated as

• Given a TM description and a word as $\langle M, w \rangle$, we have to say whether $M$ does not halt on $w$.

If we can answer "yes" for all "yes" cases, then the problem becomes semi-decidable. Since this problem is known to be not semi-decidable we should not be able to say "yes" for all "yes" cases. 

Now, for reduction, given an instance of $H'$, $\langle M,w \rangle,$ we can make another TM $M_1$ which if halt will accept the given input and otherwise accepts nothing. So, if $M$ halts on $w$, $L(M_1)$ contains at least $w$ and if $M$ does not halt on $w$, $L(M_1) = \emptyset.$ So, now if we can see if $M_1 = M_2$, where $L(M_2) = \emptyset$ we can answer the complement of halting problem. TM for our given $L$ must be able to do this at least when $M_1 = M_2$ if $L$ is describing a semi-decidable problem. But this is not possible, and hence $L$ cannot be describing a semi-decidable problem (non recursively enumerable).  

Answer 2

option c

here language is not given then we can consider as recursive ennum language. becz it include all language .now question become equvalence problem of recursive ennum language . which is undesidable.

Comments

why not semi decidable?undecidable language can be semi decidable also.

Answer 3

This language is not even semi decidable(i.e not recursively enumerable).So it is undecidable.

We can reduce complement of  halting problem(<M,w>,M doesn't halt on w),which is known to be not recursively enumerable to this problem by following way:

Take TM M₂ as a halting TM.Suppose it is "TM accepting prime numbers as input".We can easily construct a halting TM for this language.

Now we modify TM 'M' of the non halting problem <M,w> as the following way and use it as TM M₁

For all input x we run TM M  on w for $\left | x \right |$ steps.If the TM M doesn't halt within  $\left | x \right |$  steps then we run a copy of the TM M₂(accepting all the prime numbers) as a subroutine.So M₁ will accept all  those input 'x' which are prime numbers,when TM M doesn't halt on w within $\left | x \right |$  steps.

And if the TM M  halts within this $\left | x \right |$  steps then we will run another TM as subroutine which accepts all the numbers which are not prime numbers(This language also has halting TM).

This whole construction is named as TM M1.

So M1 is accepting all prime number set if M doesn't halt on w and accepting non prime numbers(not the complete non prime number set) if M  halts on w.

Assume that L = { <M₁,M₂> | L(M₁) = L(M₂) } is recursively enumerable language.So it has a TM.Let us give name of the TM as R.

Now take the encoding of TM M₁ & M₂ which we constructed above and give it to TM R.If R accepts <M₁,M₂>(yes instance) then TM R informing us that M₁ and M₂ accepts same language.i.e M doesn't halt on w.Because prime numbers are infinite and if  M doesn't halt on w then M₁ will accept all the prime numbers.So that indicates M1 is same as M2(M2 also accepting whole prime number set).

Hence we come to a conclusion that if TM R exists then we can decide whether M doesn't halt on x.So clearly TM R can't exist.i.e This language is not even semi decidable

Comments

yes sir if we take  L(M2)=∅ then also it's fine.And i think this is the one and only finite language  we can take into consideration for L(M2).

---

Okay :) Youll get full mark in exam, but your answer is difficult for a newbie to follow. Ideally if we add why something was chosen in an answer, it will make the answer better.

---

Thanks sir.I will try to follow that next time.

Answer 4

The two languages can be reduced to another set of languages. Let the set be T1  and T2. Now T1 can or can not be equal to T2   . Hence if the reduced version is undecidable then the parent can/cannot be decidable therefore the problem becomes undecidable .