我已经阅读了“什么是图灵完备”和维基百科页面，但我对正式证明的兴趣不如对图灵完备的实际意义感兴趣。
我实际上想要决定的是我刚刚设计的玩具语言是否可以用作通用语言。我知道如果我可以用它编写图灵机，我可以证明它是。但在我相当确定成功之前，我不想进行那个练习。
是否有最小的功能集，没有图灵完备性是不可能的？是否有一组功能几乎可以保证完整性？
（我的猜测是条件分支和可读/可写的内存存储将使我大部分时间到达那里）
编辑：
我想我已经说“图灵完成”了。我试图以合理的信心猜测具有特定功能集的新发明语言（或者具有特定指令集的 VM）将能够计算任何值得计算的东西。我知道证明你可以用它构建图灵机是一种方法，但不是唯一的方法。
我希望的是一套指导方针，例如：“如果它可以做 X、Y 和 Z，它可能可以做任何事情”。
您需要某种形式的动态分配构造（malloc或new或cons将做）以及递归函数或其他一些编写无限循环的方式。如果您拥有这些并且可以做任何有趣的事情，那么您几乎可以肯定是图灵完备的。
lambda 演算在功能上等同于图灵机，如果您实现 lambda 演算，编写 lambda 演算程序实际上非常有趣。 比为图灵机编写程序更有趣！
我知道的图灵完备性的唯一实际含义是您可以编写不会终止的程序。我使用了几种保证终止的专用语言，因此不是图灵完备的。有时放弃额外的表达能力以换取有保证的终止是有用的。
“图灵完备性”描述了能够表达任意算法计算的属性，这首先是图灵机的重点。如果语言或逻辑系统具有此属性，则可以将其描述为“图灵完备”。从实用的角度来看，所有通用编程语言 - 以及数量惊人的专用编程语言 - 都可以为适当松散的定义做到这一点（见下文）。
然而，图灵完备性的严格定义意味着无限的存储容量，这在物理上当然是不可能的。鉴于此，没有物理机器可能是图灵完备的，但是当将图灵完备归因于编程语言时，这种约束通常会被放松（至少是非正式的）。一种语言的图灵完备性的一个简单测试是该语言是否可用于实现图灵机模拟器。
不是图灵完备的广泛系统的一个例子是关系代数，它是 Codd 的论文大型共享数据库的关系模型中描述的 SQL 背后的理论基础。 关系代数具有哥德尔完备性的性质，这意味着它可以表达任何可以用一阶谓词演算（即普通逻辑表达式）定义的计算。但是，它不是图灵完备的，因为它不能表达任意算法计算。
请注意，如果不是所有实用 SQL 方言，大多数（如果不是全部）实用 SQL 方言都使用过程构造扩展了纯关系模型，以至于它们按照通常应用于编程语言的定义是图灵完备的。但是，单个 SQL 查询大体上不是。
图灵完备领域特定语言的一些更令人震惊的例子是TeX和sendmail.cf，. 在后一种情况下，实际上有一个著名的例子，有人使用 sendmail.cf 来实现通用图灵机模拟器。
不是图灵完备的语言的例子经常有有界循环，比如：
for i=1 to N {...}但缺少检查更一般条件的无界循环，例如：
while bool_expr {...}如果所有可能的循环结构都是有界的，那么您的程序肯定会终止。而且，尽管无条件终止保证可能有用，但这也表明该语言不是图灵完备的。
还要注意，确定所有可能的循环结构可能很困难。例如，我很确定 C++ 模板不是图灵完备的……
我不确定是否存在“最小功能集”，但要证明一种语言是图灵完备的，你只需要证明它可以模拟另一个图灵完备的系统（不一定是图灵机），只要其他系统已知是图灵完备的。http://en.wikipedia.org/wiki/Turing_complete#Examples有一个完整的图灵完备系统列表。其中一些比图灵机更简单。
我想对 Norman Ramsey 所说的添加一个警告：图灵机具有无限的内存，因此被认为是图灵完备的编程语言只是在内存也是无限的假设下如此。
Brainfuck 是图灵完备的，只有循环结构和内存增量/减量，所以这就足够了。
另一方面，无法修改 lambda 演算中的任何值，但它是图灵完备的，因此显然可以在没有可变内存的情况下进行修改。
不过，您的程序很可能与 lambda 演算无关，因此对于实际答案，最小值必须是
我不记得看到图灵完整性的最低功能。但是，如果您的语言支持循环和条件分支，那么它是图灵完备的可能性很大。但是，证明它的唯一方法仍然是模拟图灵机或另一种图灵完备语言。
如果您可以实现图灵机（只要可以实现，因为它们是具有无限内存的数学结构[磁带大小是无限的]），那么您可以确定它是图灵完备的。
一些迹象：
任何能够不终止的语言几乎都是图灵完备的。您可以通过为语言提供无界循环结构（如 While 循环或可以再次到达自身的 Goto）或通过为其提供一般递归（通过让函数不受限制地调用自身）来使语言无法终止。
一旦你完成了图灵完备，你就可以做一些事情，比如解释其他图灵完备语言，包括你自己的。
真正的问题是“它有什么好处？” 如果您的语言将用于特定领域来解决特定问题，那么最好找到一种方法来用不是图灵完备的语言来表达解决方案，从而保证给出答案。
您始终可以通过在任何其他图灵完备语言（其中 X 由非图灵完备语言提供）中编写“做这个、那个或任何事情；但用 X 提供的结果来做”来添加图灵完备性。
当然，如果你只想使用一种语言，最好是图灵完备......
您可以尝试模拟OISC（一台指令集计算机）。如果您可以模拟其中的一条指令，那么由于这些单条指令可用于组成图灵完备机器，那么您已经证明您的语言也必须是图灵完备的。
是否有最小的功能集，没有图灵完备性是不可能的？是否有一组功能几乎可以保证完整性？
是的，您需要有以数据为条件的控制流：通常表示为if. 例如，+-*/袖珍计算器不是图灵完备的，因为没有办法表达条件。
您还需要能够在程序中表达返回到较早点的跳转，在此之上您可以实现一个循环。例如，禁止向后跳转以保证程序将终止的 BPF 也不是图灵完备的。
您需要一些可读写且任意大的存储空间。例如，只有两个 32 位变量的语言的计算能力受到限制。对于存储的结构，您有很多选择：由指针、数组、堆栈、cons 单元、纯数据结构等寻址的内存。
在这些之上，您可以构建所有其他编程语言：它可能并不容易或快速，但已经足够了。