ACE Test Series

Question

Comments

C?

---

@Mk Utkarsh i also marked it as C  but answer given is A.

---

Should be A only.
RE set is the set of Turing of acceptable languages only.

---

Soumya29 example of RE language?

---

in P2, whether <M> accepts Recursively Enumerable Language a trivial property as a Turing accepts all Recursive Enumerable Languages.

So, it should be decidable.

Correct me if I'm wrong.

---

I think P1 is sort of a membership problem. Membership problems are decidable in RE languages.

---

Isn't the membership problem similar to halting problem which is undecidable ?

I think membership problem in RE languages are undecidable

---

there is a difference between Turing acceptable and Turing decidable

http://web.cs.iastate.edu/~cs531/notes/notes2.pdf

---

$L_1$ be $\{\text{<M>, M halts on w \}}$

this is well known RE language

Now how $L_1$ is accepted by arbitrary TM is decidable?

---

@Mk Utkarsh

what I think 

TM accepts both RE and Rec problem. And as it accepts RE language, it is accepting some undecidable String. So, P1 is undecidable

but for TM accepts RE language - it is always true. So, here for TM yes and no ans possible . Language will be decidable

---

@Mk Utkarsh yes there is difference, but turing acceptable comes when some strings belong to language and some not, but here the property says whether T.M. will accept REL or not and a T.M. will accept on every REL so the property holds for every T.M., so it is trivial and hence decidable.

---

whether REL are undecidable and the statement $P_{2}$ are totally different

---

Shobhit Joshi yes that link is not related

---

Yes it's not. So can we conclude REL are undecidable and TM accepts RE languages ?

---

TM accepts RE but it may or may not reject RE -->I think saying accepts RE is decidable is true

and whether TM accepts a string can be reduced to halting problem whether TM halts so its Undecidable.

---

@Mk Utkarsh, $P2$ is trivial property. 
That's why it is decidable. Every TM will satisfy this property. 
See informally how I understand it -  
Suppose $<M_1>,<M_2>,<M_3>.........$ these are the descriptions of TMs. Now when I pick each description one by one and check $L(M_i), where \  i=1,2,3.....$, I find that each $L(M_i)$ is a $R.E$ set so each $<M_i>$ will satisfy our required property hence its a trivial property of $T.Ms.$
@Shobhit Joshi @Hemanth_13 Can you please verify it once?

---

@Soumya29 yes you are correct

---

Thanks for verifying :)

Answer 1

a)1. Run the TM on the string
w. If it ever enters its accept state, accept.
2. If it ever enters its reject, reject.

3) it can also go in infinite loop

Thus, we've proven that it is undecidable.

b)

Decidability is possible if the property is there for any recursively enumerable languages or if it is absent for all recursively enumerable languages (trivial)

since a given TM has a language which is REL

So TM accepts a REL is trivial property so it is decidable