评估语言的“图灵完整性”的实际准则是什么？
https://stackoverflow.com/questions/449014
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我读了 “什么 - 完整的” 还有Wikipedia页面，但我对正式证明的兴趣不如Turing完成的实际含义。
我实际上要决定的是我刚刚设计的玩具语言是否可以用作通用语言。我知道我可以证明是否可以用它编写图灵机。但是，直到我确定成功之前，我不想进行这项练习。
是否没有最低的功能，没有图灵的完整性？是否有一组几乎可以保证完整性的功能？
（我的猜测是有条件的分支和可读/可写入的内存商店将使我大部分时间到达那里）
编辑：
我认为我说“图灵完整”是在切线的。我试图合理的信心猜测，具有特定功能集的新发明的语言（或其他具有一定指令集的VM）将能够计算任何值得计算的内容。我知道证明您可以用它构建图灵机是一种方法，但不是唯一的方法。
我希望的是一组准则：“如果可以做X，Y和Z，它可以 大概 做任何事情”。
解决方案
您需要某种形式的动态分配结构（malloc 或者new 或者 cons 会做）和递归功能或其他一些编写无限循环的方式。如果您有这些并且可以做任何有趣的事情，那么您几乎可以肯定的是图灵完整。
lambda演算的功率与图灵机相等，如果您实现了lambda微积分，那么编写lambda calculus程序实际上很有趣。 方法 比图灵机的编写程序更有趣！
我知道的图灵完整性的唯一实际含义是，您可以编写不终止的程序。我使用了几种保证终止的专用语言，因此 不是 图灵完整。有时，放弃额外的表达能力以换取保证终止很有用。
其他提示
“图灵完整性” 描述能够表达任何任意的财产 算法计算， 这就是重点 图灵的机器 首先。如果语言或逻辑系统具有此属性，则可以将其描述为“图灵完整”。从实际的角度来看，所有通用编程语言（以及大量的特殊用途）都可以做到适当的定义（见下文）。
但是，对图丁完整性的严格定义意味着无限的存储能力当然是不可能的。鉴于此，没有任何物理机器可以完成，但是当将Turing完整性归因于编程语言时，通常会放松（至少在非正式上）这种约束。一种语言的图丁完整性的一个微不足道的测试是该语言是否可以用于实现图灵机模拟器。
不完整的广泛系统的一个示例是关系代数，这是CODD论文中所述SQL背后的理论基础 大型共享数据库的关系模型。 关系代数具有 上帝的完整性, ，这意味着它可以表达任何可以根据 一阶谓词演算 （即普通逻辑表达式）。但是，它并不是Turing-Complete，因为它无法表达任意算法计算。
请注意，大多数如果不是所有实用的SQL方言，则将纯粹的关系模型扩展到程序构造的范围内，以至于它们按照通常应用于编程语言的定义完整。但是，单个SQL查询总体上不是。
图灵完整的特定域特异性语言的一些令人震惊的例子是 德克萨斯 和 sendmail.cf，. 。在后一种情况下，实际上有一个著名的例子，就是有人使用sendmail.cf 实施通用的图灵机模拟器。
如果你可以写 brainf $＆＃ 用您的语言解释器，它是图丁完整的。 lolcode 被证明是用这种方式完成的。
不经常完整的语言的示例 有界环, ， 喜欢：
for i=1 to N {...}但是缺乏 无限 循环检查更通用的条件，例如：
while bool_expr {...}如果所有可能的循环结构都有限，则保证您的程序将终止。而且，尽管无条件的终止保证潜在有用，但这也表明该语言不是完整的。
还请注意钉住 一切可能 循环结构可能很困难；例如，我很确定C ++模板不是打算完整的...
我不确定是否有“最低功能”已知其他系统正在完成。 http://en.wikipedia.org/wiki/turing_complete#examples 有整个图灵完整系统列表。其中一些比图灵机简单。
我想对诺曼·拉姆西（Norman Ramsey）所说的警告添加一个警告：图灵机具有无限的记忆力，因此被认为是图灵完整的编程语言仅在假设记忆也是无限的假设下。
Brainfuck已完成Turing完整，并且只有循环结构和记忆的增量/减少，因此足够了。
另一方面，无法修改lambda演算中的任何值，但是它已经完成了，因此显然可以在没有可变内存的情况下这样做。
您很可能您编程与lambda微积分无关，因此，对于实际答案，最低限度必须是
- 一种写入变量的方法
- 一种读取变量的方法
- 有条件的goto形式（如果语句，循环等）
我不记得看到类似的东西 最小功能 用于图丁完整性。但是，如果您的语言支持循环和有条件的分支，那么图灵完成的机会很不错。但是，证明它仍然是模拟图灵机或其他图灵完整语言的唯一方法。
如果您可以实现图灵机（尽可能实现它们，因为它们具有无限内存的数学构造（磁带大小为Infinte]），那么您可以确定它的图灵完成了。
一些迹象：
- 您可以根据当前值以及使用它来控制程序流。
- 可以分配内存的内存，您可以附加到的字符串，可以通过递归等上分配内存的堆栈。
- 程序流可以通过迭代或基于选择的递归。
任何能够非终止的语言都几乎完整了。您可以通过给予无限制的循环结构（例如循环或可以再次达到自身的goto）或通过给出一般递归（通过让函数呼叫本身而毫不限制的情况下）来制作一种非终止能力的语言。
一旦您 是 图灵完成，您可以做一些解释其他图灵完整语言（包括自己的）之类的事情。
真正的问题是“有什么好处？”如果您的语言将在特定领域中用于解决特定问题，那么最好找到一种方法来用不完整的语言来示意解决方案，因此可以保证给出答案。
您总是可以通过编写“执行此操作，或其他任何内容来添加图灵完整性；但是，在任何其他图灵完整的语言中提供了X提供的结果，其中X提供了非曲目的完整语言。
当然，如果您只想使用一种语言，那么它可能最好是完整的...
您可以尝试模仿 OISC （一台指令集计算机）。如果您可以模仿其中的一种说明，那么由于可以使用这些单个指令来构成图灵完整的机器，因此您已经证明您的语言也必须完整。
是否没有最低的功能，没有图灵的完整性？是否有一组几乎可以保证完整性的功能？
是的，您需要在数据条件下具有控制流量：通常表示的 if. 。例如 +-*/ 口袋计算器不是图灵完整的，因为没有办法表达有条件的条件。
您还需要能够将跳跃回到程序中的较早点，其中您可以实现循环。例如，禁止向后跳动以确保程序将终止的BPF也未完成。
您需要一些既可以阅读又可写的且任意大的存储空间。例如，只有两个32位变量的语言在计算上受到限制。您有许多选择存储的构造方法：由指针，数组，堆栈，缺陷单元格，纯数据结构等解决的内存等。
最重要的是，您可以构建其他所有编程语言：它可能不容易或快速，但这足够了。
