concurrency - 图灵完备和并行编程(真正的并发)

Question

我经常看到人们说如果你能用某种语言做 X，你就可以用另一种语言做 Y，这就是图灵完备的论点。所以你会经常(通常在一个讽刺的评论中)“确定你可以用 y 做 t 因为 y 也是图灵完备的。

我很久以前就学过 CS 理论，但我认为这并不总是正确的，因为我不确定图灵在哪里适合并发。例如，有些编程语言具有正确的硬件，您可以执行完全同时发生的事情，但其他语言则不可能。

我知道这可能更多是硬件/驱动程序问题而不是语言，但我很好奇并发是否或如何改变图灵完备？你能比图灵完备吗？

编辑:
original reason我问这个问题在很大程度上是由于量子计算。虽然接受的答案没有说这个 but quantum computing is (ostensible) a subset of turing .

Answer 1

对于很多人来说，这是一个令人困惑的话题；你不是一个人。问题是这里对“可能”有两种不同的定义。 “可能”的一个定义是你如何使用它:是否可以进行并发，是否可以使用该语言操作巨型机器人，是否可以让计算机享受草莓等。 这是外行的定义的“可能”。

图灵完备性与上述意义上的可能性无关。当然，并发性并非无处不在，因为(至少对于并发性的某些定义)语言必须能够生成可以同时在两个或多个不同处理器上运行的代码。一种只能编译为将在单个处理器上运行的代码的语言，因此不能并发。然而，它仍然可以是图灵完备的。

图灵完备性与可以在给定足够内存和运行时间的机器上计算的数学函数类型有关。出于评估数学函数的目的，单个处理器可以做多个处理器能做的所有事情，因为它可以通过一个接一个地执行一个处理器的逻辑来模拟多个处理器。可以在任何设备上计算的所有数学函数都可以使用图灵机计算的(未经证实和无法证实，但可证伪)声明是所谓的 Church-Turing论文 .

一种编程语言被称为 图灵完备如果你能证明你可以使用它来模拟任何图灵机。将此与 Church-Turing 论文结合起来，这意味着编程语言能够评估任何设备可以评估的每种类型的数学函数，只要有足够的时间和内存。大多数语言都是图灵完备的，因为这只需要分配动态数组和使用循环和 if 语句以及一些基本数据操作的能力。

另一方面，由于可以构建图灵机来模拟我们目前所知的任何处理器，并且编程语言使用处理器来完成它们所做的事情，因此当前的编程语言也没有比图灵机更强大的表达能力。因此，数学函数的计算同样可以跨所有常见的编程语言进行。在一个函数中可计算的函数在另一个函数中是可计算的。这与性能无关——并发本质上是一种性能优化。