computer-science - 评估语言 "Turing Completeness"的实用指南是什么？

Question

我已阅读 "what-is-turing-complete"和维基百科页面，但我对形式证明不太感兴趣，而对图灵完备的实际 含义 要求感兴趣。

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

是否存在一个最小的特征集，没有这些特征集，图灵完备性就不可能实现？是否有一组功能实际上可以保证完整性？

(我的猜测是条件分支和可读/可写内存存储将帮助我完成大部分任务)

<小时/>

编辑:

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

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

Answer 1

您需要某种形式的动态分配构造(malloc 或 new 或 cons 即可)以及递归函数或其他某种方式写一个无限循环。如果您拥有这些并且可以做任何有趣的事情，那么您几乎肯定是图灵完备的。

lambda 演算的能力相当于图灵机，如果您实现 lambda 演算，那么编写 lambda 演算程序实际上非常有趣。 比为图灵机编写程序有趣得多!

据我所知，图灵完备性的唯一实际意义是您可以编写不会终止的程序。我使用了几种保证终止的专用语言，因此它们不是图灵完备的。有时，放弃额外的表达能力以换取有保证的终止是有用的。