recursiontheorycomputability

Prove that all non-recursive languages are infinite


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

ps. sorry for the confusion. Yes TM means Turing machine. And too be clear My question is : Does ALL non-recursive languages are Infinite?


Solution

  • As a hint: prove all finite languages are regular. All regular languages are decidable. Taking the contrapositive of this statement gives you that all undecidable (non-recursive) languages are infinite.

    Hope this helps!