# Prove that all non-recursive languages are infinite

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

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?

• Are you familiar with regular languages? Every finite language is regular. Can you proceed from here? – Shaull Nov 20 '13 at 18:23
• sorry, not really sure what's regular language is. – geasssos Nov 20 '13 at 18:26
• 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. – Shaull Nov 20 '13 at 18:28

First, not every infinite language is undecidable. Some infinite languages are very easy to decide. For example, the language of all words ($\Sigma^*$).
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.