来自天才少年的三个思考

世界上是否所有数学问题都有明确的答案？如果有，是否可以通过有限步骤的计算得到答案？如果是，能否通过一种图灵机（即数学模型、计算理论模型），经过不断运行直到数学答案被计算出来？

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

一、图灵机与可计算问题

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

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

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

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

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

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

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

三、什么是图灵完备？

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

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

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

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

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

本文来源：能链科技
原文标题：来自天才少年的三个思考

—-

编译者/作者：能链科技

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。