Arc*_*her 3 theory algorithm turing-machines computation
在Michael Sipser的计算理论导论中,他指出:
"有些语言不具有可判定性,甚至图灵无法识别,因为有无数种语言,但只有相当多的图灵机.因为每个图灵机都能识别单一语言,而且语言比图灵机器多,有些语言无法识别任何图灵机"(178).
图灵机不是可以模拟任何计算机算法的假想机器吗？从理论上讲,您是否可以提出无数的算法？我无法绕过这个概念.我将非常感谢"像我5'这样的解释",但当然,任何帮助都比没有好.
sep*_*p2k 11
有一个可数图灵机的数量.这并不意味着数量有限.图灵机的数量是无穷无尽的,这意味着图灵机可以使用自然数进行编号.也就是说,您可以在自然数和图灵机之间创建一对一的映射.