图灵机和算法有什么区别？

Question

按照我的理解，图灵机只是一种算法的机器表示。算法和图灵机有区别吗？

Answer 1

算法比图灵机广泛得多。算法实际上只包含一些输入和一组要遵循这些输入的指令。这是一个非常简单的算法：

Algorithm SumNumbers
  Input: A list of numbers L.
  Output: The sum of all numbers in L.
  if L.size = 0 return null
  sum <- 0
  for each item in L, do
    sum <- sum + item
  return sum

至此，我们已经定义了算法。甚至还没有讨论图灵机。

一旦定义了m元组，图灵机就只是一种算法。输入是通过设置磁带的初始状态来定义的。算法的输出是最终状态 and/or 进程停止后磁带的最终状态。并且在给定输入的情况下达到输出的步骤由 m 元组和车床计算的一般规则确定：https://en.wikipedia.org/wiki/Turing_machine#Formal_definition

现在，确定图灵机是否会真正停止并为您提供“输出”是另外一个难题：https://en.wikipedia.org/wiki/Halting_problem

Answer 2

它们非常不同。

算法是一个过程。它可以通过多种方式指定，通常是通过用某种编程语言编写程序。相比之下，图灵机描述了一个适用于运行非常具体且不切实际的机器的过程。

然而，算法的特性取决于它运行所在的机器。图灵机看起来与现实世界感兴趣的任何机器都不一样。因此，虽然每个算法都可以用图灵机来表示，但图灵机并不是首选的表示方式。图灵机表示掩盖了算法最有趣的属性。

例如众所周知的归并排序 O(n log(n))。从 1960 年代 Donald Knuth 的人工 MIX 架构到如今云中高度并行的分布式实现，它都以这种方式进行扩展。

但是在图灵机中，并行遍历两个数组并写入第三个数组需要不断地在磁带中两个相距较远的位置之间来回查找以比较它们，然后再次查找以找到写入输出的位置。因此，虽然您可以构建实现可识别归并排序的图灵机，但它不会是 O(n log(n))。不是一英里。事实上，它的性能会比冒泡排序差得多。（因为冒泡排序只比较磁带上接近的东西，所以来回寻找的时间更少。）

图灵机和算法有什么区别？

What is the difference between a Turing Machine and an Algorithm?

algorithm

math

automata

infinite

turing-machines