比特币的图灵完备性

如果您不能理解比特币的脚本系统,就不能理解中本聪对比特币的设计,就看不到比特币功能最强大的部分,也就领悟不了中本聪的那句话:“The nature of Bitcoin is such that once version 0.1 was released, the core design was set in stone for the rest of its lifetime”(比特币的性质是这样的,一旦 0.1 版本发布,其核心设计在其整个生命周期中都是一成不变的)。

如果不明白比特币的脚本是图灵完备的,又怎能理解彻底比特币脚本系统?

一、图灵机 Turing Machine 基础知识

图灵机是英国数学家艾伦 · 图灵于 1936 年提出的一种抽象计算模型。图灵提出图灵机的时候,世界上还不存在电子计算机。图灵都是用笔和纸解决这些问题的。所以,本质上,图灵机和图灵完备,都是数学问题。

图灵机,可以从上图的简单模型开始来理解。简单的图灵机,包括下面四个部分:

  • 单向无限长的纸带,纸带上面有一个个存储用空格子,每个空格可以写字符如 {‘0’,‘1’} 或者空格。
  • 一个读写头,读写头每次可以左或者右移动一格,或者不动,这个读写头可以在纸带的空格上读、写 / 修改字符。
  • 状态存储器,记录图灵机当前的状态。有一个初始状态,还有一个特殊的状态,是停机状态。
  • 控制操作的规则,也就是程序指令。根据图灵机当前的状态,以及读写头读到的字符,确定读写头的动作,左移一步,还是右移一步,或停止不动。并可改变图灵机的状态,是进入一个新状态,还是保持不变。

图灵机虽然简单,但是它可用来解决任何可计算问题。图灵机有很多种,但是任何二种之间,如果能够相互模拟,则二者是等价的。

图灵完备 Turing completeness

这是可计算性理论的概念,如果一系列操作数据的规则(如编程语言)可以模拟出图灵机,那么它是图灵完备的。

图灵完备是一个理论上的概念,它是假定有无穷的存储空间的,并且不管计算的效率。

凡是图灵完备的语言,它们之间描述问题、解决问题的能力,理论上说是等价的。比如,比特币脚本与 C/C++ 的语言能力是等价的。

图灵停机问题

图灵停机是一个难题,而且与比特币、区块链密切相关。凡是图灵机、图灵完备的程序语言,都有图灵停机的难题。

停机问题,通俗地说,就是对任意一个程序,对任意的输入数据,能否事先判断出程序是否会停止运行?

结论是否定的,即不可能存在这样的方法,能够事先判断出来。

对于区块链上的智能合约而言,智能合约是任意人部署的,即程序是任意的;智能合约的触发,是任意用户发数据、交易等触发的,即输入数据是任意的。所以,智能合约运行后,能否停止,是无法预先判断的。

与比特币区块链的关系

比特币中,是有脚本指令系统。由于比特币的脚本中,没有循环结构(语句),在很长的时间里,人们都认为比特币脚本不是图灵完备的。世界上只有一个人知道比特币脚本是图灵完备的,那就是中本聪。而且比特币的脚本,是特地设计成没有循环语句的。

由于人们都错误地认为,比特币脚本不是图灵完备的,语言解决问题的能力有限。而实际上,比特币脚本是比特币最强大的功能。这点被误解后,人们就根本理解不了中本聪设计比特币的原意。

为什么比特币脚本语言,是图灵完备的?后面文章有详细的介绍。

以太坊、EOS 的智能合约

以太坊

以太坊最初目标是实现一台链上计算机,运行智能合约,它需要图灵完备的语言。以太坊开发智能合约的语言 solidity 确实是图灵完备的,它有循环语句。

以太坊的智能合约,不可避免地遇到了图灵停机的难题。它无法预先知道智能合约运行起来后,是否会停止?而智能合约不能停机,则所有的矿工机器,在运行的时候,都可能会死循环,永远出不来了。这对区块链是致命的,也就是链死在那里了。平常普通电脑在死机的时候,一般是断电、开机重启,又可以重新使用电脑。但是,区块链没有中心控制点,也无法断电。智能合约死循环,链就死掉了。

以太坊为了解决这个问题,特地推出一个附加资源限制,Gas(汽油)。运行智能合约需要耗费 Gas,Gas 用完了,智能合约必须停止。以太坊的智能合约,成千上万的矿机都需要运行相同的智能合约;而矿机运行智能合约,每运行一步(或者计算单元),都需要检查还有 Gas 没有,有则继续运行,没有就停机。所有的以太坊的矿机,都要不断地检查是否还有足够的 Gas?这个方法好像是挺笨拙的。

