以太坊和图灵完整性

只要你开始阅读关于以太坊的信息，你将立即听到“图灵完成”一词。他们说，与比特币不同，以太坊是“图灵完成”。这到底是什么意思呢？

术语“图灵完全”是以英国数学家阿兰图灵（Alan Turing）的名字命名的，他被认为是计算机科学之父。1936年，他创建了一个计算机的数学模型，该计算机由一个状态机构成，该状态机通过读写顺序存储器（类似于无限长度的磁带）来操纵符号。通过这个构造，Alan Turing继续提供了一个来回答（否定的）关于 通用可计算性（是否可以解决所有问题）问题的数学基础。他证明了存在一些不可计算的问题。具体来说，他证明 停机问题 Halting Problem（试图评估程序是否最终会停止运行）是不可解决的。

Alan Turing进一步将系统定义为_Turing Complete_，如果它可以用来模拟任何图灵机。这样的系统被称为 通用图灵机 Universal Turing Machine（UTM）。

以太坊在一个名为以太坊虚拟机的状态机中执行存储程序，在内存中读写数据的能力，使其成为一个图灵完整系统，因此是一台通用图灵机。对于有限的存储，以太坊可以计算任何图灵机可以计算的算法。

以太坊的突破性创新是将存储程序计算机的通用计算架构与去中心化区块链相结合，从而创建分布式单状态（单例）世界计算机。以太坊程序“到处”运行，但却产生了共识规则所保证的共同（共识）状态。

图灵完备是一个“特性”

听说以太坊是图灵完备的，你可能会得出这样的结论：这是一个图灵不完备系统中缺乏的功能。相反，情况恰恰相反。需要努力来限制一个系统，使它不是 Turing Complete 的。即使是最简单的状态机也会出现图灵完备性。事实上，已知最简单的Turing Complete状态机（Rogozhin，1996）具有4个状态并使用6个符号，状态定义只有22个指令长。

图灵完备不仅可以最简单的系统中实现，而且有意设计为受限制的图灵不完备的系统通常被认为是“意外图灵完备的”。图灵不完备的约束系统更难设计，必须仔细维护，以保持图灵不完备。

关于“意外图灵完备的”的有趣的参考资料可以在这里找到： http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html

以太坊是图灵完备的事实意味着任何复杂的程序都可以在以太坊中计算。但是这种灵活性带来了一些棘手的安全和资源管理问题。

图灵完备的含义

图灵证明，你无法通过在计算机上模拟程序来预测程序是否会终止。简而言之，我们无法预测程序的运行路径。图灵完备系统可以在“无限循环”中运行，这是一个用于描述不终止程序的术语（过分简化地说）。创建一个运行永不结束的循环的程序是微不足道的。但由于起始条件和代码之间存在复杂的相互作用，无意识的无限循环可能会在没有警告的情况下产生。在以太坊中，这提出了一个挑战：每个参与节点（客户端）必须验证每个交易，运行它所调用的任何智能合约。但正如图灵证明的那样，以太坊在没有实际运行（可能永远运行）时，无法预测智能合约是否会终止，或者运行多久。可以意外，或有意地，创建智能合约，使其在节点尝试验证它时永久运行，实际上是拒绝服务攻击。当然，在需要毫秒验证的程序和永远运行的程序之间，存在无限范围的令人讨厌的资源浪费，内存膨胀，CPU过热程序，这些程序只会浪费资源。在世界计算机中，滥用资源的程序会滥用世界资源。如果以太坊无法预测资源使用情况，以太坊如何限制智能合约使用的资源？

为了应对这一挑战，以太坊引入了称为 燃气 _gas_的计量机制。随着EVM执行智能合约，它会仔细考虑每条指令（计算，数据访问等）。每条指令都有一个以燃气为单位的预定成本。当交易触发智能合约的执行时，它必须包含一定量的燃气，用以设定运行智能合约可消耗的计算上限。如果计算所消耗的燃气量超过交易中可用的天然气量，则EVM将终止执行。Gas是以太坊用于允许图灵完备计算的机制，同时限制任何程序可以使用的资源。

2015年，攻击者利用了一个成本远低于应有成本的EVM指令。这允许攻击者创建使用大量内存的交易，并花几分钟时间进行验证。为了解决这一攻击，以太坊必须在不向前兼容（硬分叉）的更改中改变特定指令的燃气核算公式。但是，即使有这种变化，以太坊客户端也不得不跳过验证这些交易或浪费数周的时间来验证这些交易。