Let $A$ be the language $\{\langle M\rangle\mid M\text{ is a Turing machine that accepts only one string}\}$

According to my understanding, if a Turing machine is able to decide if another Turing machine will accept only one string, then the halting problem could also be solved. Therefore, $A$ is non-recursively enumerable in my understanding. Is it correct ?

  • $\begingroup$ Do you mean non-recursive, rather than non-recursively enumerable? $A$ is certainly recursively enumerable - simply pick an ordering on the strings over the alphabet (say lexicographic) and try them one by one in order. If there is some string that $M$ accepts, you will eventually find it. If there is none, then we don't actually care as we're only aiming for recursively enumerable. $\endgroup$ – Luke Mathieson Jan 10 '13 at 2:27
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. We have migrated your question to Computer Science which has a broader scope. $\endgroup$ – Kaveh Jan 10 '13 at 2:46
  • $\begingroup$ Just to be more precise with my earlier comment, you can't precisely test each string one by one, you have dovetail the executions of each string to make it work. $\endgroup$ – Luke Mathieson Jan 10 '13 at 3:47
  • $\begingroup$ @Luke Mathieson, that will never guarantee you that $M$ only accepts one string - it would take solving the halting problem for $M$ to be sure it never accepts some other one. $\endgroup$ – Steven Stadnicki Jan 10 '13 at 4:14
  • $\begingroup$ @StevenStadnicki, you're right, ignore what I said! $\endgroup$ – Luke Mathieson Jan 10 '13 at 4:49

As the question suggests, it is not too hard to show a reduction from the halting problem (HP) to the language $A$ stated in the question, $HP \le A$. This means that $A$ is undecidable, $A\notin R$ (also, it is not in co$RE$). But, is it in $RE$ or not?

Lets show that $\overline{HP} \le A$ and conclude that $A\notin RE$.

The reduction goes like that: on input $(\langle M\rangle,x)$ we generate the TM $M_x$ that, on input $w$:

  1. If $w$=$\varepsilon$, ACCEPT.
  2. Run $M$ on $x$. If M halts, ACCEPT (otherwise, we're in a loop anyways)

The reduction is valid: if $(\langle M\rangle,x) \in \overline{HP}$, then $M$ does not halt on $x$. This means that $M_x$ accepts only the empty string (and loops on any other input). Thus $\langle M_x\rangle \in A$.
On the other hand, if $(\langle M\rangle,x) \notin \overline{HP}$, then $M$ halts on $x$, and $M_x$ accepts any input, thus $\langle M_x\rangle \notin A$.

It is easy to verify that the reduction is computable and complete.

| cite | improve this answer | |
  • $\begingroup$ You should explain what $HP$ and $L$ are. In fact, you should rename $L$ to $A$ because that is what the question called it. $\endgroup$ – Andrej Bauer Jan 10 '13 at 7:29
  • $\begingroup$ @AndrejBauer Oh, thanks, I missed that. Fixed. $\endgroup$ – Ran G. Jan 10 '13 at 7:35

I thought up a reduction on the train home, but Ran G. has beaten me to the punch ;). Nonetheless, as an exercise:

Let $E_{TM} = \{\langle M\rangle\mid L(M) = \emptyset\}$ (as usual). This language in not recursively enumerable (in fact you have asked another question where this is demonstrated.

We can show that if $A$ is recursively enumerable, then $E_{TM}$ is also. Let $R$ be a Turing Machine that recognises $A$ (if $A$ is recursively enumerable, then it is Turing recognisable and such a machine exists). Using it we can construct a machine $T$ that recognises $E_{TM}$ as follows:

On input $\langle M\rangle$:

  1. Pick two strings $w$ and $x$ where $w\neq x$.
  2. Construct two machines $M_{w}$ and $M_{x}$ where each have a new branch from the start state that accepts $w$ and $x$ respectively.
  3. Step for step run $R$ on inputs $\langle M_{w} \rangle$ and $\langle M_{x}\rangle$
    • If R accepts on both, halt and accept.

Now we argue that $T$ recognises $E_{TM}$. If $L(M) = \emptyset$, then $M_{w}$ and $M_{x}$ accept only $w$ and $x$ respectively, thus $R$ will accept on both. If $R$ accepts on both $\langle M_{w}\rangle$ and $\langle M_{x}\rangle$, then $M$ cannot have accepted on any string:

  • If $w \in L(M)$, then $\langle M_{x}\rangle \notin A$, and hence $R$ would not accept.
  • If $x \in L(M)$, then $\langle M_{w}\rangle \notin A$, and hence $R$ would not accept.
  • If $y \in L(M)$ where $y \neq w,x$, then $R$ would accept neither $\langle M_{w}\rangle$ nor$\langle M_{x}\rangle$.

Therefore $R$ cannot exist as it contradicts the non-recursive enumerability of $E_{TM}$, and hence $A$ is also not recursively enumerable.

| cite | improve this answer | |

Your Answer

