How to argue about semi-decidability of a problem?

Question

I have the following problem, and I try to prove that it is semi-decidable, but I have a hard time arguing about it.

I know that if a problem $\mathcal{P}$ is semi-decidable, then we can build a program $\Pi$, such that $\Pi$ takes as input instance $I$ of $\mathcal{P}$, and if we have a positive instance, then $\Pi$ returns true, and on negative instance, $\Pi$ either returns false, or does not terminate.

Now, I tried to write a simple procedure like this:

Then, I tried to argue like this:

We can write a procedure $\Pi'$ that takes as input $(S,n)$, and simulates a run of $\Pi_1$ on $S$, and a run of $\Pi_2$ on $n$. We can show that such procedure $\Pi'$ is a semi-decision procedure, and we can distinguish the following cases:

1. Case 1. Suppose that $(S,n)$ is a positive instance, meaning $\Pi_1$ outputs $I$ on input $S$, and $\Pi_2$ outputs $I$ on input $n$. Then the simulation $\Pi'$ will encounter that $OUT1 = OUT2$, and output return true by its construction.
2. Case 2.1. Suppose that $(S,n)$ is a negative instance and it halts. Then, we have that $\Pi_1$ outputs $I_1$ on input $S$, and $\Pi_2$ outputs $I_2$ on input $n$, such that $I_1 \neq I_2$. Thus, $\Pi'$ does not halt due to its construction.

My problem is that, I cover just two cases, I believe I need one more case, where we have as output false, and terminate. Also, from the definition of semi-decidable program, I believe instead of using the pair $(S,n)$, I need to use the pair $(\Pi_1, \Pi_2)$, which is the actual instance of the problem. But, then how will I choose $S$ and $n$? If someone can help me with those questions, I would be glad.

Answer 1

We know that $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ have the same cardinality, so there exists a bijection $f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$. Let $s_n$ be the $n$-th string in some enumeration, like $s_1=\epsilon, s_2=0, s_3=1, s_4=00, s_5=01,\dotsc$ then consider the following semi-decider, where I leave it to you to fill in the missing parts: $$\begin{align} &\Pi'(\Pi_1, \Pi_2)=\\ &\quad\text{for }n=1,2,3,\dotsc\\ &\quad\quad\text{compute }f(n)=(i,j)\\ &\quad\quad\text{run }\Pi_1(s_i)\\ &\quad\quad\text{run }\Pi_2(j)\\ &\quad\quad\text{... }\\ &\quad\quad\text{... }\\ &\quad\quad\quad\text{return accept} \end{align}$$

There are lots of bijections between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$, here are a few to get you started.

Answer 2

Your solution doesn't make too much sense. What you want is a procedure that takes $\Pi_1,\Pi_2$ as input, not a string $S$ and an integer $n$. Also, in your proof you don't explain what values of $S$ and $n$ you are going to use.

Finally, you are not required to enter an infinite loop - you can always just return false. Think about it from a programmer's perspective - why would you ever enter an infinite loop on purpose? Infinite loops are there only since we can't avoid them in some cases. When we can, we do.

Try to think how you, as a human, would try to solve the problem. You would probably make two lists, one consisting of outputs of $\Pi_1$, the other consisting of outputs of $\Pi_2$, and constantly compare the two lists to see if there is any intersection. Formalize this method and you have answered your question.

Please spend a few hours thinking about this answer before commenting here. If things are still not clear, contact your TA, or read your textbook again, or find another textbook or lecture notes and read them instead.