World's most popular travel blog for travel bloggers.

# [Solved]: How to prove that a language $A$ is decidable?

, ,
Problem Detail:

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.

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.