Prove that all non-recursive languages are infinite

Problem Detail: 

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?

Asked By : geasssos

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18203