11
$\begingroup$

Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$
Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$?

It seems that the same technique used to show that $\{A \mid A \text{ is a DFA and } L(A)=\emptyset\}$ should work here as well.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? For example, can you think of a DFA for the empty language? Remember that DFAs can be thought of as very limited TMs. $\endgroup$ – Shaull Mar 29 '13 at 16:34
  • 1
    $\begingroup$ Sure. From the start state, move into the "halt reject" state, regardless of what's on the input tape. This explicitly accepts every string in the language and rejects every string not in the language. $\endgroup$ – Patrick87 Mar 29 '13 at 17:05
  • 8
    $\begingroup$ @mahdisaeedi: The latter is an entirely different question! You are asking if it is decidable to decide whether a given TM recognizes the empty language - and the answer is no, see Rice's Theorem $\endgroup$ – Shaull Mar 29 '13 at 17:11
9
$\begingroup$

By marking, you probably mean reachability analysis - looking for a path from the initial state to an accepting state. Indeed, the language of a DFA is empty iff there is no such path.

Let's start with an example as to why this fails in TMs. Consider a TM that, in $q_0$, ignores it's input, but writes $a$ on it's tape, moves the head right and goes to state $q_1$, then in $q_1$ it again ignores the input, writes $a$, moves the head left and goes to $q_2$. In $q_2$, if it reads $a$, then it writes $a$, moves the head right and goes back to $q_1$.

That is, the machine just writes $a$ and alternates between two states ($q_1$ and $q_2$) and always has two adjacent $a$'s on the tape.

We now add a transition from $q_2$ that when reading $b$ goes to an accepting state and halts.

The language of this machine is empty. Indeed, the run always gets stuck in the $q_1-q_2$ loop, and will never get to the accepting state. Yet, there is a state-path to an accepting state. So what went wrong?

Well, intuitively, the ``state'' of a TM is not informative enough to describe the continuation of the run. In order to have all the information, you need the configuration of the TM, which includes the state, the position of the head, and the contents of the tape. If you find a configuration-path (which is called a run) to an accepting configuration, then indeed the language is non-empty, and it is an iff condition.

The problem with using reachability analysis on the configuration graph, is that it may be infinite. This is why deciding language emptiness is undecidable.

This is also why language non-emptiness is recognizable - you can perform a BFS on the infinite configuration graph. If there is a path to an accepting state, you will find it eventually. If there isn't, however, then you may get stuck in an infinite search.

$\endgroup$
  • $\begingroup$ The transition function of a TM is like this : F(QT)->(QT*{L,R}). Could you write the function for ignoring the input? $\endgroup$ – msn Mar 30 '13 at 12:18
  • $\begingroup$ Yes. In this case, $F(q_0,a)=F(q_0,b)=(q_1,a,R)$, $F(q_1,a)=F(q_1,b)=(q_2,a,L)$, $F(q_2,a)=(q_1,a,R)$, and $F(q_2,b)=(q_{acc},a,L)$ (but the latter is never reached). $\endgroup$ – Shaull Mar 30 '13 at 12:20
9
$\begingroup$

$A$ is undecidable because of Rice's Theorem, which states that non trivial properties of partial functions are not decidable.

  1. There is a TM which doesn't accept any string. (Which directly goes to the reject state).
  2. There is a TM which accepts every string. (Which directly goes to the accept state).

This means that the functions computed by elements of $A$ have a non trivial property. Hence $A$ is not decidable.

