#TOC plz help

Question

Consider the following two languages :

S1: L1= {<M>|M is a TM AND L(M)>=3}

S2: L2= {<M>|M is a TM AND L(M)<3}

Which of the following is correct?
a. Only S1 is REC b. Only S2 is REC c.   Both S1 and S2 are REC d.   None of the above is REC

Comments

my reasoning correct or wrong ??

---

L1 - recursively enumerable but not recursive ??

---

You may find this helpful : http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf

See L2 and L3. It is exactly the same question.

Answer 1

Okay, we have L1 and L2 are complement of each other here.and we know that recursives are closed under complementation! so if L1 is recursive then L2 has to be recursive and vice versa.

so we can easily get rid of option A, B here

Now, i assume that L(M) means Language of turing Machine

Now let's

check for L1:

After providing an Input,if the it goes >= 3 then it Accepts it but if it gets into  Loop, much before ,then we have no way to know if it will Accept that i/p or Not

so we can't say it rejects for other inputs

so it is Recursively Enumerable but not Recursive

Check for L2:

No way to know,what's going to happen if it gets into a loop

so it is Non RE

ALTERNATIVE:

Both of this are Non-Trivial Property.According to Rice theorem they are Not Recursive

So D should be the answer.Correct me ,if i am wrong

Comments

After providing an Input,if the Length goes >=3,then it Accepts...

What do you mean by this statement ? Do you mean to say if 3 input symbols are read ? If so then the problem of 'deciding if a given TM reads at least 3 chars from input tape' is decidable.

And, I think L(M) does not mean length of M. L(M) means the language accepted by the TM. So, L(M) < 3 should mean that if M accepts less than 3 inputs then our deciding TM should say YES else NO. The problem of finding L(M) $\geq$ 3 is RE(but not recursive) because using dovetailing we can say 'YES' easily. So, S1 would be RE(semidecidable) but not recursive and S2 is definitely not RE. 

---

yes, you are correct! i missed something!.