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$ Jan 10, 2013 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, 2013 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$ Jan 10, 2013 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$ Jan 10, 2013 at 4:14
  • $\begingroup$ @StevenStadnicki, you're right, ignore what I said! $\endgroup$ Jan 10, 2013 at 4:49

2 Answers 2


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.

  • $\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$ Jan 10, 2013 at 7:29
  • $\begingroup$ @AndrejBauer Oh, thanks, I missed that. Fixed. $\endgroup$
    – Ran G.
    Jan 10, 2013 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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