Sir ...I know all the problems given below are undecidable because they are non trivial property of RELs....but i have some doubt...
L1 = {<M>| M is a TM and and TM M accepts some strings of length at most 100}
my doubt ...Is this problem R.E. or not R.E. ??? I think this problem is R.E. because I can generate all the strings of length at most 100 and then use the method of dovetailing to see they are accepted or not....am I right or wrong???
And is this problem same as { <M> | M is a TM and | L(M) | <= 100 } which is not R.E. ???
L2 ={<M> | M is a TM and TM accepts all strings of length at most 100 }...
Is this problem R.E. or not R.E. ??? Can I use dovetailing here??
L3= {<M>| M is a TM and TM accepts some strings of length greater than 100 }
Is this problem R.E. or not R.E. ?? Can I use dovetailing here...and is this problem same as { < M > | M is a TM and
| L(M) | > 100 } which is R.E. but not recursive ????
L4 = {<M>| M is a TM and TM accepts all strings of length greater than 100 }
Is this problem R.E. or not R.E. ?? Can I use dovetailing here...
L5 ={ < M > | M is a TM and M never reaches the accepting state }
Is this problem recursive or R.E or not RE ??? is this problem same as state entry problem which is undecidable???
L6 = { < M > | M is a TM and L(M) = 0^n 1^n }
ans : this is a non trivial property and hence satisfies Rice 1st theorem so it is undecidable..
it also satisfies Rice 2nd theorem and it is a non-monotonic property of TM and hence we have at least two TMs one which satisfies the property (TM yes) and one which violates the property (TM no).
L(TM yes ) = 0^n 1^n and L (TM no) = sigma*..
so L(TM yes ) is a proper subset of L (TM no) ...hence L6 is not Recursively Enumerable. sir please verify whether my solution is right or wrong???
Sir please explain this??
