问题标签 [turing-complete]

对于这个新手问题，我很抱歉，但如果可能的话，我需要一个快速的答案来告诉朋友。

今天早上，我在纯 HTML5 + CSS3（无 javascript）中遇到了以下规则 110 的实现。您按顺序按制表符和空格键来运行自动机。

http://elilies.com/rule110-full.html

我查看了源代码，但我真的无法弄清楚它是如何跟踪状态的。按下选项卡时，我认为 :focus 选择器会起作用，但我不确定按下空格时会发生什么。

“字典”是指具有唯一键的键/值对数组。如果不是，为什么？如果足够长，您可以将键用作输入，将值用作输出，它可以解决任意数量的问题。只要它足够长以容纳所有可能的输入，它就可以“计算”任何东西。只要确定输入将具有一定数量的位，它就不需要是无限的。因此，如果我们同意输入将是 X 位，那么您将只需要一个包含 2^X 项的字典，并且您拥有所有可能的图灵机，它将 X 位作为输入。

对？好吧，我想我不是，但为什么？

如果我们将星巴克的迷你语言菜单系统解释为某种语法或状态机，那么这种语法会是图灵完备的吗？星巴克的订单迷你语言的描述可以在这里找到

我知道 C++ 模板元编程是图灵完备的。预处理器元编程也有同样的情况吗？

我的意思是，编写网络摄像头识别，其准确性接近 kinect。

我见过 Ruby 和 Perl 程序员完全使用正则表达式来完成一些复杂的代码挑战。Perl 正则表达式中的前瞻和后视能力使它们比大多数其他语言中的正则表达式实现更强大。我想知道他们到底有多强大。

有没有一种简单的方法可以证明或反驳 Perl 正则表达式是图灵完备的？

在 System FI 中，可以使用 Church 数字定义真正的总加法函数。

在 Haskell 中，由于底部值，我无法定义该函数。例如，在 haskell 中，如果 x + y = x，那么我不能说 y 为零 - 如果 x 是底部，对于任何 y，x + y = x。所以加法不是真正的加法，而是它的近似值。

在 CI 中无法定义该函数，因为 C 规范要求所有内容都具有有限的大小。所以在 C 中可能的近似值甚至比在 Haskell 中更糟糕。

所以我们有：

在 System F 中，可以定义加法，但不可能有完整的实现（因为没有无限的硬件）。

在 Haskell 中，不可能定义加法（因为底部），也不可能有完整的实现。

在 C 中，不可能定义总加法函数（因为一切的语义都是有界的），但兼容的实现是可能的。

因此，所有 3 个正式系统（Haskell、System F 和 C）似乎都有不同的设计权衡。

那么选择一个而不是另一个的后果是什么？

昨天，我在网上看到了一篇关于编程语言的文章，叫做BrainFuck. http://www.muppetlabs.com/~breadbox/bf/

所以奇怪的是我是这个

那么，它真的是当今图灵完备编程语言的最小编译器吗？是否证明了更小的编译器无论如何都不存在？

这方面有没有结果。我真的很感兴趣，图灵完备的编程语言的编译器的大小是否有最小值，这个值是多少？

“图灵完备性”的完整定义需要无限的记忆。

除了受限于有限的（比如 100 字或 16 位或 32 位等）地址空间之外，还有比图灵完备更好的术语吗？