以太坊和图灵完备性

以太坊和图灵完备性

一旦开始阅读有关以太坊的内容以太坊是个什么，您就会立即听到“图灵完备”一词。 他们说，与比特币不同，以太坊是“图灵完备的”。 这到底是什么意思？

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

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

以太坊能够在称为以太坊虚拟机的状态机中执行存储的程序，并在内存中读取和写入数据，使其成为图灵完备系统，从而成为通用图灵机。 对于有限的存储空间，以太坊可以计算图灵机可以计算的任何算法。

以太坊的突破性创新是将存储程序计算机的通用计算架构与去中心化的区块链相结合，打造分布式单态（singleton）世界计算机。 以太坊程序“无处不在”运行，但会产生一个由共识规则保证的共同（共识）状态。

图灵完备性是一个“属性”

听到以太坊是图灵完备的，您可能会得出结论，这是图灵不完备系统所缺乏的功能。 反之，则相反。 需要努力来约束系统，使其不是图灵完备的。 即使是最简单的状态机也会出现图灵完备。 事实上，已知最简单的图灵完备状态机（Rogozhin，1996）有 4 个状态并使用 6 个符号，状态定义只有 22 条指令长。

不仅可以在最简单的系统中实现图灵完备，而且故意设计为限制图灵不完备的系统通常被称为“意外图灵完备”。 图灵不完备的约束系统更难设计，必须小心维护以保持图灵不完备。

可以在此处找到有关“意外图灵完备”的有趣参考：

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

图灵完备性的含义

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

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

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