$E$ is decidable only under the assumption that DFAs are encoded in a special way like state transition table or etc. (we cannot decide whether a TM only accepts regular languages, because of Rice's Theorem!). In this case Rice's Theorem is not applicable because the particular encoding of an element is required to decide on $E$. So we don't just decide on partial functions.

(That is to say if the problem were, deciding whether a particular TM is a DFA -- or DFA computable -- and the language accepted by it is empty, $E$ would be undecidable through Rice's Theorem. Notice that in this case $A = E$.)

$\endgroup$
6
$\begingroup$

Another hint: Try reducing the halting problem to $L_\emptyset$.

(The original hint is to use Rice's theorem, but in this case a direct proof is also pretty simple.)

$\endgroup$
  • $\begingroup$ @Yuval_Filmus Is it correct to say that this language is not even Turing recognizable ? $\endgroup$ – sashas Oct 28 '15 at 20:33
  • 1
    $\begingroup$ What do you think? Can you prove your claim? If so, there is no need to ask the question. $\endgroup$ – Yuval Filmus Oct 28 '15 at 21:58
1
$\begingroup$

Lemma 1: If L is undecidable then so is the complement of L.

We know that the halting problem, $H_{TM}$ is undecidable. Therefore, according to Lemma 1 complement of halting problem, $H_{TM}^c$ too is undecidable.

$H_{TM}$ = $ \{\langle M, x \rangle { }\mid \text{ M is a TM and M halts on input x } \} $

$H_{TM}^c$ = $ \{\langle M, x \rangle { }\mid \text{ M is a TM and M loops on input x } \} $

$E_{TM}$ = $ \{\langle M \rangle { }\mid \text{ M is a TM and L(M) = } \emptyset \} $

Assume that $E_{TM}$ is decidable. We will reduce $H_{TM}^c$ to $E_{TM}$ – in other words we will show how to construct a Turing Machine $M_{H_{TM}^c}$ that decides $H_{TM}^c$ using the TM, $M_{E_{TM}}$ that decides $E_{TM}$. This gives us a contradiction, because we know that $H_{TM}^c$ is undecidable, and so $M_{H_{TM}^c}$ cannot exist. The word “reduce” simply means solving a given problem by converting it into another problem which we already know to solve. So, the Turing Machine for $H_{TM}^c$ can be constructed as follows:

$M_{H_{TM}^c}$ = “on input $\langle M,x \rangle$

$\qquad$ 1. Construct the code for a TM, $M_1$ that does the following:

$\qquad$ $\quad$ $M_1$ = "on input $w$

$\qquad$ $\quad$ 1. Simulate $M$ on $x$.

$\qquad$ $\quad$ 2. Accept if $M$ halts."

$\qquad$ 2. Run $M_{E_{TM}}$ on $\langle M_1 \rangle$

$\qquad$ 3. Accept if $M_{E_{TM}}$ accepts, reject otherwise."

It is crucial to understand that the TM $M_1$ is never actually simulated – such simulation could go into an infinite loop. All we are doing is constructing the code for $M_1$.

$M_1$ is constructed such that on any input $w$ given to it, it will simulate $M$ with input $x$. $M$ can halt or loop on $x$ and hence there can be two cases:

$\quad$ 1. $M_1$ accepts all inputs $w$ if $M$ halts on $x$. $M_{E_{TM}}$ will reject $M_1$ as $L(M_1) \neq \emptyset$.

$\quad$ 2. If $M$ loops on $x$, $M_1$ will also loop for every input $w$ given to it. Anyway, as $M_{E_{TM}}$ is a $\quad$decider it will reject and halt on input $M_1$ as $L(M_1) = \emptyset$.

$Correctness$: Since $M_{E_{TM}}$ always halts (by our assumption), $M_{H_{TM}^c}$ also always halts. $M_{H_{TM}^c}$ accepts if $M_{E_{TM}}$ accepts, that is if $L(M_1) = \emptyset$ which happens if $M$ loops on $x$.
$M_{H_{TM}^c}$ rejects if $M_{E_{TM}}$ rejects that is $L(M_1) \neq \emptyset$ which happens if $M$ halts on $x$. Thus, $M_{H_{TM}^c}$ decides $H_{TM}^c$ which is a contradiction as $H_{TM}^c$ is undecidable.


$Nb: $

Let R be the reduction from $H_{TM}^c$ to $E_{TM}$.

The reduction gives:

i) $\langle M, x \rangle \in H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \in E_{TM}$

$\qquad$ M loops on input x iff the language recognised by $R(\langle M,x \rangle)$ accepts nothing

ii) $\langle M, x \rangle \notin H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \notin E_{TM}$

$\qquad$ M halts on input x iff the language recognised by $R(\langle M,x \rangle)$ accepts something

$\endgroup$
0
$\begingroup$

Proof by contradicting $A_{TM}= \{\langle M,w\rangle \mid M \text{ is a Turing Machine which accepts w}\}$, (which we know is undecidable).

Assume the existence of $R_{TM}$, a TM that decides $L_\emptyset$

Use can then use $R_{TM}$ in the construction of a TM $S_{TM}$, which is a decider for $A_{TM}$

$S_{TM}=^{definition}$ "On input $\langle M,w\rangle$, where $M$ is the encoding of a TM and $w$ is a string:

  1. Modify $M$, taking into account the input $w$, such that the new $M$ (call it $M_1$) rejects all input which is not equal to $w$, where $w$ is built into its description. If the input is equal to $w$, then $M_{1}$ runs $M$ on $w$ and outputs whatever $M$ outputs.

  2. Run $R_{TM}$ with the input $\langle M_1,w\rangle$

  3. Output the opposite of $R_{TM}$s output."

The assumption that there exists a Turing Machine deicer for $L_\emptyset$, allows us to construct a decider for $A_{TM}$, which is a contradiction.

$\endgroup$
  • $\begingroup$ Isn't the input of $R_{TM}$ a TM (without extra $w$)? How do you run $R_{TM}$ on $\langle M_1,w\rangle$? $\endgroup$ – xskxzr Mar 22 '18 at 8:29
-2
$\begingroup$

E={ | M is a TM and L(M)=Φ}. Is E Turing-recognizable?

E is a language, to accept language E we construct a Turing Machine. Suppose we create a Turing EM for the language E.

EM will be provided as input the encoding of another Turing machines, If that inputted machine M accepts an empty language then it will be a member of language E, else it will be not a member of language.

Suppose we have a Turing Machine M, we need to check if it accepts an empty language. Turing Machine EM have M and strings eps, a, b, aa, bb, ..... EM will check if M can reach a final state for at least on a single input, and if it accepts at least a single input it will be discarded and not included in language E. Now, see a possibility T.M M gets into a loop so M will keep on running and we couldn't decide whether it can accept or can't accept anything. Hence, this given language E is NOT RE.

PS: I think the complement of this given Language E will be RE.

$\endgroup$
  • $\begingroup$ Unfortunately, this intuitive argument doesn't constitute a proof. There could be a different way of deciding E, and this is not ruled out by your argument. $\endgroup$ – Yuval Filmus Aug 21 '17 at 7:09
  • $\begingroup$ yes correct, but the way i explained can someone make understand in layman language. $\endgroup$ – Manu Thakur Aug 21 '17 at 7:56
  • $\begingroup$ This site is not for laypersons. It's for academic-level theoretical computer science. $\endgroup$ – Yuval Filmus Aug 21 '17 at 7:58
  • 2
    $\begingroup$ All you've done is give an intuitive argument about why a particular computational technique seems to fail to solve this problem. But the question is asking for a proof that no possible technique works. $\endgroup$ – David Richerby Aug 21 '17 at 12:45

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.