0
$\begingroup$

We suppose that the sets $S_1$ and $S_2$ are constructible enumerable, that means that there is an algorithm that enumerates them. Show that the sets $S_1 \cup S_2$ and $S_1 \times S_2$ are also constructible enumerable.

To show this do we have to construct a Turing machine for the union and one for the cartesian product?

$\endgroup$
  • $\begingroup$ Yes, a Turing Machine which enumerates the union and an other one which enumerate all the pairs. But you can also think with an higher abstraction level. $\endgroup$ – François Jun 25 '15 at 20:26
  • $\begingroup$ You can generate an infinite output stream which enumerates the elements of a set, using infinite input streams of sets that you already know enumerable. This allow you to use pseudo-code rather than Turing Machines. $\endgroup$ – François Jun 25 '15 at 20:42
  • $\begingroup$ You can also write a semi-algorithm (always finishes when output is true) which recognizes the target set using semi-algorithms for other problems already known r.e. $\endgroup$ – François Jun 25 '15 at 21:33
1
$\begingroup$

Hints:

  1. For $S_1 \cup S_2$, use the same idea in the proof that the natural numbers and the integers have the same cardinality. The proof goes by listing the integers in sequence: $$ 0,1,-1,2,-2,3,-3,\ldots $$ You can think of $S_1$ as $0,1,2,3,\ldots$ and of $S_2$ as $-1,-2,-3,\ldots$.

  2. For $S_1 \times S_2$, use the same idea in the proof that the natural numbers and the positive rationals have the same cardinality. The proof uses the "diagonal method", and consists of listing the rationals sorted by the maximum of the numerator and the denominator: $$ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{2}{2}, \frac{1}{3}, \frac{2}{3}, \frac{3}{1}, \frac{3}{2}, \frac{3}{3}, \ldots $$ In this case $S_1=S_2$ are both $1,2,3,\ldots$.

$\endgroup$
  • $\begingroup$ Nice hint but the question wasn't about the enumerators themselves, but about their type (TM or not ?) ! $\endgroup$ – François Jun 25 '15 at 21:21
  • $\begingroup$ @FrançoisGodi Yes, I realize that. Fortunately, the proofs of the results I mention are effective, i.e., they result in an algorithm for solving the exact problems which the OP is after. $\endgroup$ – Yuval Filmus Jun 25 '15 at 21:24
  • $\begingroup$ Could you explain to me further how we enumerate the cartesian product? I haven't really understood it... @YuvalFilmus $\endgroup$ – Mary Star Jun 28 '15 at 11:59
  • $\begingroup$ You'll have to keep thinking... $\endgroup$ – Yuval Filmus Jun 28 '15 at 14:01
1
$\begingroup$

One way to show that a set is enumerable, is to provide a TM that enumerates all the words in that set. (that what the comments are trying to say, and probably what you are asking)

A second way is to show a bijection to another enumerable set of the same cardinality (like the natural numbers or like $S_1$ or $S_2$ themselves, in case they are infinite.) This is what Yuval was trying to hint.

Choose your way, both are correct.

$\endgroup$
  • $\begingroup$ I will try using the first way: $S_1$ is enumerable so there are the TM $M_1=(F_1, \Sigma , \delta_1 , s_1 , H_1)$ and $M_2=(F_2, \Sigma , \delta_2 , s_2 , H_2)$ that enumerate all the words in the sets $S_1$ and $S_2$ respectively. We construct a TM $M_u=(F_u, \Sigma, \delta_u, s_u, H_u)$ that enumerates all the words in the set $S_1 \cup S_2$, where $F_u=F_1 \cup F_2$, $s_u=s_1$, $H_u=H_1 \cup H_2$. But how will the transition function $\delta_u$ look like?? $\endgroup$ – Mary Star Jun 25 '15 at 23:10
  • $\begingroup$ Or didn't you mean to provide a TM in that way?? $\endgroup$ – Mary Star Jun 25 '15 at 23:16
  • $\begingroup$ @MaryStar right, it is not immediate. You need to run them "in parallel". Just think how to "interleave" the two machines: one word from $M_1$ then one word from $M_2$, then another from $M_1$, etc... $\endgroup$ – Ran G. Jun 25 '15 at 23:19
  • $\begingroup$ So, do we have to describe the TM $M_u$ in words?? Does the TM $M_u$ looks as followed?? When we start with a word of $M_1$ we have at the even numbered tape squares of $M$ words of the $M_2$ and at the odd numbered tape squares words of $M_1$. Is this correct?? $\endgroup$ – Mary Star Jun 25 '15 at 23:39
  • $\begingroup$ Then Alice asked: "do we have to describe the TM $M_u$ in words"?, and the the Cheshire cat answered "Where do you want to go?". I don't care if you describe it by words, or give the full $\delta_u$; both are doable and correct in my eyes; this depends on your goals. About the tapes: for me it would be most convenient to use multiple tapes: two for $M_1$ (work/output), two for $M_2$, and one for the output of the combined enumerator. $\endgroup$ – Ran G. Jun 25 '15 at 23:48

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.