评估一个语言的“图灵完整性”的实用指南是什么？

我读过“什么是图灵完成”和维基百科页面，但是我对forms化certificate的兴趣不如图灵完成的实际意义。

我真正想要决定的是，如果我刚刚devise的玩具语言可以用作通用语言。我知道我可以certificate，如果我可以写一个图灵机。但是我不想经过这个练习，直到我相当确定的成功。

是否有一个最小的特征，没有图灵完全性是不可能的？是否有一套几乎可以保证完整性的function？

（我的猜测是条件分支和一个可读/可写的内存存储将使我在那里大部分的方式）

编辑：

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

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

你需要一些forms的dynamic分配结构（ malloc或new或cons将会这样做），以及recursion函数或其他写入无限循环的方式。如果你有这些，可以做任何有趣的事情，你几乎可以肯定图灵完成。

lambda演算与图灵机相当，如果你实现lambda演算，写lambda演算程序实际上是非常有趣的。比图灵机写程序更有趣！

我意识到图灵完备性唯一的实际意义是你可以编写不终止的程序。我使用了一些保证终止的特殊用途语言，因此不是图灵完成的。有时放弃额外的expression力量来换取有保证的终止是有用的。

“图灵完备性”描述了能够expression任何algorithm计算的性质，这首先是图灵机器的要点。一个语言或逻辑系统可以被描述为“图灵完成”，如果它有这个属性。从实用的angular度来看，所有通用编程语言（以及大量特殊用途的编程语言）都可以为适当松散的定义（见下文）做到这一点。

然而，图灵完备性的严格定义意味着无限的存储容量，这当然不是物理上可能的。考虑到这一点，没有任何物理机器可能是图灵完成的，但是这种约束通常会在将图灵完备性归于编程语言时放宽（至less是非正式的）。一种语言的图灵完整性的一个微不足道的testing是语言是否可以用来实现一个图灵机模拟器。

一个不是Turing Complete的广泛系统的例子是Relational Algebra，这是SQL背后的理论基础，如Codd的论文“大型共享数据库的关系模型”所述。关系代数具有Godel完备性，这意味着它可以expression任何可以用一阶谓词演算（即普通逻辑expression式）定义的计算。然而，它不是Turing-Complete，因为它不能expression一个任意的algorithm计算。

请注意，大部分（如果不是全部的话）所有实际的SQL方言都将纯粹的关系模型扩展到程序结构，以至于它们是Turing Complete（通常应用于编程语言的定义）。但是，单个SQL查询大体上不是。

Turing Complete领域特定语言的一些更令人震惊的例子是TeX和sendmail.cf，。在后一种情况下，实际上有人使用sendmail.cf来实现一个通用的图灵机模拟器。

如果你可以用你的语言编写一个Brainf $＆＃解释器，那么它是图灵完整的。 LOLCODE正是这样被certificate是图灵完整的。

非图灵完成语言的例子经常有限制循环 ，如：

 for i=1 to N {...}

但缺乏无限循环检查更一般的条件，如：

 while bool_expr {...}

如果所有可能的循环结构是有界的，你的程序将保证终止。而且，尽pipe无条件终止保证可能是有用的，但这也表明该语言不是图灵完成的。

还要注意，钉住所有可能的循环结构可能是困难的; 例如，我很确定C ++模板并不是图灵完成的…

我不确定是否有一个“最less的function”，但要certificate一种语言是图灵完整的，你只需要certificate它可以模拟另一个图灵完整的系统（不一定是一个图灵机），只要其他系统已知是图灵完整的。 http://en.wikipedia.org/wiki/Turing_complete#Examples有图灵完整系统的完整列表。; 其中一些比图灵机更简单。

我想补充一点，Norman Ramsey说：图灵机具有无限的内存，因此被认为是图灵完整的编程语言只有在内存也是无限的假设下才是如此。

Brainfuck是图灵完整的，只有循环结构和内存增加/减less，所以这就够了。

另一方面，在lambda演算中没有办法修改任何值，但它是Turing完成的，所以显然可以做到这一点，而不会有可变内存。

尽pipe你的程序很可能与lambda微积分无关，但对于实际的答案来说，最小值必须是

一种写入variables的方法
一种读取variables的方法
有条件的goto（if语句，while循环等）

我不记得看到像Turing Completeness的最小特征 。但是，如果你的语言支持循环和条件分支，那么图灵完成的机会就很好。但是，certificate它的唯一方法仍然是类似图灵机或另一种图灵完整语言。

如果你可以实现一个图灵机（只要他们可以实现，因为它们是无限存储的math结构[磁带大小是无限的]），那么你可以肯定它是图灵完整的。

一些迹象表明：

您可以检查内存并根据当前值对其进行操作，并使用它来控制程序stream。
该内存可以分配内存，你可以附加到的string，你可以通过recursion分配内存的堆栈等。
程序stream程可以通过迭代或者通过基于recursion的select。

任何不能终止的语言几乎都是图灵完成的。通过给它一个无限循环结构（像While循环或一个可以再次到达自身的Goto），或者通过给它一个通用的recursion（通过让一个函数调用自己而不受限制），你可以使语言无法终止。

一旦你完成了，你可以做一些事情来解释其他的Turing Complete语言，包括你自己的。

真正的问题是“它有什么好处？” 如果您的语言将被用于特定的领域来解决特定的问题，最好find一种方法来解决一个语言是不是图灵完成，从而保证给出答案。

您可以通过在任何其他Turing Complete语言（其中X由非Turing完整语言提供）中书写“执行此操作，即可完成”，或者以其他方式添加Turing Completeness，但可以使用X提供的结果执行此操作。

当然，如果你只想使用一种语言，它可能更好的是图灵完成…

是否有一个最小的特征，没有图灵完全性是不可能的？是否有一套几乎可以保证完整性的function？

是的，你需要有条件的数据stream控制：往往expression如下。例如，一个+-*/袖珍计算器不是图灵完整的，因为没有办法expression条件。

你还需要能够跳回到程序中的一个较早的点，在这之上你可以实现一个循环。例如，禁止向后跳转以保证程序终止的BPF也不是图灵完整的。

您需要一些可读写的存储空间。例如，只有两个32位variables的语言在计算能力方面受到限制。存储结构的存储方式有多种select：内存由指针，数组，堆栈，单元格，纯数据结构等组成。

除此之外，您还可以构build其他所有编程语言：它可能并不容易或快速，但这已经足够了。

您可以尝试模拟一个OISC （一台指令集计算机）。如果你可以模拟其中的一个指令，那么因为这些指令可以用来组成一个Turing Complete机器，所以你已经certificate你的语言也必须是Turing Complete。

…比图灵完成的实际意义更为重要。

我怀疑是否有完整的图灵的实际意义。

如果你看一下图灵整机的一些例子，比如原来的图灵机，你会发现它们对于真正的计算来说是非常有用的，所以这个概念只能是理论上的兴趣。