区块广播:
20
已解决

大家经常说的“图灵完备”是什么意思?

zhuoji船员发布在 问答/互助
 39459  9
达叔这篇文章给出了一个比较学术的解释,能不能通俗一点说说什么是“图灵完备”,
图灵完备是指一个能计算出每个图灵可计算函数(Turing-computable function)的计算系统。或者说,图灵完备使我们的脚本系统有能力解决所有的可计算问题。一方面,它带来了强大的处理能力;另一方面,它也使对脚本的静态分析变为不可能:我们永远也无法知道脚本何时会停止,除非我们真正去执行它。
——《中本聪:智能合约?比特币自带》

最佳答案
玛_雅船员
2016-03-30 11:22:26
图灵完备,图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。图灵完备意味着你的语言可以做到能够用图灵机能做到的所有事情,可以解决所有的可计算问题。图灵不完备也不是没有意义, 有些场景我们需要限制语言本身. 如限制循环和递归, 可以保证该语言能写的程序一定是终止的。来源:[url]http://www.zhihu.com/question/20115374[/url]理解一下,就是说图灵完备的语言,有循环执行语句,判断分支语句等。理论上能解决任何算法。但有可能进入死循环而程序崩溃。图灵不完备,应该是不允许或限制循环。可以保证,每段程序都不会死循环,都有运行完的时候。比特币的脚本系统是图灵不完备的,而一些竞争币的智能合约系统是图灵完备的。各有优缺点,图灵不完备会更安全些,图灵完备会更智能些。
  • 正序
  • 最新
只看帖主楼层直达
  • 玛_雅 版主 2016-03-30 11:22:26 只看该作者沙发
    图灵完备,图灵完全性通常指具有无限存储能力的通用物理机器或编程语言。
    图灵完备意味着你的语言可以做到能够用图灵机能做到的所有事情,可以解决所有的可计算问题。
    图灵不完备也不是没有意义, 有些场景我们需要限制语言本身. 如限制循环和递归, 可以保证该语言能写的程序一定是终止的。

    来源:http://www.zhihu.com/question/20115374

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

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

    比特币的脚本系统是图灵不完备的,而一些竞争币的智能合约系统是图灵完备的。
    各有优缺点,图灵不完备会更安全些,图灵完备会更智能些。
  • 510685947 副船长 2016-03-30 13:36:59 只看该作者板凳
    一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。
    一个能计算出每个图灵可计算函数(Turing-computable function)的计算系统被称为图灵完备的。一个语言是图灵完备的,意味着该语言的计算能力与一个通用图灵机 (Universal Turing Machine)相当,这也是现代计算机语言所能拥有的最高能力。
    图灵完备是什么意思呢?
    在可计算理论中,当一组数据操作的规则(一组指令集,编程语言,或者元胞自动机)满足任意数据按照一定的顺序可以计算出结果,被称为图灵完备(turing complete)。一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的,它(计算机设备)有能力执行条件跳转(“if” 和 “goto”语句)以及改变内存数据。 如果某个东西展现出了图灵完备,它就有能力表现出可以模拟原始计算机,而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的(C++ template就是图灵完备的),都能解决内存有限的问题。图灵完备的机器都被定义有无限内存,但是机器指令集却通常定义为只工作在特定的,有限数量的RAM上。
    来源:http://baike.baidu.com/link?url=S2dDtjEik5WhTrNsfSpfqGJfiK2es4bDz66DH4L4V5XheaN3t3QdE6f-c8HVT18Vz7KBqoH08Cjw8ag9ZDciha
  • sider 副船长 2016-03-31 14:36:09 来自App只看该作者地板
    太高深了不怎么懂啊
  • ffzh888 副船长 2016-03-31 16:55:40 只看该作者5楼
    图灵完备就是八卦图!包容一切数理!
  • Xseraph2 队长 2016-07-07 10:54:51 只看该作者6楼
    比特币的图灵非完备性
    比特币脚本语言包含许多操作,但都故意限定为一种重要的方式——没有循环或者复杂流控制功能以外的其他条件的流控制。这样就保证了脚本语言的图灵非完备性,这意味着脚本的复杂性有限,交易可执行的次数也可预见。脚本并不是一种通用语言,施加的这些限制确保该语言不被用于创造无限循环或其它类型的逻辑炸弹,这样的炸弹可以植入在一笔交易中,通过引起拒绝服务的方式攻击比特币网络。受限制的语言能防止交易激活机制被人当作薄弱环节而加以利用。



    现在看这段话真是有惊人的预见性
  • 骚皮狗 副船长 2016-07-07 11:44:37 来自App只看该作者7楼
    文盲表示看不懂
  • jeason0829 版主 2016-07-07 12:26:15 只看该作者8楼
    图灵完备官方的解释比较晦涩,说点通俗的吧,图灵完备本身是并不复杂,这么说吧,基本上支持像什么for、if、while...... 等等这些可以条件执行的程序语言都可以说成是图灵完备的语言
  • nxttyisgood 副船长 2016-07-07 13:00:10 只看该作者9楼
    好帖,马一个。
  • memorybox 水手 2016-07-09 07:52:56 只看该作者10楼
    从知乎上看到过一个解释:

    图灵完备是对计算能力的描述。

    一门语言为什么要图灵完备呢?可以这么理解:
    一台计算机也是一个图灵机,一个图灵完备的语言意味着这个语言可以使用计算机完成任何计算机可以完成的任务,也就能够发挥计算机的所有能力。(这句话有点绕口)
    反之,一个图灵不完备的语言,就意味着不能发挥计算机的所有能力。

    这个概念也就是图灵等价。
登录 账号发表你的看法,还没有账号?立即免费 注册