Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
$L = \{ \langle M \rangle \mid \epsilon \in L(M) \}$, where $M$ is any Turing machine.
Why is the above problem undecidable? Can't we just check whether the initial state is a final state and say the TM accepts $\epsilon$ if the initial state is the final state else it doesn't? We can also just check if the TM goes to an accepting state on the blank symbol.
First, a note on notation: $L(M)$ is a language which is a set. Languages don't accept or reject, Turing machines do. You can either say "$\epsilon \in L(M)$" or "$M$ accepts $\epsilon$".
There are many Turing machines in this language that don't meet your description. For example, imagine a machine that upon reading a blank goes and writes, say, 111 and then accepts. The initial state does not need to have a transition to an accept state on a blank symbol in order to belong in this language.
Here's another perspective on why this language is undecidable using Kleene’s Recursion Theorem. Imagine that there is some decider $D$ that, given the description of a TM $\langle M \rangle$, $D$ accepts if $M$ accepts $\epsilon$ and rejects otherwise. Now create a Turing machine with the following behavior:
Get my own description <M> and then run D on <M>.
If D accepts <M>:
If input is empty, reject. Otherwise accept.
Else:
If input is empty, accept. Otherwise reject.
The existence of this decider allows us to create the above Turing machine which is a contradiction. Essentially, if the decider says the Turing machine is supposed to accept the empty string, it then goes and rejects and if it's supposed to reject, it then goes and accepts. This idea of being able to use self-reference and ask "What am I about to do?" and then doing the opposite shows that no single machine can predict behavior of all others.
Consider a TM $M$ that, on input $\epsilon$, computes $3654^{256}$, divides it by two, and then accepts.
Then $\langle M \rangle \in L$, even if $M$ does not get to the accepting state on blank. Before reaching the accept state it does a lot of computation, traversing many states and writing a lot of data on the tape.
As this question is related to recursively enumerable set, we can use Rice's theorem.
Rice's theorem 1. Any non trivial property of Recursively enumerable set is undecidable. Note the word non trivial, so if you can give two sets suppose yes instance and no instance with respect to Recursively enumerable set of TM , then the problem is undecidable. Here yes instance : L = {epsilon} No instance : L = {00,01,10,...} Here instance means property which is asked in your question. Here as we have shown it is a non trivial property. This problem is undecidable.
$M$ may be doing computations regardless of the input, rather then checking then first checking it and secondly compute things accordingly
Consider a turing machine, Take just blank on the input tape, Turing machine could have moves just on blank and could loop infinitely without it being decidable whether it accepted epsilon or not
