turing machine

Question

Does turing machine accepts epsilon?

Comments

write epsilon on tape

---

http://math.stackexchange.com/questions/668896/what-does-it-mean-for-a-turing-machine-m-to-accept-epsilon   See this

Answer 1

Suppose the answer is "no"

1. Decidability of whether a TM accepts empty string becomes trivial - but this is an undecidable problem
2. Set of all recursively enumerable language will never be a superset of set of all context-sensitive languages or context-free languages or not even regular languages as all these can include empty string.

So the answer is "yes". A TM accepts empty string when it can go to an accept state on "B" (blank symbol) on input tape or if the initial state is an accepting state (similar to finite automata).

Comments

sir but in TM all are blank symbols how do we set delimeter means how do  we know that it is our string starting... it will move forever as it is infinite and not bounded.. so how can we say that it accept epsilon???

---

Plz tell is it RE or non-RE?

https://gateoverflow.in/283972/self-doubt

---

@Arjun sir here Rice's theorem will not be applicable right?

Answer 2

Turing Machine can accept Epsilon? No

Because when we telling turing machine accept epsilon, that means yes cases of TM is accepts nothing.

Means u can simply ask this question "Is TM accepts nothing?"

We can only check that if TM accepts a finite or infinite language . But how can we say if there is nothing as a string, then still TM accepts it. It can never be decided. So, TM accepts epsilon is undecidable or not even Recursive Enumerable.

Comments

i wrote this

but then it doesn't mean , It's decidable to know whether a TM accepts ∊  or not...it's Undecidable problem even.

read carefully srestha , i said if some TM accepts epsilon then we can't generalize it like 'every TM will accept too, and even accepting epsilon is UD , i explicitly said this.

---

Besides these.

Another way of proving that Turing machine accepts empty string or not is by Rice Theorem:-

According to rice theorem for every non trivial property if there exist a turing machine which say no and there exist another turing machine which say yes then thr given problem is UD.

So for the given problem we can design single state turing machine with transition  {B, B, L|R} to aanother state which dont have any transition this will say yes. And another TM M in which we have two states Q1 and Q2 trans from Q1 to Q2 is {a/b, X, R} this Tm will say no.

Thus, as per Rice’s theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable.

So the given problem is UD.

if you feel wrong any thing in this comment then please let me know because I am new to this Rice theorem.

---

@Shubhanshu u r right brother as the property is non trivial (as not obeyed by every turing machine ) the language which consists of the encodings of turing machines which accept epsilon is not RE or RE and the problem is undecidable.