首页 > 其他 > 详细

图灵完备-转自 知乎 陈超 的回答

时间:2014-10-22 21:33:30      阅读:366      评论:0      收藏:0      [点我收藏+]

陈超工程师

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

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

这个概念也就是图灵等价。

一般概念上图灵不完备指的是计算能力不如图灵机的。当然也存在计算能力可能更高的,比如说非确定图灵机。但是到底高多少,还是本质是一样的。应该没人知道,这也就是P和NP的问题。(这一段话我也不知道说的对不对,因为没印象了#_-)

图灵完备-转自 知乎 陈超 的回答

原文:http://www.cnblogs.com/so-magic/p/4044228.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!