[书籍分享]图灵完备——《区块链社会》节选（十二）

本文节选自《区块链社会-解码区块链全球应用与投资案例》，本书由中信出版社出版。通过对区块链社会蓝图的勾勒和细致描绘，分析了最真实的区块链全球应用与投资案例，对区块链的投融资数据、法律监管及对未来产生的影响进行了深入阐释。目前在京东、当当、亚马逊和淘宝等电商平台均有出售，更多精彩知识敬请期待。

作者：龚鸣（暴走恭亲王）

伴随着智能合约概念，我们经常可以听到另外一个词句，就是“图灵完备”。经常有支持智能合约的平台，声称自己编写智能合约的语言是“图灵完备”的。

严格来说，对于虚拟机或者计算机语言而言，在可计算理论中，当一组数据操作的规则（一组指令集，编程语言，或者元胞自动机），在满足任意数据和按照一定顺序的情况下，都可以计算出结果，被称为图灵完备（turing complete）。

一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的，它（计算机设备）有能力执行条件跳转（“if” 和 “goto”语句）以及改变内存数据。如果某个东西展现出了图灵完备，它就有能力表现出可以模拟原始计算机，而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的（C++ template就是图灵完备的），都能解决内存有限的问题。图灵完备的机器都被定义有无限内存，但是机器指令集却通常定义为只工作在特定的，有限数量的RAM上。

简单地说，一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。一个语言是图灵完备的，意味着该语言的计算能力与一个通用图灵机（Universal Turing Machine）相当。虽然图灵机的概念很简单，但这是现代编程语言所能拥有的最高计算能力。

作者：龚鸣（暴走恭亲王） | 来源：Chainb