What is the difference ??

Question

Please explain clearly?

Answer 1

• $L_{12} = \{ \langle M\rangle \mid M $ is a TM and $M_{0}$ is also a TM which halts on all inputs and $M_{0} \in L(M) \}$

This set consists of all those TM's whose languages contain the encoding of TM M₀ which halts on all the inputs. So, suppose we are given a TM M₁ and we have a task to check whether M₀ belongs to the language of TM M₁ which can be done simply by running M₁ over M₀ and halts if M₁ accepts M_{0 .} Hence, we have recognized the language by a recognizer .

We will add M₁ to this set and similarly, we can check with all other TM's such as M₂ , M₃ and so on. They all can be added to this set .

But, is the language decidable? we have already established that this language is RE but what about R ? So, the question is simple whether the TM M₁  (halts or loops) if the given M₀ is not there in the language of L(M₁) ?

For this, we use Rice's theorem to prove undecidability but here it is little bit twisted .

---

This says that the languages which follow a certain property is indeed undecidable.

More can be found here => http://gatecse.in/rices-theorem/

Given a property P, such that $\Phi \subset P \subset RE$, then the language 

=> $L_{p} = \left \{ \langle M \rangle \mid M\ \in RE \right \}$ is undecidable.

Here, for this language we can form this property P as

$P = \left \{ L | M_{0}\ \in L\ and\ L\ \in RE\ \right \}$

and the set folowing this property P will be

$L_{P} =\left \{ \langle M \rangle \mid L(M)\ \in P \right \}$

Hence, If the given property P = PHI or  P = RE then it becomes trivial, but here clearly, that property is "not all of the RE" and "not none of the RE". If P = PHI that means none of the TM follow that and If P = RE that means all the TM follow this making it trivial property(always true).

Here, This property P is non trivial in the sense that "Some TM follow this property and some do not".

Hence, Atlast it can be said that L₁₂ is undecidable in the sense of rice theorem.

---

• $L_{13} = \{ \langle M\rangle \mid M$ is a TM\ and $M_{0}$ is also a TM which halts on all inputs and $M\ \in L\left(M_{0}\right)  \}$

Now, Similarly this set contains the TM whose encodings are contained in the language of TM M₀ which halts on all the inputs.

So, it can be clearly seen that M₀ halts on all the inputs so, if we input it with a string which is contained in its language, then it will always halt and say accept

But, if we input it with a string which is not contained in the language , then also it will always halt and say reject.

Since, it is providing YES as well as NO answers, making this set decidable .

Comments

I guess it depends on how you apply that intuition. And yes, if question is understood properly many decidability problems can be answered by "intuition". But the thing is those who cannot understand Rice's theorem usually won't be able to get the intuition correct.

---

We can say it easily like

M is a TM, M₀ another TM.

M₀ halts on every input.

1) M₀ includes one language of M, L(M). As it halts on every input, it also halt for L(M). So, here halting problem is satisfied. As halting problem is undecidable, so, this problem also undecidable (Also we can say T_no condition cannot be satisfied here, so it is RE.)

2) Here M includes M₀. But we donot confirm if M halts or not. For some inputs M accepts the input of M₀, for other inputs M doesnot halt on M₀.So, here 'yes' and 'no' both answer present. That means here language is decidable.

Is there any need of Rice Problem or double recursion here? Coeect me

---

No. It is wrong. $L(M)$ includes $M_0$ - not the other way. Also, halting problem is halting of a general TM for a given input - here $M_0$ is a halting TM (not a general) and it is guaranteed to halt for any input.

And anyway this question should be read only after covering a good number of decidability problems.

Answer 2

Here, $L_{12}$ includes the description of TMs $M$ such that that  $M$ accepts the given halting TM $M_0$. i.e. inorder for a TM description to be in $L_{12}$, that machine must accept $M_0$ (double recursion?) which is a halting TM.

Now, $L_{13}$ includes the description of TMs $M$ such that $M$ element of $L(M_0)$  where $M_0$ is a TM that halts on all inputs. Since $M_0$ halts for all inputs, to decide $L_{13}$ we can simply run its input on $M_0$ which is guaranteed to halt.

Comments

Sir, I don't understand anything

---

Not surprising. The issue with reduction is that usually only the one who writes it understands - like a complex code. This question and explanation is so simple to the one who wrote it but not for others. So, to understand this only way is to form our own answer (of course not wrong one). I suggest to do Rice's theorem and its examples - is given in gatecse.in TOC page. And while seeing, do the examples on own starting with easy ones. Rice's theorem is fairly or much easier compared to reduction. Finally come back to this question as this has an extra layer of twist.

---

sir plz explain in simple terms i didn't get it :(