最近在看关于区块链的资料时经常出现一个词——“图灵完备”，在以太坊发布的白皮书中，明确指出“以太坊协议的全部复杂性均来自于一门通用的图灵完备的脚本语言”，那到底什么是图灵完备，它和图灵机又是什么关系，图灵机又能解决什么问题？本文就结合笔者的理解和认识做一下简单的梳理，希望能进一步加深对图灵提出的相关概念的认识与理解。
相信很多人对“图灵测试”这个词并不陌生，它的知名度不亚于其提出的信息论中熵的概念，比较通俗一点的定义就是测试者与被测试者（一个人和一台机器）隔开的情况下，通过一些装置（如键盘）向被测试者随意提问。进行多次测试后，如果有超过30%的测试者不能确定出被测试者是人还是机器，那么这台机器就通过了测试，并被认为具有人类智能。
在吴军博士的《智能时代》一书中，也列举了图灵智能的5大应用领域，有兴趣的朋友推荐阅读一下：
1、语音识别
2、机器翻译
3、文本的自动摘要或写作
4、战胜人类的国际象棋冠军
5、自动回答问题
先说一下什么是图灵机，图灵机是基于图灵测试的思想设计出的一个设想，准确的说是一个数学模型，1936年图灵发表的《论可计算数及其在判定性问题上的应用》一文中被首次提及。论文中还证明了只要图灵机可以被实现，就可以用来解决任何可计算问题。
图灵机的结构主要包括如下几个部分：
1.一条无限长的纸带（tape），纸带被分成一个个相邻的格子（square），每个格子都可以写上至多一个字符（symbol）。
2.一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符。
3. 一个读写头（head），可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容，此外也可以每次向左/右移动一个格子。
4. 一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行/终止）。当这个状态从运行变为终止，则运算结束，机器停机并交回控制权。如果你了解有限状态机，它便对应着有限状态机里的状态。
5. 一个有限的指令集（instructions table），它记录着读写头在特定情况下应该执行的行为。可以想象读写头随身有一本操作指南，里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时，擦除，改写为1并向右移一格。此外，令下一状态为运行。”这样的命令。其实某种意义上，这个指令集就对应着程序员所写下的程序了。
在计算开始前，纸带可以是完全空白，也可以在某些格子里预先就有写上部分字符作为输入。运算开始 时，读写头从某一位置开始，严格按照此刻的配置（configuration），即：
当前所处位置
当前格子内容
来一步步的对照着指令集去进行操作，直到状态变为停止，运算结束。而后纸带上留下的信息，即字符的 序列（比如类似“...011001...”）便作为输出，由人来解码为自然语言。
那图灵机能干什么呢?如果图灵机能被以某种形式物理实现，任意可计算问题都可以被解决，所谓的计算问题泛指一切与计算有关的问题，比如：
给定一个整数，判断其是否为合数
给定一个字符串系列，对其进行排序或查找某个字符的所在位置
给定一个逻辑命题，求它的逆否命题
而下面的问题就不是计算问题：
你今天心情不好么
太阳从西边出来了吗
而并不是所有计算问题都可以被解决的，这就引出了可计算性的概念，与其等价的一个比较通俗易懂的说法：是否存在一个算法，能解决在任何输入下的此计算问题。
比较官方但是还比较易懂的定义：
图灵完备性（Turing Completeness）是针对一套数据操作规则而言的概念。数据操作规则可以是一门编程语言，也可以是计算机里具体实现了的指令集。当这套规则可以实现图灵机模型里的全部功能时，就称它具有图灵完备性。它是对计算能力的描述。
如何理解一门语言具有图灵完备性呢？一台计算机也是一个图灵机，一个图灵完备的语言意味着这个语言可以使用计算机完成任何计算机可以完成的任务，也就能够发挥计算机的所有能力。反之，一个图灵不完备的语言，就意味着不能发挥计算机的所有能力。
附，以太坊白皮书的片段：
- 上一篇： 《琅琊榜之风起长林》的三句话
- 下一篇： 带宽和稀缺心理——解决稀缺问题的关键
评论
访客
回复需要学习的东西太多了
访客
回复已阅~