TM Decidablity

Question

Why this statement Turing Machine accepts the null string epsilon ? is not Decidable ? explain with an example.

Answer 1

The question is whether 

• whether a TM $M$ accepts null string $\epsilon$

and not 

• whether ANY TM accepts null string $\epsilon$

Answer to second one is "YES" and is independent of the input making the problem trivial.

For the first one, answer is "undecidable" but "semi-decidable". We can have 

• $L(T_{yes}) = \{\epsilon\}$ and $L(T_{no}) = \{\}$ and thus the problem is non-trivial making it undecidable.
• To prove that the problem is semi-decidable we can simulate TM $M$ on input $\epsilon$ and accepts when $M$ accepts $\epsilon.$ This will work and outputs correctly whenever $M$ halts on $\epsilon.$

Answer 2

yes Turing machine can accept null string

Say we can think turing machine as a computer , then it accepts every string and even NULL string. Then it is Recursive

If it accepts only NULL string and no other string , then it will be Recursive Enumerable but not recursive.

We can represent NULL string only with

Example X={M| L(M)={}}

Complement of X i.e. X' which accepts all string other string

Comments

When we talk about decidability then what exacty do we refer by that  .I mean if something Is given like is it decidable ..then what exactly we are looking for in question to get the answer .......if you did not understand what am i asking just comment ..I think i have made my point clear what i am asking.

---

in decidability we have to check yes and no condition rt?

---

I have read it somewhere that it is not decidable .now I m confused  either you are right or that other one.

Answer 3

Explanantion of such problem is not so simple .Always remember that emptiness problem in turing machine undecidable almost all problem related to turing machine and restricted grammar always undecidable .It is very important to keep into mind.