区块链-图灵完备

图灵完备,图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。

图灵完备意味着你的语言可以做到能够用图灵机能做到的所有事情,可以解决所有的可计算问题。
图灵不完备也不是没有意义, 有些场景我们需要限制语言本身. 如限制循环和递归, 可以保证该语言能写的程序一定是终止的。

理解一下,就是说图灵完备的语言,有循环执行语句,判断分支语句等。理论上能解决任何算法。但有可能进入死循环而程序崩溃。

图灵不完备,应该是不允许或限制循环。可以保证,每段程序都不会死循环,都有运行完的时候。

  • 以下是Stackoverflow回答:
    以下是一个简短的解释。
    一个图灵完备系统意味着在这个系统中写程序能够找到解决方法(尽管不保证运行时和内存)。
    因此,如果有人说,我的新东西是图灵完备的,意思是在原则上(尽管不是经常在实践上)它能够用来解决任何计算性的问题。
    有时,它是一个笑话,有人在vi上写了一个图灵模拟器,因此可以说vi是有史以来唯一需要的计算引擎。

  • 以下是维基百科解释:
    可图灵指在可计算性理论中,编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之,此系统可与通用图灵机互相模拟。这个词源于引入图灵机概念的数学家艾伦·图灵(Alan Turing)。
    虽然图灵机会受到存储能力的物理限制,图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。简单来说,一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。

比特币的脚本系统是图灵不完备的,而一些竞争币的智能合约系统是图灵完备的,比如以太坊。各有优缺点,图灵不完备会更安全些,图灵完备会更智能些。

a、顺便一提,图灵机是我们已知能实现的最强的计算模型。最近媒体经常报道的量子计算机仍然是图灵机,只是特定算法快一些。
b、顺便二提,根据Kleene正规型定理,任意偏递归函数都可以由原始递归函数经过一次极小化得来,所以写程序的时候如果发现两层以上的无限循环要格外小心,很可能逻辑是错的。

参考
1、什么是“图灵完备”?
2、以太坊“图灵完备”是什么意思?
3、什么是图灵完备?

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,634评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,951评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,427评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,770评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,835评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,799评论 1 294
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,768评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,544评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,979评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,271评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,427评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,121评论 5 340
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,756评论 3 324
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,375评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,579评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,410评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,315评论 2 352

推荐阅读更多精彩内容

  • 前言 在学习区块链的过程中,常常被一些外星人词汇(专业术语)困扰,图灵完备、零知识证明就是其中之二,今天就彻底搞定...
    叶先生的鱼阅读 3,340评论 0 9
  • 【中文版】以太坊白皮书 翻译:少平、 Seven当中本聪在 2009 年 1 月启动比特币区块链时,他同时向世界引...
    __Seven__阅读 4,181评论 0 10
  • 文/耿先生 谈到说话,就想起之前看过的一个节目,当时何炅和汪涵在一起主持,便有人问汪涵,何老师和涵哥到底谁是湖南台...
    耿先生阅读 208评论 2 6
  • 行动起来,你就会发现: 时间睡够了7小时,曾经以为翻身多睡一小时自然醒会不困,结果醒了以后更困更累。 曾经以为坐在...
    KOALA_e36d阅读 245评论 1 3
  • 他和她 因海而相知相识 走过初夏的纯爱 因海的遥远 在初秋断点 若相思相忆 能像飘着雨的南国潮汐 来去自安排 亦不...
    Alex0309阅读 225评论 0 0