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

Question

在 Michael Sipser 的计算理论导论中，他说:

"some languages are not decidable or even Turing recognizable, for the reason that there are uncountably many languages yet only countably many Turing machines. Because each Turing machine can recognize a single language and there are more languages than Turing machines, some languages are not recognized by any Turing machine" (178).

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

Answer 1

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