3
$\begingroup$

Consider the following question: Example of R and G when $R \subseteq L(G)$ is undecidable

Is this question on-topic for cstheory? On one hand, it has been already answered on MSE and I was able to find an answer by googling "deciding if a regular language is a subset of a context-free language", while having a typical CS familiarity with the area (i.e. I am not an expert). On the other hand, asking for a specific example as well as a question that I think is not 100% straightforward to answer, so it could be useful as a reference-request question.

I noticed there are some similar questions in the meta, but nothing that IMHO is a suitable fit, especially this one. Any thoughts?

$\endgroup$
2
  • $\begingroup$ Maybe we could use the blog for that or make a community wiki? $\endgroup$
    – Joshua Herman
    Commented Aug 12, 2015 at 0:33
  • $\begingroup$ from answers, there seems to be more than one way to interpret it, either undergrad or more complex. note SE does encourage answers that "rescue" nearly-off-topic questions with definitive answers. and in general, think its not worth worrying about individual questions much (as SE mgt says in semifamous blog they are like "grains of sand") unless there is something tricky/ notable about them eg substantial split votes, unreasonable high votes, etc $\endgroup$
    – vzn
    Commented Aug 18, 2015 at 21:28

2 Answers 2

Reset to default
8
$\begingroup$

If you legitimately couldn't find the answer to this question after a search, it then may be on topic as a reference request. But if you did a google search and found the references you mention, then you shouldn't ask the question here.

Also, to note, we aren't trying to build a community reference of all possible interesting questions, but rather be a legitimate Q&A site (which will also happen to be a useful reference for the community).

$\endgroup$
3
$\begingroup$

Personally I voted to close not because it was answered somewhere (MSE in this case) but because it is at the level of typical undergrad course exercises. A good undergrad who has taken computability should be able to answer it.

ps: I understand the question as similar to asking if there is a fixed TM whose halting is not computably decidable. It is clear to me the author is not asking about the general case where R/G are part of the input (that would be an OK question). I also think interpreting it as being about logical independence does not follow from the question and seems too far. This is a trivial question and people are trying (too hard imho) to interpret it more interestingly.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .