0
$\begingroup$

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

What does it mean by enumerator enumerating in decreasing order? I am so confused about this concept. Can you prove the above theorem? Please help me.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ You cannot prove a statement without firs understanding what it means. $\endgroup$
    – Yuval Filmus
    Mar 14, 2021 at 13:40
  • 1
    $\begingroup$ If you're not sure what an exercise is asking you to do, you should contact whoever set you the exercise. $\endgroup$
    – Yuval Filmus
    Mar 14, 2021 at 13:40
  • $\begingroup$ The textbook does not talk about what it means by enumerator in increasing/decreasing order. It just says enumerator is what a TM for a language prints out, and it is Turing-recognizable iff enumerator enumerates in increasing order. I am so confused about what it means by enumerating in increasing/decreasing order. $\endgroup$
    – user133085
    Mar 14, 2021 at 13:53
  • 2
    $\begingroup$ It's up to the textbook to explain what it means by decreasing order. I certainly have no idea. If there is no explanation of this term, I suggest ignoring this exercise. $\endgroup$
    – Yuval Filmus
    Mar 14, 2021 at 13:54
  • 1
    $\begingroup$ Similar question asked recently as cs.stackexchange.com/questions/136535/… $\endgroup$
    – Pål GD
    Mar 14, 2021 at 16:51

0

Reset to default

Browse other questions tagged or ask your own question.