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:Pass $\left<M\right>$ to the following reduction:Create $w_1 \in L(M), w_2 \in L(M)$, so that $w_1 \not= w_2$, and let $M' = M$.Pass $\left<M', w_1\right>$ to $\mathsf{Halt}$. If the answer is Yes, proceed to step 4. Otherwise, return No.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?
Reducing a problem to Halt
computability;reductions
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 cycleNow 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}$$