1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Java code is offtopic here, so I'm removing that part again. If you want to share the code with future visitors, I'd recommend creating a pastbin or gist and link to it in a comment on the answer you implemented. $\endgroup$ – Raphael Sep 11 '14 at 14:03
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Almost OK. If we assume that $\Sigma = \{0,1,\dots, k-1\}$ we first have to prepend a $1$ to the string before reading it as a number, to avoid problems with leading $0$'s. $\endgroup$ – Hendrik Jan Sep 11 '14 at 12:02
  • $\begingroup$ Thank you for the clearification. However, if you append a $1$ at the beginning, you might want to avoid the resulting duplicates. I wrote a Java program, based on your answers. Thanks :) $\endgroup$ – r0f1 Sep 11 '14 at 12:52
2
$\begingroup$

The principle of the counter implementation suggested by David Richerby's answer to enumerate the integers is very simple and nice. However I would amend it differently to answer Hendrik Jan's comment regarding leading zeros.

One way is to enumerate all positive integers in base $|\Sigma|$, using $\Sigma$ as an ordered set of digits, which we assume for simplicity to begin with $0$ and $1$. However, one must ignore all integers numbers that do not begin by the digit $1$ on the left, and for the numbers that are kept, one must remove the leading $1$ on the left. So, for example,$"100617"$ becomes $"00617"$. This will take care of including strings with leading $0$'s. It will also take care of including the empty string in the enumeration, since $"1"$ becomes the empty string $""$.

Alternatively, to avoid generating numbers that are skipped, you can more directly change the successor function of the counter. You make it work as usual, except when the number is of the form $1\,z^n$ for $n\geq 0$, in which case the next number is $1\,0^{n+1}$, assuming the last symbol is $z$ in $\Sigma$ used as an ordered set of digits. For example $successor("1zzz")="10000"$. Thus all the numbers enumerated begin with a $1$, which you remove, so that it becomes an enumeration of all strings, including the empty string.

Then, when you get a string of size n, cut it in two substrings in the n+1 ways possible (since the empty string is also a string), and that will give you an enumeration of pairs of strings.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, I did not have that last part, for the pairs of strings. I thought it was way more complicated. I updated my post and linked to my solution. $\endgroup$ – r0f1 Sep 11 '14 at 21:10
  • $\begingroup$ @r0f1 There are other standard techniques to enumerate pairs. But in this case, this seemed a lot cheaper. I cannot read Java, and I do not understand precisely the answer you accepted. What does your program do. Can you give a sample output, say the first fifty strings over a 3 symbols alphabet. $\endgroup$ – babou Sep 11 '14 at 21:49
  • $\begingroup$ Sure, there you go: pastebin.com/Ggep4PJ6 $\endgroup$ – r0f1 Sep 12 '14 at 8:57
  • $\begingroup$ @r0f1 Thanks. It seems your enumeration of strings misses the empty string. Your first result should be <, >, 2, 1 (with your current setting). But I do not understand your relation between counter and counter base 3, as they are off by 1. For example $10_3=3_{10}$, not $4_{10}$. I also wonder how your counter works: what value does it start from, and how does it jump, for example, from 6 to 10 in the decimal version? Do you compute the incrementation in base 3 or in base 10 (or rather just in the binary format of the computer)? $\endgroup$ – babou Sep 12 '14 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.