Ada*_*ent 7 theory concurrency quantum-computing
我经常看到人们说如果你能用某种语言做X,你可以用另一种语言做Y,这就是Turing Complete论证.所以你经常(通常在讽刺评论中)"确定你可以用y做,因为y也是图灵完成.
我很久以前就采用了CS理论,但我不认为这总是正确的,因为我不确定图灵在哪里适合并发.例如,有适当硬件的编程语言,您可以在同一时间执行事情,但在其他情况下则无法执行.
我理解这可能更多的是硬件/驱动程序问题而不是语言,但我很好奇并发是否或如何改变Turing Complete的内容？你可以超过图灵完成吗？
编辑: 在原来的原因,我问这个问题在很大程度上是由于量子计算.虽然接受的答案并未说明这一点,但量子计算(表面上)是图灵的一个子集.
对许多人来说,这是一个令人困惑的话题; 你不是一个人.问题是这里有两种不同的"可能"定义."可能"的一个定义是你如何使用它:是否可以进行并发,是否可以使用该语言操作巨型机器人,是否可以让计算机享受草莓等等.这是外行人的定义"可能".
图灵完整性与上述意义上的可能性无关.当然,并发性在任何地方都是不可能的,因为(对于至少一些并发的定义),语言可以生成可以同时在两个或多个不同处理器上运行的代码.一种只能编译为将在单个处理器上运行的代码的语言因此不具备并发性.然而,它可能仍然是图灵完成的.
图灵完整性与可以在给定足够内存和运行时间的机器上计算的各种数学函数有关.为了评估数学函数,单个处理器可以完成多个处理器所能做的一切,因为它可以通过一个接一个地执行一个处理器的逻辑来模拟多个处理器.可以在任何设备上计算的所有数学函数都是使用图灵机计算出来的(未经证实且无法证实的,虽然可证伪的)声明,即所谓的Church-Turing论文.
如果您可以证明您可以使用它来模拟任何图灵机,那么编程语言称为Turing-complete.将此与Church-Turing论文相结合,这意味着编程语言能够评估任何设备可以评估的每种类型的数学函数,给定足够的时间和内存.大多数语言都是图灵完备的,因为这只需要分配动态数组并使用循环和if语句以及一些基本数据操作的能力.
走向另一个方向,因为可以构建图灵机来模拟我们目前所知的任何处理器,并且编程语言使用处理器完成它们所做的事情,当前的编程语言也没有比图灵机更具表现力的能力.因此,在所有常见的编程语言中,数学函数的计算同样是可能的.可计算的函数在另一个中是可计算的.这对性能没有任何说明- 并发本质上是一种性能优化.