algorithm - 为什么图灵机的数量是有限的？

Question

在 Michael Sipser 的《计算理论导论》中，他说：

“有些语言是不可判定的，甚至是图灵无法识别的，因为语言有无数种，而图灵机只有无数种。因为每台图灵机只能识别一种语言，而且语言比图灵机多，所以有些语言无法识别通过任何图灵机”（178）。

图灵机不是可以模拟任何计算机算法的假设机器吗？理论上你能想出无数种算法吗？我很难理解这个概念。非常感谢“像我 5 岁一样解释”的答案，但当然，任何帮助总比没有好。

Answer 1

有无数的图灵机。这并不意味着有一个有限的数字。图灵机的集合是可数无限的，这意味着图灵机可以使用自然数进行编号。也就是说，您可以在自然数和图灵机之间创建一对一的映射。