3
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 ...
2
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.
2
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.
...
2
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 ...
2
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.
1
If you look closely at the proof to show that $L_u$ is not recursive, the autor is using a reduction to $\overline{L_u}$ (which is not RE), not to $L_u$, and explain that a reduction to $L_u$ cannot work since $L_u$ is RE.
Only top voted, non community-wiki answers of a minimum length are eligible
