比特币史话·69 | 智能合约(4): 图灵完全吗？

(艾伦·图灵。图片来源于网络)

前情回顾：

正文：

艾伦·图灵，全名艾伦·麦席森·图灵(Alan Mathison Turing, 1912-1954)，英国数学家、计算机科学家、逻辑学家、密码分析师、哲学家和理论生物学家[1]。他深刻的影响了理论计算机科学的发展，他提出的“图灵机”(Turing machine)被认为是通用计算机最早的模型。他是理论计算机科学之父。他是人工智能之父，发明了检验人工智能是否已经有足够智慧能够骗过人类的“图灵测试”(Turing test)。有着“计算机界的诺贝尔奖之称”的计算机科学领域最高奖就是以他的名字命名的“图灵奖”(A.M. Turing Award)，由美国计算机协会(ACM)与1966年设立。

因为对计算理论包括伪随机数生成、密码学与通信复杂度的突出贡献而获得2000年图灵奖的姚期智先生，是该奖项迄今唯一华人得主。2017年2月，姚期智先生放弃外国国籍成为中国公民，正式转为中国科学院院士[2]。我们前文曾经介绍过的高德纳(Donald Knuth)，也曾获得过1974年图灵奖。(参见《比特币史话·14 | 哈希(1)》)[公众号:刘教链]

二战期间，图灵一度领导了负责德国海军密码分析的部门“Hut 8”，改进了战前波兰密码局破译德国著名的“恩尼格玛机”(Enigma machine)的方法。(有关于“恩尼格玛机”的那段历史，可以回顾一下《比特币史话·8 | 椭圆曲线(1)》) 由于图灵在破获拦截的德军密电方面的卓越贡献，据估计欧洲战场的战争时间因此缩短了2年以上，拯救了超过1400万人的生命。

战后，图灵设计了“自动计算引擎”(Automatic Computing Engine)，帮助研发了“曼彻斯特计算机”(Manchester computers)，还对“数学生物学”(mathematical biology)产生了兴趣。他发表了一篇关于“形态发生学”(morphogensis)的化学基础的论文，预言了振荡化学反应的存在。该预言在他死后6年的1960年被实验证实。他的论文启发了诺奖得主普利高津(Ilya Prigogine, 1917-2003)，后者因提出耗散结构理论而获得了1977年诺贝尔化学奖。普利高津在1977年于瑞典斯德哥尔摩所做的诺贝尔讲座中引用了图灵的论文并指出，“图灵分叉”(Turing bifucation)形成了系统的“历史”(history)，产生了不同于动力学时间和热力学时间的第三种时间，流淌在历史长河之中的时间。比特币区块链PoW算力竞争中的自发分叉，正是图灵分叉。(关于比特币区块链是“时间链”的有关历史，请参看《比特币史话·22 | 时间之矢(5)》)[公众号:刘教链]

1952年，根据1885年英国《拉布切雷修正案》(Labouchere Amendment)有关规定，图灵因同性恋行为被刑事起诉。为了免于坐牢，他被迫接受了化学阉割。1954年，图灵服用氰化物浸泡过的苹果自杀，享年41岁。他自杀的那一天，距离他42岁生日还有16天。

图灵短暂而辉煌的一生以一种令人扼腕的方式结束了，但是他给我们留下的影响却十分深远。他在1936年所发明的“图灵机”成为了计算机的一般模型。虽然图灵机只是一个由计算的数学模型所定义的抽象计算机，与我们真正制造和使用的、冯·诺伊曼架构的计算机(参看《比特币史话·48 | 左右互搏(3)》)相去甚远。图灵机的模型十分简单，就是根据一个规则表格操作一条无限长的纸带上的符号。但就是这么一个简单的计算机模型，图灵证明它足以表达所有我们能够构造出来的算法。而我们今天所用的计算机，就是图灵机的一种模拟(毕竟，真实的计算机不是无限的)。[公众号:刘教链]

(图灵机。图片来源于网络)

于是，我们就把图灵机作为一种计算能力的判定标准。一个计算机系统，如果能够模拟出图灵机，那么我们就把这称之为“图灵完全”(Turing completeness)。一门计算机编程语言，如果是图灵完全的(Turing complete)，那么这门编程语言就在理论上足以编码出任何计算机能够做到的任务。

比特币脚本也是一门编程语言。可是，比特币脚本不是图灵完全的。这究竟是中本聪的故意，还是中本聪的失误？我们这就来一探究竟。

【未完待续】(公众号：刘教链)