recursion - 证明所有非递归语言都是无限的

Question

我想知道[标题]上面的这句话是真的还是假的。

这是我已经拥有的：非递归意味着不可判定。

我读过这篇文章 所有无限语言都无法确定吗？

其中说：

如果一种语言是不可判定的（非递归的），则必须有一些字符串使 TM 无法停止。所以它必须有无限的字符串使 TM 无法停止。

这怎么能证明我的陈述[标题]？谁能更清楚地向我解释一下？

谢谢

附言。对困惑感到抱歉。是的，TM 表示图灵机。也很清楚我的问题是：所有非递归语言都是无限的吗？

Answer 1

作为提示：证明所有有限语言都是正则的。所有常规语言都是可判定的。取这个陈述的对立面，你会发现所有不可判定（非递归）的语言都是无限的。

希望这可以帮助！