Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 ?

share|improve this question
    
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. –  Luke Mathieson Jan 10 '13 at 2:27
    
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. –  Kaveh Jan 10 '13 at 2:46
    
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. –  Luke Mathieson Jan 10 '13 at 3:47
    
@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. –  Steven Stadnicki Jan 10 '13 at 4:14
    
@StevenStadnicki, you're right, ignore what I said! –  Luke Mathieson Jan 10 '13 at 4:49
add comment

migrated from cstheory.stackexchange.com Jan 10 '13 at 2:47

This question came from our site for theoretical computer scientists and researchers in related fields.

2 Answers

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.

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

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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