1
$\begingroup$

$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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It's also possible that the intended meaning of "$(L(M) \text{ is }\epsilon$" is "$L(M)=\{\epsilon\}$" (i.e., the empty string is the only string accepted by the machine). $\endgroup$ – David Richerby Jan 26 '19 at 13:26
  • $\begingroup$ @DavidRicherby the initial wording of the question had "$L(M)$ accepts $\epsilon$" - I probably should've made that first remark as a comment on the question instead of part of the answer $\endgroup$ – roctothorpe Jan 28 '19 at 21:29
  • $\begingroup$ @roctothorpe What is the name of this TM? I think it is a famous one? (I am asking so I can enter the name in the question so that it will be easier for future people that are searching for this) $\endgroup$ – Tomer Jan 16 at 11:14
  • $\begingroup$ @Tomer I don't know that this particular TM has a special name. This general pattern of using self-reference to show that languages are undecidable is common, though the resulting TM will have different behavior based on the language. $\endgroup$ – roctothorpe Jan 22 at 22:29
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It's true that Rice's theorem can be used to prove that the language is undecidable, though your explanation of what Rice's theorem is and how it can be used is very vague, to the extent that it can't really be said to be correct. $\endgroup$ – David Richerby Jan 26 '19 at 13:29
  • $\begingroup$ @DavidRicherby I just tried to elaborate in Layman terms the non trivial property. Even one example is sufficient right? $\endgroup$ – Tushar Patil Jan 28 '19 at 2:06
-1
$\begingroup$

$M$ may be doing computations regardless of the input, rather then checking then first checking it and secondly compute things accordingly

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.