Reducing a problem to Halt

Question

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?

Answer 1

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} $$

Answer 2

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.

or

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.