首页 能链洞察 区块链百科

图灵完备 | 来自天才少年的三个思考

图灵完备 | 来自天才少年的三个思考

发布时间:2020.06.24

世界上是否所有数学问题都有明确的答案?

如果有,是否可以通过有限步骤的计算得到答案?

如果是,能否通过一种图灵机(即数学模型、计算理论模型),经过不断运行直到数学答案被计算出来?

 

——来自天才少年阿兰·麦席森·图灵在《论可计算数及其在判定性问题上的应用》三个思考。

 

一、图灵机与可计算问题

 

在理解图灵完备之前,我们先来理解图灵机的概念。

 

1936年5月,年仅24岁的英国数学家图灵发表了一篇题为《论可计算数及其在判定性问题上的应用》的论文。在此篇论文中,图灵提出一种假想的计算装置,后来被称为“图灵机”。而图灵机模型,则奠定了现代计算机的理论基础。

 

 
 

艾伦·麦席森·图灵(Alan Mathison Turing,1912年6月23日-1954年6月7日),英国数学家、逻辑学家,被誉为计算机科学与人工智能之父。有着“计算机界的诺贝尔奖”之称的“图灵奖”,便是为了致敬这位伟大的科学家。

1954年6月7日,图灵被发现死于家中的床上,床头放着一个被咬了一口的苹果。而今,人们还流传着苹果logo是为了纪念这位伟大科学家的美丽传说。

 

二、为什么要提出图灵机这个概念?

目的之一是为了回答德国数学家David Hilber在1928年提出的一个问题:可判定性问题。在逻辑中,如果某个逻辑命题是不可判定的,即表明对它的推理过程将一直运行下去,永远都不会停止。而在计算机理论视角下,如何判定哪些是“可计算”的,哪些是“不可计算”的,是否存在一种算法,输入形式化的逻辑语句(Formal Logic Statment),能够判断该命题的真假,并最终输出判断结果。

 

实际上,图灵机并不指具体的计算机,而是一种数学计算模型,用于解决任何可计算问题。比如说判断一个数是基数还是偶数,一加一等于几……这种能够通过计算得出结果的问题,图灵机都可以解决。那图灵机有没有解决不了的问题呢?比如说“今天晚饭吃什么”,这不是一个纯粹的可以计算的问题,图灵机就解决不了。因此对于一个问题,只要你能输入一些图灵机可以识别的数据,问题是可以计算的,图灵机就能给你一个结果。

 

如果不考虑速度,只考虑可计算性,迄今为止,人们提出的所有计算模型都能够用图灵机模型模拟。无论是算盘、手机、还是超级计算机等,都不能超越图灵机模型的计算能力。其实从某种意义上来说,“人”本身,也可抽象模拟为图灵机模型。

 

 

三、什么是图灵完备?

 

在图灵机的基础上,我们再来理解图灵完备。根据维基百科的解释:在可计算性理论里,如果一系列操作数据的规则(如指令集、编程语言、细胞自动机)可以用来模拟单带图灵机,那么它是图灵完备的。

 

简单来说,如果一门编程语言、一个指令集可实现图灵机模型里面全部的功能,或者说能够满足任意数据按照一定顺序计算出结果,我们就可称其具有图灵完备性。像平时使用的C、Java都是图灵完备的编程语言,可实现所有计算机能实现的功能。与图灵完备相反的就是图灵不完备,图灵不完备指不允许或限制循环,也就是可以保证每段程序都不会死循环,都有运行完的时候。

 

对区块链系统而言,图灵完备或者图灵不完备都是为了匹配不同的应用需求。在有些场景下,我们需要限制语言本身,以保证程序的终止性。例如,比特币的脚本语言就是图灵不完备的,它没有循环语句和复杂的条件控制语句,一定程度上保障了系统的安全性

 

而作为公有区块链平台,以太坊将比特币针对数字货币交易的功能进一步进行拓展,面向更为复杂和灵活的应用场景,支持了智能合约( Smart Contract)这一重要特性。从此,区块链技术的应用场景, 从单一基于 UTXO 的数字货币交易,延伸到图灵完备的通用计算领域。用户不再受限于仅能使用比特币脚本所支持的简单逻辑,而是可以自行设计任意复杂的合约逻辑。

 

也正是基于图灵完备性,区块链的系统为构建各种多样化的上层应用开启了大门。