Problem Detail: I am given the following decision problem: A program $ Pi $ takes as input a pair of strings and outputs either $true$ or $false$. It is guaranteed that $Pi$ terminates on any input. Does there exist a pair ($I_1,I_2$) of strings such that $Pi$ terminates on ($I_1,I_2$) with output value $true$? It is clear that $Pi$ is semi-decidable and to proof this, I am asked to give a semi-decision procedure. However, how do I enumerate all possible pairs strings? Or how do I enumerate all possbile (single) strings in general? Of course, such a program may never terminate, but that is no problem because I am only asking for semi-decidability. EDIT2: Solution (Java)
Asked By : r0f1
Answered By : David Richerby
Consider a string over $Sigma$ to be a number written in base $|Sigma|$ and implement a counter. Remember to include leading “zeroes”: first generate all the length-1 strings, then all the length-2 ones, and so on.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/29841 3.2K people like this
