New answers tagged


The difference here comes from the requirement to halt. An algorithm that returns "true", must always do so in finite time, hence, it will never be able to go through all strings in $\Sigma^*$ and confirm that it is either generated not by both CFGs. However, for the complement problem, the requirement changes drastically: It is enough to show one ...


If you have an algorithm which decides "Does DFA $M$ accept $\Sigma^*$?" you just need to check if the input is a DFA (in whatever reasonable notation you specify), if not, reject; if it is a DFA, apply the above algorithm. This decides your language.


Your task is to prove that the language is decidable. Rice's theorem shows only when a language is not decidable, hence it can't be used. About reduction: for as long as you can reduce this problem to some other decidable problem, its fine. That is, you can show that $L\le_p L'$ for some decidable $L'$ and this would ensure that $L$ is also decidable. ...


If memory serves, Soare's old book Recursively enumerable sets and degrees gives a few examples. Here are a couple off the top of my head (below I fix some standard enumeration $(W_e)_{e\in\mathbb{N}}$ of the r.e. sets): The set of $e$ such that $W_e$ is recursive is $\Sigma^0_3$-complete. The set of $e$ such that $W_e$ is co-infinite (= has infinite ...


An enumerator for a set will start by generating some item, then another item, and so on, in a way that every element of the set will eventually be listed. If the set is empty, then it won't even generate the first item. If the set is non-empty but finite, then it will eventually generate the last item and stop. What does it mean to enumerate a set in ...


Your problem is essentially the same as the question of whether a given string can be generated from a given initial string using a given unrestricted grammar (simple reverse all productions). The latter question is known to be undecidable, since you can simulate the running of a Turing machine using an unrestricted grammar.

Top 50 recent answers are included