Language comprising of Turing machine encodings

Question

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 ?

Answer 1

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.

Answer 2

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.