World's most popular travel blog for travel bloggers.

How to argue about semi-decidability of a problem?

, , No Comments
Problem Detail: 

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

enter image description here

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:

enter image description here

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.

Asked By : Yunyao
Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback