Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm reviewing for a computability test, and my professor has not provided solutions to his practice questions. I came up with a "solution" to this problem, but it really seems like my answer is wrong (since I call upon $\mathsf{Halt}$ twice)...

We are given this initial language for some machine $M$:

$\mathsf{2Strings} = \left\{ \left<M\right>\ |\ L(M)\text{ contains at least 2 distinct strings }\land M\text{ is a }TM \right\}$

And we are told to "[s]how that [the language] is recursive-enumerable." The problem title is Reduction, so I assume we are supposed to use that.

My solution is as follows:

  1. Pass $\left<M\right>$ to the following reduction:
  2. Create $w_1 \in L(M), w_2 \in L(M)$, so that $w_1 \not= w_2$, and let $M' = M$.
  3. Pass $\left<M', w_1\right>$ to $\mathsf{Halt}$. If the answer is Yes, proceed to step 4. Otherwise, return No.
  4. Pass $\left<M', w_2\right>$ to $\mathsf{Halt}$. If the answer is Yes, return Yes. Otherwise, return No.

Basically, this is my logic: We pass each of two distinct strings from $L(M)$ to $\mathsf{Halt}$ separately; if either one says No, our answer is No. If both say Yes, the answer is Yes.

Is my answer valid? More importantly, is it correct? If not, what should I do to fix it?

share|cite|improve this question
up vote 5 down vote accepted

First of all I find it rather artificial to argue with reductions, since a more direct argument is applicable here. However, you can of course do it.

I think your approach follows basically the right direction. But it is not a clean reduction. Here is how I would phrase it.

We want to show that ${\sf 2Strings}$ is recognizable by showing ${\sf 2Strings}\le_m {\sf Halt}$. The reduction goes as follows: Assume we have a TM $M$ and based om $M$ we define a different TM $M'$. Let us first define a NTM $N$:

 0. Delete the input
 1. Guess two words u and w
 2. If u=w cycle
 3. Simulate u on M
 4. Simulate w on M
 5. Accept if both simulation accepted, otherwise cycle

Now let $M'$ be the deterministic version of $N$. The reduction maps $\langle M \rangle $ to $\langle M',\varepsilon \rangle$. By construction, $$ \begin{align} \langle M \rangle \in {\sf 2String} & \iff N \text{ accepts every input}\\ & \iff M' \text{stops on every input}\\ & \iff M' \text{stops on }\varepsilon \\ & \iff \langle M',\varepsilon\rangle \in {\sf Halt} \\ \end{align} $$

share|cite|improve this answer
This is a far better way to put it, thanks! I feel like I was missing two key points: performing cycles (upon failure), and putting $\epsilon$ into $\mathsf{Halt}$. This is perfect, thanks! – Eric Dec 6 '12 at 21:30

You don't need to give a reduction to show that the language is r.e., you can simply give an algorithm that will recognize the language.

Given $\langle M \rangle$:
0. Check if $M$ is a TM, if it is not reject,
1. Run $M$ in parallel on all strings using dove-tailing,
2. As soon as two branches halt and accept, halt and accept.


Given $\langle M \rangle$:
1. Check if $M$ is a TM, if it is not reject,
2. Guess two strings $u\neq v$,
3. Run $M$ on $u$ and $v$,
4. If both halt and accept, halt and accept.

A reduction to $Halt$ proves more than the language being r.e., it proves that the complement of the language is not r.e., if the question was asking for that then you would need to give a reduction.

share|cite|improve this answer

Your Answer


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.