按照我的理解,图灵机只是一种算法的机器表示。算法和图灵机有区别吗?
最佳答案
它们非常不同。
算法是一个过程。它可以通过多种方式指定,通常是通过用某种编程语言编写程序。相比之下,图灵机描述了一个适合在非常具体且不切实际的机器上运行的过程。
然而,算法的特性取决于运行它的机器。图灵机看起来与现实世界感兴趣的任何机器都不一样。因此,虽然每个算法都可以用图灵机来表示,但图灵机并不是首选的表示方式。图灵机表示掩盖了算法最有趣的属性。
例如众所周知的归并排序是O(n log(n))
。从 1960 年代唐纳德·高德纳 (Donald Knuth) 的人工 MIX 架构到如今云中高度并行的分布式实现,它都以这种方式进行扩展。
但在图灵机中,并行遍历两个数组并写入第三个数组需要不断地在磁带中两个相距较远的位置之间来回寻找以比较它们,然后再次寻找写入输出的位置。因此,虽然您可以构建实现可识别合并排序的图灵机,但它不会是O(n log(n))
。不是一英里。事实上,它的性能会比冒泡排序差得多。 (因为冒泡排序只比较磁带上接近的东西,所以来回查找的时间更少。)
关于algorithm - 图灵机和算法有什么区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65328165/