0
$\begingroup$

How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering.

Word length alphabetically means a sorting first after the word length and then after the character ordering $(\epsilon,a,b,aa,ab,ba,bb, ...)$.

Hope somebody can help me like give a hint or an approach.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – adrianN Jun 15 '16 at 15:23
  • $\begingroup$ I said I hope somebody can help that doesn't mean that I want you to solve the task.. ?!?! If I ask something on StackExchange I ALWAYS want to have a hint or an approach. $\endgroup$ – fragant Jun 15 '16 at 15:28
  • 1
    $\begingroup$ Hint: ​ The result is not constructive; you'll have a different decider for each possible number of elements in $A$. ​ ​ ​ ​ $\endgroup$ – user12859 Jun 15 '16 at 16:13
0
$\begingroup$

I'll write $L$ for the language, $\mathscr{A}$ for the alphabet and $\mathscr{A}^*$ for the set of all possible words.

If $L$ is decidable, then it's easy to list the words in $L$ in any order that doesn't depend on $L$, such as length-then-lexicographic order: list all the words in $\mathscr{A}$, and for each word, test whether it's in $L$ and output the word only if it is in $L$.

Conversely, suppose that there is a Turing machine $M$ that lists the words in $A$ in length-then-lexicographic order. By definition, this shows that $L$ is recursively enumerable. How can you go from this to the stronger property that $L$ is decidable?

The idea is that you can turn this into a decision procedure if you know when to stop. That is to stay, to decide whether a word $w$ is in $L$, stop the machine after $s$ steps. $s$ may depend on $w$ — if it doesn't, that means that $L$ can be recognized by a finite-state machine — so I'll write $s(w)$. If $w$ has been listed then $w \in L$ by assumption about the machine $M$, and if $w$ has not been listen then $w \notin L$ by construction of $s(w)$.

Of course, in general, there is no suitable function $s$: if $L$ is recursively enumerable but not decidable, that means that no computable function $s$ exists.

Use the fact that the order is length-then-lexicographic to find a suitable function $s$. There's a subtlety there: the function $s$ itself might not be computable — but it can be expressed in terms of how $M$ runs. The important point is that you can construct a machine $M'$ which runs $M$ for time and decides when to stop based on the output of $M$ and on some extra counter.

$\endgroup$
  • $\begingroup$ The phrase "describe a way to compute it" suggest that we can actually compute it, however we can't. If $L$ is finite then we can wait forever for the next word to appear but at some moment it won't. That means that for finite $L$ we have to "know" the size of the set to conclude the output is finished. Unfortunately we cannot compute that size of $L$, but assuming the size is known we fix the algorithm for the decider. In short: the decider exists, but in cannot be computed (in general). $\endgroup$ – Hendrik Jan Jun 15 '16 at 22:08
  • $\begingroup$ @HendrikJan True, my formulation was inadequate. The decider machine can be computed from $M$, but the number $s$ can't be (it depends on how long $M$ runs to list each word). $\endgroup$ – Gilles 'SO- stop being evil' Jun 15 '16 at 22:13
  • 1
    $\begingroup$ It seems it is a little more complicated. When $L$ is infinite, then we know how to do the decider: we wait until the enumerator shows either $w$ or a string later than $w$, which will always happen. If $L$ is finite then we cannot use that construction. There will be no next word after some point and we cannot conclude we have seen the last one unless the number of elements of $L$ is known. Thus the decider exists, but we only know which one it is when we know the cardinality of $L$. It cannot be computed. $\endgroup$ – Hendrik Jan Jun 16 '16 at 20:13
  • $\begingroup$ @HendrikJan. Very good point. Too bad we can't give more than one upvote. $\endgroup$ – Rick Decker Jun 17 '16 at 15:08
0
$\begingroup$

You know that a language $L$ is decidable if there is a TM, $M$ which when given a word $w$ as input always halts and accepts if $w\in L$ or halts and rejects if $w\notin L$. Here are some hints to get you started.

($\Rightarrow$) This is easy. If $L$ is decidable by a TM $D$, you can make an enumerator TM $E$ by trying all possible inputs in order. For word $w_i$ in that order $E$ will run $M$ on $w_i$ and write $w_i$ if $M$ accepts.

($\Leftarrow$) Suppose you had an enumerator $E$ that lists all $w\in L$ in lexicographic order. Use that to construct a decider $M$ which when given $w$ as input, runs $E$ until it finds $w$ among the enumerated strings or fails to find $w$. Your task is to show that it will always either find $w$ or decides it does not appear on the enumeration in a finite amount of time.

$\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.