比特币史话·70 | 智能合约(5): 停机问题

(大卫·希尔伯特,德国数学家。图片来源于网络)
前情回顾:比特币史话·65 | 赌徒的破产(6): 算力威慑
比特币史话·66 | 智能合约(1): 脚本的由来
比特币史话·67 | 智能合约(2): 合约并不智能
比特币史话·68 | 智能合约(3): 同性恋之死
比特币史话·69 | 智能合约(4): 图灵完全吗?

正文:
“我正在说的这句话是谎话”究竟是不是谎话?(说谎者悖论,公元前4世纪)
一个只给那些不给自己理发的人理发的理发师可不可以给自己理发呢?(理发师悖论,罗素悖论的通俗版,1901年)
可不可以用一门计算机语言写出一个判定程序,该程序可以判定任意一段计算机程序是能够正常结束还是会陷入死循环,换句话说,就是判定任意一段计算机程序是否可以停机?
如果计算机程序是用图灵完全的语言写出来的,那么可以把这个问题一般化为关于图灵机停机判定的问题:是否存在一个图灵机,可以判定任何一个图灵机是否可以停机?这就是著名的“停机问题”(halting problem)[1]。
1900年,在巴黎召开的第二届国际数学大会上,德国数学家大卫·希尔伯特(David Hilbert)提出了著名的“23个问题”。这些问题又被称为“希尔伯特问题”,都是当时最重大的未解决数学问题,其中一些深刻影响了20世纪数学的发展方向。
1928年,希尔伯特重新阐述了第2个问题,并展开为三问:1、数学是完全的吗?2、数学是一致的吗?3、数学是可判定的吗?这第三问就是所谓的“判定问题”(德语:Entscheidungsproblem)。
1936年,美国数学家、逻辑学家丘奇(Alonzo Church)使用他发明的λ-演算法(lambda calculus)证伪了判定问题[2]。
1937年1月,图灵的著名论文《关于可计算数及其在判定问题中的应用》(On Computable Numbers With an Application to the Entscheidungsproblem)发表,通过另外一种思路同样证伪了判定问题。这个思路就是把判定问题翻译为等价的图灵机停机问题,然后证明停机问题不可解。
所有图灵完全的编程语言所编写的代码都存在这个问题,也就是无法确定这段代码一定可以在有限时间内结束,而不会一直运行下去。
对于中心化管理的系统而言,可以通过人为干预的方式,比如强制中断程序运行,来解决这个难题。
但是比特币是一个去中心化的系统,这意味着如果比特币的脚本,作为一段特殊的计算机程序,不能确定在有限时间内终止的话,甚至有可能是恶意攻击者故意编写一段不能终止的程序,这对于每一个验证该交易和脚本的节点而言,都是一个灾难。所有节点都会被卡在这段脚本的地方,一直在运行这段永不终止的代码,整个系统无法再继续提供服务。
所以,比特币脚本是中本聪特别设计的一门“删减版”的特定领域编程语言。在这门编程语言里,图灵完备的表达能力被大大削弱,仅仅保留了比特币作为数字货币在交易中所需的可编程性。从这一点上讲,比特币脚本甚至称不上是一门完整的编程语言,中本聪把它叫做“脚本”也是恰如其分。
【未完待续】(公众号:刘教链)

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