turing-machines - 图灵完备性

Question

因此，如果一种语言满足某些标准，就可以说它是图灵完备的，并且它可以做另一种图灵完备语言可以做的任何事情。

这是否意味着我理论上可以使用 JavaScript 或Brainf_ck实现 Google ？

Answer 1

您可以从由火柴盒和石头组成的堆栈机器实现 Google。亚巴-达巴-杜？

Answer 2

不，对于给定的示例，这是不可能的。图灵完备性是关于实现算法之类的，它不会告诉你是否不能在其中实现任何软件。谷歌主要依赖他们的数据库，你不能直接通过 JavaScript 操作，所以没有 DB == 没有谷歌。

Answer 3

是的，他们可以计算的任何东西，你都可以用这些语言做。但这并没有说明所需的内存或其他存储量、运行速度或编写或调试的难易程度。

Answer 4

除了 I/O 性能问题外，还有执行时间问题。一台图灵完备机器执行某项任务所需的步骤数可能比另一台图灵完备机器执行相同任务所需的步骤数长数百个数量级。因此，一台机器完全有可能在几分之一秒内完成一项让另一台机器忙碌到宇宙尽头的任务。如果让后一种机器在宇宙终结后以某种方式继续运行，它可能会产生答案，但从实际的角度来看，后一种机器将无法有效地解决这个问题，尽管它具有图灵完备性。