1
$\begingroup$

I am wondering this statement above [the title] is true or not.

Here is what I've already had : non-recursive means undecidable.

I've read this Are all infinite languages undecidable?

which says:

If a Language is undecidable(non-recursive), there must be some strings make the TM fail to halt.SO IT MUST HAVE INFINITE OF THEM WHICH MAKE THE TM FAILS TO HALT.

How could this prove my statement[title]? Can anyone explain it to me a bit more clearly?

Thanks

TM means Turing machine. And too be clear My question is : Does ALL non-recursive languages are Infinite?

$\endgroup$
  • 1
    $\begingroup$ Are you familiar with regular languages? Every finite language is regular. Can you proceed from here? $\endgroup$ – Shaull Nov 20 '13 at 18:23
  • $\begingroup$ sorry, not really sure what's regular language is. $\endgroup$ – geasssos Nov 20 '13 at 18:26
  • $\begingroup$ A regular language is a language that can be recognized by a DFA (deterministic finite automaton). It's not crucial in order to solve your problem, but using it can shorten the proof. $\endgroup$ – Shaull Nov 20 '13 at 18:28
1
$\begingroup$

First, not every infinite language is undecidable. Some infinite languages are very easy to decide. For example, the language of all words ($\Sigma^*$).

The converse is true, however: every undecidable language is infinite. In order to show this, we can simply show how to decide every finite language:

Consider a finite language $L=\{w_1,...,w_n\}$. In order to decide it, you can construct a TM $M$ that encodes in its states the words $w_1,...,w_n$. This is done as follows: the machine starts in $q_0$, which intuitively corresponds to the empty word $\epsilon$.

$M$ then reads an input letter. If there is no letter, meaning that the word is $\epsilon$, then $M$ either goes to $q_{acc}$ or $q_{rej}$, depending on whether or not $\epsilon\in L$. Now, if there is an input letter $\sigma$ on the tape, $M$ goes to a state that corresponds to $\sigma$. Then, again, it reads the tape. If there are no more letters, it either accepts or rejects, depending on whether $\sigma\in L$. Otherwise, it read the next input $\tau$ and moves to the state $\sigma\tau$, and so on, until the maximal length of a word in $L$ is reached, in which case $M$ rejects immediately.

So essentially, $M$ has a state for each word of length at most $k$, where $k$ is the maximal length of a word in $L$. Thus, $M$ can keep track of the word that was read so far, and decides if it needs to be accepted.

$\endgroup$
  • $\begingroup$ OK,in your TM M, which decides any finite language, it shows all finite languages are decidable. So non-decidable languages can't be finite. Thanks. $\endgroup$ – geasssos Nov 20 '13 at 19:53

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.