Some Questions on Decidabilty

Question

1) Is it decidable whether a given Turing machine accepts any string at all? That is, is L(M) not equal to  ∅? 

2) Is it decidable whether a given Turing machine accepts all strings? That is, is L(M) = A*? 

3) Is it decidable whether a given Turing machine accepts a finite set? 

4) Is it decidable whether a given Turing machine accepts a regular set? 

My reasoning/Solutions -------------------------------------------------------------------------------------------------------------------------

1) I don't know. Please tell.

2) Is it Completeness Problem? If yes, then its UD.

3) Finiteness Problem and it's UD

4) UD

Comments

None are decidable

---

1. is RE using devotelling method.

2. is non RE since L(M) =sigma* is undecidable.

3. reduces to finiteness. undecidable

4. reduces to regularity problem . undecidable

Answer 1

Though all are undecidable, but more precisely:

1. RE
2. NOT RE
3. NOT RE
4. NOT RE

Answer 2

actually 2nd one was  MEMBERSHIP  problem  and it is UNDECIDABLE iff L(M) is REL

and the first one is completeness problem  it is also UD for TM

so all are UD  except OPTION 3 (D) hence it is  FINITE SET