in Theory of Computation
481 views
0 votes
0 votes

in Theory of Computation
481 views

4 Comments

edited by

@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?

0
0

@Soumya29 yes you are correct

0
0
Thanks for verifying :)
0
0

1 Answer

0 votes
0 votes
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