1
$\begingroup$

Show that a language is decidable iff some enumerator enumerates the language in decreasing order.

I know a language is decidable iff some enumerator enumerates the language in the standard string order (increasing order), but I am not sure if this makes sense in decreasing order. I carefully think if some enumerator enumerates the language in decreasing order, then a language is not decidable. For infinite languages, we cannot assure which comes first in the enumerator. However, are all finite languages decidable? If so, I think the given statement is true for finite languages.

$\endgroup$
3
  • $\begingroup$ Where did you encounter this task? $\endgroup$
    – D.W.
    Mar 12 at 19:25
  • $\begingroup$ What does it mean by enumerator in decreasing order? Enumerator does not have input, so I guess it does not mean that enumerator produces the reversal of input as output. I am so confused about this concept. $\endgroup$
    – user133085
    Mar 14 at 13:23
  • $\begingroup$ I faced a task similar to the above from the textbook, "Introduction to the theory of computation_third edition - Michael Sipser." The task is "Show that a language is decidable iff some enumerator enumerates the language in the standard string order." I got to wonder what about the case of enumerator in decreasing order $\endgroup$
    – Juns
    Mar 14 at 14:43
3
$\begingroup$

If there is an enumerator in decreasing order then the language is finite and hence decidable.

But that means any infinite language wont have such an enumerator, and in particular there is some infinite language that is decidable (such as $\Sigma^*$) and it wont have such an enumerator.

So, this theorem is incorrect

$\endgroup$
5
  • $\begingroup$ Then, if a language is decidable then some enumerator enumerates the language in decreasing order? Of course that we can say for sure it is if the language is finite but if it is infinite, I think there is no possible enumerator for that language because we never know what comes the first string in the enumeration in decreasing if lanague is infinite. $\endgroup$
    – Juns
    Mar 14 at 15:37
  • $\begingroup$ No, what I said is that if a language is infinite, there is no enumerator that enumerates in decreasing order. It doesn't matter if its decidable or not. $\endgroup$
    – nir shahar
    Mar 14 at 15:50
  • $\begingroup$ And there is a decidable infinite language, hence there is a decidable language without an enumerator. @Juns read again my answer. It contains the explanation... $\endgroup$
    – nir shahar
    Mar 14 at 15:51
  • $\begingroup$ Thank you for your prompt and concise explanation! It helps a lot for me! Lastly, to sum up, if a language is finite, then we say it is decidable and if and only if some enumerator enumerates L in decreasing order. On the other hand, if a language is infinite, no matter what that language is decidable or not, there is no enumerator that enumerates it in decreasing order. Am I correct in understanding? $\endgroup$
    – Juns
    Mar 14 at 16:15
  • 1
    $\begingroup$ You are correct, but notice something even simpler: any finite language is decidable. Also, every finite language has a decreasing enumerator! So, even though the terms are equivalent when talking about finite languages, they are equivalent in some redundant sense, since every finite language is both decidable and has a decreasing enumerator. $\endgroup$
    – nir shahar
    Mar 14 at 17:07
3
$\begingroup$

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 decreasing order? You would start with an existing enumerator that defines some order. And whenever that enumerator generates A followed by B, the enumerator "in decreasing order" will generate B followed by A.

If the set is empty, then "decreasing order" is just an empty enumerator. If the set is non-empty but finite, then "decreasing order" means we enumerate the last element in the original enumerator first, then the element that was enumerated before the last element, until the first element of the original enumerator is generated, and then the enumerator "in decreasing order" stops.

But what if the set is infinite? The new enumerator must generate some set element A first. The original enumerator would generate A followed by some element B. In decreasing order, B would have to precede A, but it can't because there cannot be anything before the first item. For example, you can't generate the primes in descending order.

So if a generator can enumerate a language in reverse order, this means that the language must have been finite in the first place. And every finite language is decidable. Infinite languages cannot be enumerated in reverse order. But that doesn't say anything about being decidable or not.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.