algorithm - 递归可判定语言，接受无限语言

Question

因此，我的理解是，递归可判定语言是我们可以构建图灵机的语言，这样给定来自该语言的输入 w，图灵机将始终要么接受并停止，要么拒绝并停止。我感到困惑的是可以发展到无穷大的语言。例如，假设我们有一种语言 L = {0^p | p 是素数}。所以我们可以编写一个算法来判断一个数在线性空间中是否是素数。所以我的理解是，既然这个算法告诉我们数字是素数还是不是素数，那么 L 必须是递归可判定的，对吗？但是由于 p 不受任何固定数的约束，它可以到无穷大对吗？那么假设我的算法在技术上可以永远运行，而不接受或拒绝输入，这是否正确？

Answer 1

1. 是的，素数长度的一元词的语言是可判定的。正如您所说，这甚至可以在输入大小的线性空间中完成。
2. 是的，该语言包含任意长度的单词。但是说 p 趋于无穷大是一种误导。它采用所有可能的整数值，但没有任何顺序。无穷大不是整数，并且由于集合定义中没有顺序，因此没有任何趋向无穷大的趋势。
3. 不，你不能假设算法永远运行。它不会将所有字符串作为输入，而仅将一个字符串作为输入。并且每个字符串的长度都是有限的，因此算法将针对其中的每个字符串终止。有无限多不同的可能输入这一事实与此无关。