[Solved]: Reducing a problem to Halt

Problem Detail: 

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?

Asked By : Eric

Answered By : A.Schulz

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7215