也有人说,以太坊的智能合约不是图灵完备的,因为它有 Gas 限制。其实这个说法是颠倒了因果。以太坊智能合约是梦想拥抱图灵完备的,但是图灵停机难题,它没有办法才用 Gas 的。

事实上,以太坊的 Gas,也是以太坊性能的恶梦之一。

EOS

EOS 设计之初,就是对标以太坊的,当然支持图灵完备的智能合约。EOS 的智能合约,也面临着图灵停机的难题。

EOS 解决停机问题,是用 CPU 时间资源来约束智能合约的运行。每个运行智能合约的账户,根据事先抵押的 EOS 数量,分配相应的 CPU 时间。EOS 的矿工节点很少,只有 21 个超级节点产生区块。但是,这 21 个节点,都需要运行相同的智能合约。一样的,节点每运行一步智能合约,都需要去检查 CPU 时间是否还有?有则继续运行,没有就停机。跟以太坊是类似的,这个停机的方法也是挺笨拙的。

EOS 的 CPU 处理瓶颈,也成为 EOS 性能的恶梦之一。

是不是很类似?目前很多所谓的区块链和币,它们都是照抄了以太坊,或者是 EOS 的智能合约实现方法。都会面临着同样的停机难题。它们配得上称为所谓区块链 2.0,3.0,4.0 吗?

中本聪的方案

看过了以太坊、EOS 智能合约的停机方法和遇到的问题,就明白了这一切早就在聪哥的预料之中。小样,你以为聪哥不会简单地给比特币脚本添加循环语句,就实现了图灵完备?

聪哥既要比特币脚本功能相当于图灵完备,又要避免麻烦的停机问题。 而且在比特币中,矿工收取矿工费用,是按照区块大小收矿工费的。如果有循环语句,一段指令,循环了一万次,跟只执行一次,代码大小是一样的,收取矿工费是一样的;但是耗费矿工的资源却是差别很大的,对矿工不公平。

聪哥设计的比特币脚本是有二个堆栈,可以实现递归函数调用。递归方法类似于循环语句。但是,比特币脚本实现智能合约之类的程序 ,是把所有的递归(循环)展开,以增大程序的体积为代价,消除了递归(循环),得到的脚本程序必然会停机。智能合约的编译器,在生成比特币脚本指令程序的时候,会有一个程序体积的上限。太大的程序编译时都会报错,不能生成程序。那些不能停机、无限死循环的程序,生成的程序体积必然是无穷大,编译器就会报错,编译器把不能停机的有害程序,提前给拦截下来了。要实现这一点,需要比特币的区块足够大,因为比特币脚本指令的程序也会很大的!

由此可知,比特币的脚本系统设计,根本不是水平差,而是神来之笔!中本聪团队中,有英国的数学家 David Rees。David Rees 教授,年轻的时候,是跟着艾伦 · 图灵一起做项目的。所以中本聪团队,能够对图灵机、图灵停机等理论问题,理解这么深刻。

当然,本文中说的比特币,是指 Bitcoin SV。BTC 以及其它的分叉币,没有这个图灵完备的能力。

二、基础数学知识

先补充一些基础数学知识。

递归函数

后继函数

S(x) = x+1

非负整数集

$$ \mathbb{N}_0={{0,1,2,3...}}

$$

加法定义

add(x,0) = x
add(x,S(y)) = S( add(x,y) )

例如,通过加法计算 2+2=4 :

add(2,2) = S( add(2,1) )
         = S( S( add(2,0) ) )      add(2,0) = 2
         = S( S(2) )
         = S(3)
         = 4

三个基本函数

三个基本函数如下:

$$ \begin{align} &1. 零函数 \quad Z(x)\equiv0.\ &2. 后继函数 \quad S(x)\equiv x+1\ &3. 投影函数. 一个投影函数,就是选出它的某个变量。\ &\quad 特别地,如下面的函数,从二维平面,投影到一维的坐标轴上:\ &\quad P_1(x,y)\equiv x \quad P_2(x,y)\equiv y \end{align}

$$

组合运算

有两种操作,可以从旧的函数创建新的函数:组合运算和原始递归

组合,就是将一个函数的变量,用另外一个函数来替换。例如,可以用下面的方式来定义函数 f

$$ f(x,y)=g(h_1(x,y),h_2(x,y))

$$

$$ 用函数 g,h_1,h_2 来定义函数 f

$$

原始递归

原始递归的典型形式如下:

$$ \begin{align} &f(x,0)=g_1(x)\ &f(x,S(y))=h(g_2(x,y),f(x,y))\ & 用函数 g_1,g_2 和 h 来定义 f \end{align}

