$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff

  1. If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$ is recursively enumerable, then $L'$ is in $S$
  2. If $L$ is an infinite language in $S$, then there exists at least one finite subset of $L$ that is in $S$
  3. The set of all finite languages in $S$ is enumerable, i.e. a Turing machine can list all the finite languages in $S$

Source of the statement: https://cs.stackexchange.com/q/2322 and some online notes

Isn't the 3rd one contradictory to the 1st one?

  • $\begingroup$ No. For example, the 'full' class $S$ of all r.e. languages over a given symbol set satisfies the three properties. $\endgroup$ – realdonaldtrump Nov 6 '18 at 17:30
  • $\begingroup$ @realdonaldtrump what about the 3rd property? In your eg applying 3rd, we get $RE_{finite}$ a r.e set ($RE_{finite}=\{L|L$ is finite(obviously r.e)$\}$). So $RE_{finite}$ should also satisfy the 1st property, hence it contain an infinite language, which a contradiction. $\endgroup$ – Saravanan Nov 6 '18 at 19:30
  • $\begingroup$ No. In this case $RE_{finite}$ should be an element of $S$. This doesn't mean $RE_{finite}$ can take the place of $S$ in condition 1. It $\it could$, however, be used as one of the $L$s. $\endgroup$ – realdonaldtrump Nov 6 '18 at 19:56
  • $\begingroup$ @realdonaldtrump NO. $RE_{finite}$ is r.e and its also a subset of class of all recursively enumerable languages, so it should satisfy the three conditions $\endgroup$ – Saravanan Nov 6 '18 at 20:02
  • $\begingroup$ Oh, I see what you mean. There is some conflict between this new definition of a set $S$ of languages being "r.e.", and the existing definition of a language $L$ being "enumerable" in the sense of 1 and 3, in cases such as $RE_{finite}$, which can be viewed as either type. OK. But they aren't the same, and whoever wrote this tried to emphasize this the way (s)he wrote point 3. (A much better choice would have been to give the new definition a new name.) $\endgroup$ – realdonaldtrump Nov 6 '18 at 21:40

Your Answer

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

Browse other questions tagged or ask your own question.