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)
Enumerate All Possible Strings Over Alphabet
algorithms;strings;enumeration
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.