$$

例如,在加法函数中,h 就是后继函数,并且投影到第二个变量上面。

更多的原始递归

一种特殊情况的原始递归,对于某些常数 k:

$$ \begin{align} &f(0)=k\ &f(S(y))=h(y,f(y)) \end{align}

$$

原始递归函数
一个函数是原始递归的,如果它能够用基本的函数,以及组合运算和原始递归等操作来构造,那么这个函数就是原始递归函数。

原始递归函数是图灵可计算函数

组合和原始递归运算保留了可计算的特性,可计算是指图灵机可计算。因此:

事实.    一个原始递归函数是图灵可计算的。

例子:乘法

$$ \begin{align} &mul(x,0)=0\ &mul(x,S(y))=add(x,mul(x,y)) \end{align}

$$

现在我们已经展示了加法和乘法都是原始递归的,对这些函数我们可以使用正常的算术符号表示。

例子:减法和 Monus

减法更加困难,因为结果要保留在非负整数集中。

$$ 非负整数集 \quad \mathbb{N}_0

$$

因而定义一个 “尽可能地减” 的运算,叫做 monus。

$$ monus 写作 ∸ ,定义如下:\ x ∸ y = \left{\begin{matrix} & x-y \quad 如果 \quad x\geq y \ & 0 \quad 其它
\end{matrix}\right.

$$ monus 作为一个原始递归函数,要用公式表示的话,这里需要前继。

例子:前继

$$ \begin{align} & pred(0) = 0\ & pred(S(y)) = y\ \end{align}

$$

练习

下面展示 monus 是一个原始递归。

$$ \begin{align} & monus(x,0) = x\ & monus(x,S(y)) = prev(monus(x,y))\ \end{align}

$$

例子:谓词

如果一个函数,仅仅取值 0 和 1,可以看作是一种谓词(predicate)。其中 0 表示假,1 表示真。

例如,一个识别 0 的函数,它对参数0取值为1;而对 0 之外的其它值则相反,取值 1。

$$ \begin{align} & sgn(0) = 1\ & sgn(S(y)) = 0\ \end{align}

$$ 即:

sgn(S(y)) = sgn(y+1) = 0    0 之后的所有参数,都取值 0
例子:用例定义

$$ f(x) = \left{\begin{matrix} & g(x) \quad 如果 \quad p(x) \ & h(x) \quad 其它的情况 \ \end{matrix}\right.

$$

可以确定,如果 g 和 h 是原始递归函数,则 f 也是原始递归函数。一种理解这点的方式,是写成代数式:

$$ f(x) \equiv g(x)p(x)+(1-p(x))h(x)

$$

练习:

请展示:如果 p(x) 和 q(x) 都是原始递归谓词,那么 $p\land q$ (它们的“与”,或者说“并且”) 定义为真,当且仅当 p(x) 和 q(x) 都为真。

$$ p \land q = p(x) \times q(x)

$$

不是原始递归的函数

== 定理 == 不是所有图灵可计算的函数,都是原始递归的。

这里采用(康托尔)对角线论证法。每一个部分递归函数,都由有限字符串给出。因而,可以给它们编号 $f_1,f_2 ...$ 定义一个函数 g 如下:

$$ g=f_x(x)+1

$$ 这样的 g 是一个完美的可计算函数。但是它不可能是原始递归的:它跟每一个原始递归函数都不一样。

阿克曼函数(Ackermann)

阿克曼函数是一个著名的函数,但是它不是原始递归的。阿克曼函数定义如下:

$$ \begin{align} & A(0,y) = y+1\ & A(x,0) = A(x-1,1)\ & A(x,y+1) = A(x-1,A(x,y)) \end{align}

$$ 下面是这个函数比较小的一些值:

A(0,1) = 1+1 = 2
A(1,0) = A(0,1)=2

A(1,1) = A(0,A(1,0)) = A(0,2) =3
A(1,2) = A(0,A(1,1)) = A(0,3) =4

A(2,0) = A(1,1) = 3
A(2,1) = A(1,A(2,0))= A(1,3) = A(0,A(1,2)) = A(0,4) = 5

练习 A(2,2)

A(2,2) = A(1,A(2,1)) = A(1,5) = A(0,6) = 7
有界和无界最小化

假如 q(x,y)是一些谓词。一个操作叫做有界的最小化。对于一些固定的 k:

$$ f(x) = min{\,y \le k: q(x,y)}

$$ 这里,在没有 y 的情况下,必须要处理那些 x 。使得谓词 q(x,y)为真,且不大于 k 的 y 值;取最小的那个 y 值。

实际上,有界最小化只是 case 语句的一种扩展(相当于 k-1 嵌套的 case 语句)。因而,如果 f 是从原始递归谓词开始,通过有界最小化组成的,那么 f 也是原始递归的。

无界最小化

我们定义

$$ f(x)=\mu \, q(x,y)

$$ 意思是,f(x)是使得谓词 q(x,y)为真的最小的 y 的值。而谓词 q(x,y)为假时,f(x)=0。

$$ 定义 \ 一个函数是 \mu - 递归的,如果这个函数可以用基本函数、组合操作、原始递归和无界最小化等建立起来。

$$

$\mu - 递归函数 $

不难验证,所有这些函数,都可以由某些图灵机计算。其更深层次的结果是:每一个图灵可计算函数,都对应一些 $\mu - 递归函数 $ 。

$$ 定理:\, 一个函数是图灵可计算的,当且仅当它是 \mu - 递归的

$$

总结

一个原始递归函数,是由基本函数零、后继函数、投影函数使用 2 个操作,组合操作和原始递归,建造的。有一些图灵可计算函数却不是原始递归函数,例如阿克曼函数。

二、学习比特币脚本

Learning Script ,Craig Wright 博士

原文链接:https://medium.com/@craig_10243/learning-script-20303a5f867e

递归的基础,来自于下面的六个函数。比特币脚本指令 OP_ADD 和 OP_1ADD,分别封装了下面的第 4 和第 2 个函数。第六个函数,可以用乘法指令 OP_MUL 完成。下面只剩下 “尽可能地减” 函数 Monus、Characteristic function(特征函数)和 Identity functions(恒等函数)。后面将会介绍这些函数。

OP_ADD a b        把 a 的值,添加到 b 上面去        
OP_1ADD            这个指令把 1 加到输入(变量)上去
OP_MUL a b        把 a 的值与 b 相乘,结果保存在变量 b 中

根据哥德尔(Godel)的公理,所有可以决定的数学(因而,我们可以说,任何在科学,工程和金融中使用的东西)可以使用以下六(6)个函数构造来解决。

$$ \begin{align} &1. \, C_A(x) \qquad \qquad \qquad \qquad \qquad \qquad 这表示 A 的特征函数 \ &2. \, S(x)=x+1 \qquad \qquad \qquad \qquad \quad 后继函数 \ &3. \, U^n_i(x_i,...,x_n)=x_i, \quad 1 \le i\le n. \, 恒等函数 \ &4. \, x+y \ &5. \, x∸y \qquad \qquad \qquad \qquad \quad \qquad \quad \, Monus 函数 \ &6. \, x.y \ \end{align}

$$ 这六个函数就是原始函数,通过使用递归函数,来表征可计算特性。

乘法函数:

OP_MUL 覆盖了第六个函数 x.y

对比特币指令'a b OP_MUL' ,a 乘到 b 上

后继函数:

第二个函数很简单,可以用指令 OP_1ADD 覆盖。后继函数用来形成无限’格尔泽戈茨兹克‘(Grzegorczyk)超运算的层次结构,后继函数是其 0 级基础。这样就可以构建数学函数,它们包括加法,乘法,取幂,迭代幂次和函数。

加法:

OP_ADD 覆盖了第四个函数。

比特币指令 ’a b OP_ADD‘,a 加到 b 上。

Monus(尽可能地减)函数

今天,我将从认真地使用 Monus 函数开始。

它计算截止减法。当我们计算它时就知道,我们将不会得到负的返回值。在创建数学函数和编译器时,它是一个非常有价值的函数。

$$ a ∸ b = \left{\begin{matrix} & 0 \qquad \quad 如果 \quad a < b \ & x-y \quad \, 如果 \quad a\geq b \ \end{matrix}\right.

$$ 下面是用比特币的脚本指令,来实现 Monus 函数的例子。

值 1 值 2 指令 堆栈 ALT 堆栈 说明
A OP_PUSHDATA(x) A A 被压入堆栈 - x 可以是 1,2,4。意思是三个指令都可以
OP_IFDUP AA 如果 A 的值不为空,复制它。这是一个好的检查,来防止出错。
OP_TOALTSTACK A A A 被压入 ALT 堆栈。是从主堆栈移过来的。
B OP_PUSHDATA(x) BA A B 被压入堆栈 - x 可以是 1,2,4。
OP_IFDUP BBA A 如果 B 的值不为空,复制它。
OP_TOALTSTACK BA BA B 被压入 ALT 堆栈。
OP_LESSTHANOREQUAL 真, 如 A>=B, 假,其它 BA 如果 A 大于等于 B,将继续;或者返回 0。注意,这里形式上与指令相反了,指令是从 B 比较 A 的。
OP_IF <真> BA 栈顶的值不为假,语句被执行。栈顶的值被移除。
OP_FROMALTSTACK B A 将输入值移到主栈顶。并从 ALT 栈顶移除。
OP_FROMALTSTACK AB 将输入值移到主栈顶。并从 ALT 栈顶移除。
OP_SUB (A-B) 返回(A-B)
OP_ELSE <假> BA 前面 if 语句的 else 部分
OP_FROMALTSTACK B A
OP_FROMALTSTACK AB
OP_DROP B 删除栈顶元素 A
OP_DROP 删除栈顶元素 B。此时清空了主堆栈
OP_0 0 一个空的字节数组被压入堆栈,即 0
OP_ENDIF if 语句的结束标志。所有语句块必须结束,否则事务无效

上面的比特币指令,实现了下面的数学运算

结果
如果 A>=B A-B
如果 A<B 0

注释:OP_PUSHDATA(x)是指,x=1,2,4 时,分别是下面 3 条脚本指令

指令 输入 输出 说明
OP_PUSHDATA1 后面的一个字节 数据 后面的那个字节,表示压入堆栈中的数据长度,最多 256 个。
OP_PUSHDATA2 后面的二个字节 数据 后面的 2 个字节,表示压入堆栈中的数据长度,最多 64KB。
OP_PUSHDATA4 后面的四个字节 数据 后面的 4 个字节,表示压入堆栈中的数据长度,最多 4GB。

我已经扩展了一个比下面真正需要的更详细的脚本。

值 1 指令 堆栈 ALT 堆栈
A OP_PUSHDATA(x) A
OP_IFDUP AA
OP_TOALTSTACK A A
B OP_PUSHDATA(x) BA A
OP_IFDUP BBA A
OP_TOALTSTACK BA BA
OP_LESSTHANOREQUAL 真, 如 A>=B, 假,其它 BA
OP_IF <真> BA
OP_FROMALTSTACK B A
OP_FROMALTSTACK AB
OP_SUB (A-B)
OP_ELSE <假> BA
OP_FROMALTSTACK B A
OP_FROMALTSTACK AB
OP_DROP B
OP_DROP
OP_0 0
OP_ENDIF

Monus 函数遵循如下的运算规律:

    a + (b∸a) = b + (a∸b)
    (a∸b) ∸ c = a ∸ (b+c)
        (a∸a) = 0
        (0∸a) = 0

更加重要的是,我们可以保存其他函数,并调用它们以便加载到 Monus 函数中。

$$ \begin{align} & monus(x,0)=x \ & monus(0,y)=0 \ & monus(s(x),s(y))= monus(x,y) \ & 其中,s(x)表示后继函数,即 x 后面的那一个数 \end{align}

$$ 注意我们怎样将函数合并到函数中。

值 1 指令 堆栈 ALT 堆栈 说明
A OP_PUSHDATA(x) A A 被压入堆栈 - x 可以是 1,2,4。意思是三个指令都可以
OP_1ADD S(A) S(A)=A+1
OP_IFDUP S(A)S(A) 如果 S(A)的值不为空,复制它。这是一个好的检查,来防止出错。
OP_TOALTSTACK S(A) S(A) S(A)被压入 ALT 堆栈。是从主堆栈移过来的。
B OP_PUSHDATA(x) BS(A) S(A) S(A)被压入堆栈 - x 可以是 1,2,4。
OP_1ADD S(B)S(A) S(A) S(B)=B+1
OP_IFDUP S(B)S(B)S(A) S(A) 如果 S(B)的值不为空,复制它。
OP_TOALTSTACK S(B)S(A) S(B)S(A) S(B)被压入 ALT 堆栈。
OP_LESSTHANOREQUAL 真, 如 S(A)>=S(B), 假,其它 S(B)S(A) 如果 S(A)大于等于 S(B),将继续;或者返回 0。注意,这里形式上与指令相反了,指令时从 S(B)比较 S(A)的。
OP_IF <真> S(B)S(A) 栈顶的值不为假,语句被执行。栈顶的值被移除。
OP_FROMALTSTACK s(B) S(A) 将输入值移到主栈顶。并从 ALT 栈顶移除。
OP_FROMALTSTACK S(A)S(B) 将输入值移到主栈顶。并从 ALT 栈顶移除。
OP_SUB [S(A)-S(B)] 返回(A-B)
OP_ELSE <假> S(B)S(A) 前面 if 语句的 else 部分
OP_FROMALTSTACK S(B) S(A)
OP_FROMALTSTACK S(A)S(B)
OP_DROP S(B) 删除栈顶元素
OP_DROP 删除栈顶元素。此时清空了主堆栈
OP_0 0 一个空的字节数组被压入堆栈,即 0
OP_ENDIF (A-B)如果真,否则 0 if 语句的结束标志。所有语句块必须结束,否则事务无效

在这里,我们扩展了前面的结果以计算 Monus[S(x),S(y)]函数。我们当然可以使用任何函数扩展,与此进行比较。

还有更高效的方法来计算 Monus。我将把这些计算留给读者。

$$ MONUS(x,y) = \left{\begin{matrix} & 0 \qquad \qquad 如果 \quad x \le y \ & flip(flip(x)+y) \quad \, 其它 \ \end{matrix}\right.

$$ 这样,MONUS(x,y)计算通常的截止减法 x ∸ y,使用了两个补充的技巧。

注释: flip(x)没有找到定义。应当是,flip(x)=-x, flip(x)+y = y-x
                               flip(flip(x)+y) = flip(y-x) = x-y
      flip(x)就是这里用来扩展的函数。

定义 MSP 函数如下:

$$ \begin{align} & MSP(0,k)=0 \ & MSP(si(x),k)= s{Bit(k,s_i(x))}(MSP(x,k)) \ \end{align}

$$

三、比特币:一个完全的图灵机

Bitcoin: A Total Turing Machine ,Craig Wright 博士

原文链接:https://medium.com/@craig_10243/bitcoin-a-total-turing-machine-5a6c3c68f5a7

今天我发布了一份 2014 年就开始写的一篇论文草稿 “Bitcoin: A Total Turing Machine” 。文章可以从 SSRN 网站下载。这里是一个介绍。 如果您想了解更多信息,请下载全文。

Bitcoin: A Total Turing Machine

我们证明比特币脚本语言不仅允许原始递归,而且在部署阿克曼 (Ackerman) 函数的过程中,能够简单地在比特币脚本中进行递归,我们证明了脚本系统是图灵完备的。由此,我们介绍一类新的图灵机,PTTM 或概率的完全图灵机。并注意到比特币可担任一个决策者,或完全图灵机,它使得我们找到 NIZKPoK,可以作为基于图灵机的验证器,作为非交互式证明,在外部和非关联图灵机上作为证明系统运行。比特币扩展后可以安全地提供合同,例如最适合常见物流系统的解决方案,一些优化类的问题,包括旅行推销员类问题和系统优化。这可以作为开放的或有时限的合同提供,以保证付款;并且可以解决,允许投标人用假名的问题。

一,导言

在本文中,我们展示了比特币的脚本系统,如何构成了基础,形成一种特殊类型的图灵机的,称为决策者(Sipser,1996)或者完全图灵机(Kozen,1997)。这是一类图灵机,可以在任何输入下停机。

图灵机

任何程序是图灵完备的,都必须是有限的。尽管您无法决定一个程序是否会停止,但任何图灵完备的程序都将按照定义停止。任何确实会停止的程序,本质上必须具有小于无限的终止点,因为能停止的最大可能的程序,总是(本质上)小于所有程序的最大集合。我们可以简单地从中推断出,所有 UTM[A1](通用图灵机)都在有限的时间内运行(尽管这个时间仍然无具体限制),我们无法事先告知一个程序是否实际上是可判定的。

在(Wright,2016)中,我们证明了部署在比特币中的脚本系统,是使用原始递归函数构成的(Meyer 和 Ritchie,1967)。在(Wright,2017)中,我们扩展了这个 [A2] 理论,来创建一个玩具编程语言,类似于 Brainerd 和 Landweber(1974)的 PL- {GOTO},因此证明了脚本构造是图灵完备的(忽略了真实世界中,脚本限制和大小的约束)。这种脚本的最简单用法,是开发简单的决策树函数。我们证明这些可以使用随机组件进行合并,以随机化并公平地分配可能的输出结果。

这种系统 [A3] 的功能(和优势),可以尽量地发挥在开发可扩展的编译器中,这些编译器采用高级递归构造(例如 OP_ForLoop [1]),并 “展开” 这些构造。在这个系统中所表达的语言种类,镜像了递归的语言集。众所周知,所有的原始递归函数都是完全可计算的。在本文中,我们还演示了使用阿克曼 (Ackermann) 函数,比特币脚本可构造出阿克曼函数;比特币脚本构造包括扩展到非原始递归的完全可计算函数的能力。这表明比特币可以包含完全可计算函数,这些函数可以是简单“递归的”,也可以是原始递归的。

这些结果的后果是,比特币系统不受最初故意施加的脚本语言限制之约束。从它最初的设计构想出发,比特币脚本语言旨在实现高度复杂的功能,而不仅仅是简单的价值转移。省略循环语句是特意设计的,旨在防止拒绝服务(DOS)攻击无限循环。遗憾的是,故意删去循环语句,导致许多观察者认为比特币“不是图灵完备”,因此它无法执行的功能,将使其不适合作为通用编程系统。这个断言是不正确的。本文扩展了早期的论文(Wright,2017),证明比特币适用于所有实际目的图灵完备(事实上,正如其他一些观察家所说,“图灵完备性是理论上的,在实践中没有图灵完备”[2])。因此,对其执行复杂功能的能力没有实际限制,例如执行智能合约和实施分布式自治公司(DACs)。在本文中,我们也研究了比特币如何满足相关概念的实现要求,如完全图灵机(TTM)和概率的完全图灵机(PTTM)。

二、完全图灵机[A4]

关于图灵机的性质和这种系统的能力,存在许多误解。图灵机可以解决一类称为λ- 可定义函数的 “有效可计算” 函数。

首先,我们将图灵完备程序定义为:任何图灵完备程序都是会停止运行的程序。虽然我们无法事先确定,任何特定程序是否在输入任意数据集时,都会停止运行。我们确实知道,一个程序在图灵完备的系统上必须能停止,如果它确实是可判定的;并且知道只有可判定的程序,在图灵完备系统上运行到完成。因此,我们知道必然有一个点,可判定程序跑到那个点会停止运行。

结果是所有可判定的程序,必须在一些时间有界的有限周期内停止。我们也可以说,没有可判定的程序,可以无限地运行在图灵完备系统上;或者,当在图灵完备系统上加载时,所有可判定程序都是有限的。由此我们可以推断出,所有图灵完备程序和函数构成了所有可能程序集的一个子集。所有可能程序的集合,既包括那些在图灵机上会停止的程序(可判定的),也包括那些无限循环运行而不终止的程序。我们可以证明,无限和不可判断的程序集不是空集。构建一个无限期地在无限磁带上运行的程序,是一个简单的练习。这样一个程序,给予无限时间运行,将永远不会停止。这里留给读者,来想象一个能够无限递归的简单程序(即永不停止)。由此,我们现在知道,所有程序集 P(N)必须大于并包含可判定程序集(N)。

任何可判定的程序都必须能停止。因而,在时间上它是有限的。因此,我们可以声明,对于任何可判定并且在图灵完备系统上运行的程序 P(T),它需要在某个时间点能停止运行。因此,程序集合 (N) 中,是所有形式如 P(T)程序组成的程序集,对某些输入数据,它们必须在有限时间内停止运行。值得注意的是,尽管我们无法确定每个程序是否具有确定性,我们可以开发一种完全图灵机,它要求所有程序都“展开”,因此是可以判定的。

J.B.Rosser(1939)对 “有效可计算性” 进行了广泛的写作,其观点是:

显然,CC 和 RC(Church 和 Rosser 的证明)的存在,意味着一个精确定义的 “有效”。“有效方法” 在这里以一种相当特殊的方式使用,每个步骤都是精确预定的,并且肯定会以有限的步骤产生答案。

结果是,“有效”方法将按照输出顺序创建结果,这个结果是“明白无误的,决定性的或预期的效果”。并且这系统或机器本质上必须“能够产生一个结果”。

图灵(1939)定义了这种状态:

我们将使用表达式 “可计算函数” 来表示机器可计算的函数,并且让 “有效计算” 指的是直观的想法,而没有特殊识别其中任何一个定义。

正如我们上面提到的,图灵 (1939) 的论文基于这样一个前提:对于任何有效可计算的函数,必须存在一个可计算的函数。图灵表示:

有人说:如果一个函数,可以通过一些纯粹的机械过程找到它的值,那么这个函数是可以有效计算的。我们可以从字面上理解,通过纯粹的机械过程,即理解为,可以由机器执行。此开发会导向,通过有效的可计算性来识别可计算性。

结果是,尽管所有程序都不必是有限的,所有可判定的程序都可以在图灵机上停止运行。更多地,我们可以说图灵机将运行所有可判定的程序,且只运行所有可判定的程序集合。在图灵机上运行的程序集合,并且不可判定其是否会停止的程序集合,是一个空集。

比特币脚本语言 [3] 是一种类似于 Forth 的基于堆栈的语言。它有两个堆栈,称为主堆栈和备用堆栈(ALT)。脚本指令,称为“OP_CODE”,对主堆栈中的值进行操作,而备用堆栈则用作额外的数据存储。该语言是故意设计的,以排除循环结构,来避免 DOS 攻击的可能性。但是该语言有许多功能,包括访问和管理主堆栈中数值的命令(例如,OP_PICK 和 OP_ROLL)。OP_CODE 的原始列表比当前可用的更广泛(比特币 Core 开发人员禁用了几个命令)。然而比特币脚本仍然是一种简单但功能强大的语言。

Wolfram 猜测,2 状态 - 3 符号的图灵机是通用图灵机(Wolfram,2002,p709),这个在 2007 年由 Smith(2007)证实[4]。使用 Wright(2017)中的逻辑,我们可以证明,在比特币中部署的谓词逻辑系统作为脚本语言等价于 Wolfram(2,3)图灵机。通过这种见解,我们看到,比特币在功能上是一个完全图灵机的系统 [A5][CSW6]。正如 Wright(2017)所证明的,比特币的脚本语言可以递归。Wright(2017)中描述的比特币脚本语言比 Smith(2007)更具扩展性。因此,我们可以直接将 Smith(2007)的猜想映射到一个系统,此系统使用比特币内的递归系统(Wright,2017)来设计。

问题不在于是否可以构建,能运行任何想得到的可判定程序(即会停止)的计算机。当递归循环的结构被 “展开” 时,寻找最有效方法,来最小化可判定程序大小的成为问题。展开的程序大小可以按指数级增长[A7]。对于所有程序的集合,无法确定程序是否可判定并将停止运行;或者,当运行在标准图灵机上时,在现实的时间 / 空间约束下,一个系统能否运行到结束(也无法判定)。但是,完全图灵机只接受,在预先构造和设置了有界空间 / 时间参数内定义的输入。

以相同的方式,无限数量的计算可以通过有限递归程序来描述,即使该程序不包含显式重复“(Wirth,1976)。

注:比特币指令

操作码 输入 输出 说明
OP_PICK xn ... x2 x1 x0 xn ... x2 x1 x0 xn 把主栈第 n 个元素复制到栈顶
OP_ROLL xn ... x2 x1 x0 ... x2 x1 x0 xn 把主栈第 n 个元素移动到栈顶
[1] For details see Patent filing XXX. Other loop constructs include OP_WhileLoop, OP_Case, …
[2] https://www.quora.com/Why-is-Bitcoin-not-Turing-complete
[3] https://en.bitcoin.it/wiki/Script
[4] https://www.nature.com/news/2007/071024/full/news.2007.190.html

[A1]Should this be UTM?
[A2]Extend this theory or this demonstration?
[A3]Are you referring to the advantages of this system?
[A4]This section presents a good theoretical overview on the definition of a Total Turing Machine. In my opinion the references used in this section are relevant.
[A5]In my opinion, this phrase is very difficult to follow. It needs to be reformulated. Also, I suggest adding a reference or a paragraph to introduce Bitcoin Scripting language.
[CSW6] [CSW6]I will get Stef / Antonetta to add a paragraph here
[A7]The problem statement is not clear. Please try to use shorter phrases and to formulate the problem that should be solved clearly.

后记

如果这些文章,您看起来比较费劲,那么恭喜您,您的感觉是对的;图灵完备这些问题,本来就比较深奥,至少您进行了学习和探索!看过这些文章之后,就明白设计比特币的中本聪,他的理论水平,远在这些文章之上!

比特币出来很多年之后,这个世界依然没有人知道,比特币的脚本是图灵完备的,除了一个人之外!

当我第一次看到这个观点的时候,说比特币脚本是图灵完备的,我的内心是非常震撼的!这完全颠覆了我对比特币的认知。而当时,业界对这个观点,一片嘲讽;很多所谓的大佬,对比特币脚本是图灵完备的观点,嗤之以鼻。需要自己去查证。

幸运的是,我们自己可以验证这个观点。我查阅了一些资料,经过大致的推理,确信这个观点是正确的;虽然那时还不能严格地数学证明。通过这一点,我迅速过滤出一些谎言、谣言制造者,当然,现在已经没有人敢跳出来指责这个观点了。后来,又陆续有一些博士,公布了证明比特币脚本是图灵完备的方法。

毫无疑问,理解了比特币脚本是图灵完备的人,都确信,第一个提出这个观点的人,是中本聪。那就是澳洲聪哥,Craig Wright 博士。


results matching ""

    No results matching ""