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<Mright> | L(M)text{ contains at least 2 distinct strings }land Mtext{ 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<Mright>$ 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_1right>$ to $mathsf{Halt}$. If the answer is Yes, proceed to step 4. Otherwise, return No.
- Pass $left<M’, w_2right>$ 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’,varepsilonrangle in {sf Halt} end{align} $$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7215
