问题标签 [turing-complete]

“图灵完备”的表达是什么意思？

你能给出一个简单的解释，而不涉及太多的理论细节吗？

有人告诉我，C++ 中的模板系统在编译时是图灵完备的。这篇文章和维基百科都提到了这一点。

您能否提供一个利用此属性的计算的重要示例？

这个事实在实践中有用吗？

正如他们在.Net 3.5中一样。我知道它们在 4.0 中，因为这就是 DLR 的工作方式，但我对我们现在拥有的版本感兴趣。

几乎所有使用的编程语言都是图灵完备的，虽然这提供了表示任何可计算算法的语言，但它也带来了自己的一系列问题。鉴于我编写的所有算法都打算停止，我希望能够用一种保证它们会停止的语言来表示它们。

词法分析时使用用于匹配字符串和有限状态机的正则表达式，但我想知道是否有一种更通用、更广泛的语言不是图灵完备的？

编辑：我应该澄清一下，通过“通用”我不一定希望能够用该语言编写所有停止算法（我认为这种语言不会存在）但我怀疑有共同的线程停止证明，可以推广以产生一种语言，其中所有算法都保证停止。

还有另一种方法可以解决这个问题——消除理论上无限内存的需要。一旦限制了机器允许的内存量，机器所处的状态数是有限且可数的，因此您可以确定算法是否会停止（通过不允许机器进入之前的状态） ）。

我最近在阅读关于人工生命的文章，偶然发现了这样的说法，“康威的生命游戏展示了足够的复杂性，可以被归类为通用机器。” 我对什么是通用机器只有一个粗略的了解，而维基百科只是让我与维基百科一样接近理解。我想知道是否有人可以对这个非常性感的声明有所了解？

对我来说，康威的生命游戏似乎是一种可爱的消遣，具有一些巨大的影响：我无法在它和计算器之间进行跳跃？这甚至是我应该做出的飞跃吗？

我已经阅读了“什么是图灵完备”和维基百科页面，但我对正式证明的兴趣不如对图灵完备的实际意义感兴趣。

我实际上想要决定的是我刚刚设计的玩具语言是否可以用作通用语言。我知道如果我可以用它编写图灵机，我可以证明它是。但在我相当确定成功之前，我不想进行那个练习。

是否有最小的功能集，没有图灵完备性是不可能的？是否有一组功能几乎可以保证完整性？

（我的猜测是条件分支和可读/可写的内存存储将使我大部分时间到达那里）

编辑：

我想我已经说“图灵完成”了。我试图以合理的信心猜测具有特定功能集的新发明语言（或者具有特定指令集的 VM）将能够计算任何值得计算的东西。我知道证明你可以用它构建图灵机是一种方法，但不是唯一的方法。

我希望的是一套指导方针，例如：“如果它可以做 X、Y 和 Z，它可能可以做任何事情”。

对于图灵完备的语言，停止问题无法解决，而对于某些非 TC 语言（如它总是停止的正则表达式），它可以轻松解决。

我想知道是否有任何语言同时具有停止和不停止的能力，但承认可以确定它是否停止的算法。

Lambda 演算当然是相当优雅的，但是函数的输入和输出之间存在这种不对称，你不会感到困扰吗？即你可以让函数接受两个参数（通过返回一个函数），但你不能让它返回两个值。我不认为我们可以在The Book中找到它。

例如，在编写操作系统时，是否有某些事情无法用图灵完备的语言来完成？

我刚刚尝试创建最小的语言解释器。你想加入并尝试吗？

游戏规则：

• 您应该指定您正在解释的编程语言。如果它是您发明的一种语言，它应该在评论中附带一个命令列表。
• 您的代码应该从分配给您的代码和数据变量的示例程序和数据开始。
• 您的代码应以结果输出结束。最好在每个中间步骤都有调试语句。
• 您的代码应该可以按照编写的方式运行。
• 您可以假设数据是 0 和 1（整数、字符串或布尔值，您可以选择）并且输出是单个位。
• 该语言应该是图灵完备的，因为对于在标准模型上编写的任何算法，例如图灵机、马尔可夫链或您选择的类似算法，如何编写执行后的程序是相当明显（或解释）的由您的解释器执行算法。
• 代码长度定义为去掉输入部分、输出部分、调试语句和不必要的空格后的代码长度。请将生成的代码及其长度添加到帖子中。
• 您不能使用使编译器为您执行代码的函数，例如eval()或exec()类似的。

这是一个社区 Wiki，这意味着问题和答案都不会从投票中获得声誉积分。但无论如何都要投票！