The problem that I'm struggling is as follows:

Explain why the union and intersection of two effectively enumerable sets is again effectively enumerable.

I thought this is easy problem, but on the second thought, I found that it is kind of hard to prove because of the vaguness of effectiveness... Can anyone help on this problem?

  • $\begingroup$ It's pretty simple: evaluate both functions on the input, and then ... $\endgroup$ Jan 15, 2021 at 2:36
  • $\begingroup$ @DonThousand You mean evaluate both functions at the same time in parallel? Isn't it absurd in terms of algorithm? $\endgroup$
    – kkkk
    Jan 15, 2021 at 2:42
  • $\begingroup$ Not in parallel, one after another. They both terminate in a finite amount of time, so you'll get done eventually. $\endgroup$ Jan 15, 2021 at 2:42
  • $\begingroup$ @DonThousand Ok, that works fine for the intersection only (thank you), because for the union, if one doesn't finish at all, when would the other start, since it might be the case that only the latter one could end in a finite amount of time? $\endgroup$
    – kkkk
    Jan 15, 2021 at 2:45
  • $\begingroup$ What is an "effectively enumerable" set? Is it related somehow to recursively enumerable? Stronger? Weaker? $\endgroup$
    – bof
    Jan 15, 2021 at 7:36


You must log in to answer this question.

Browse other questions tagged .