建议加一段关于图灵在问题求解方面的理论贡献:图灵的理论完全可以和文章所提到的20世纪三大颠覆性科学理论平列为第四大理论,那就是:

来源: 老冷 2015-02-25 22:53:46 [] [博客] [旧帖] [给我悄悄话] 本文已被阅读: 次 (1348 bytes)
本文内容已被 [ 老冷 ] 在 2015-02-25 23:02:11 编辑过。如有问题,请报告版主或论坛管理删除.
图灵的理论告诉我们,这个世界上只有三类问题,一种叫“可计算”的问题(比如算去年的所得税,哈哈)。就是能够在合理有限时间内(严格讲叫“多项式时间(P)”内),有步骤地(既可编程地)最终解决,图灵证明了,凡这类问题都可用图灵机求解。相反,另一类问题就是“不可计算”的问题,即不能在有限时间内,有步骤地求解,这类问题图灵机不能求解 (比如爱情问题宗教问题,哈哈)。第三类问题,也是最让科学家们头疼的问题,是这些问题目前属于“中间灰色地带”,不知道他们是“可计算的”,还是“不可计算”的,叫做“NP-完全问题”。比如过去的四色定理问题,推销员问题等等。所以,现在一旦某个NP-完全问题被证明是属于可计算的或不可计算的,都会是科学界的盛事,因为这个问题的结局会导致同类一大堆问题的命运(即能否用计算机最终解决)。以上当然是通俗非严谨的说法。有兴趣的同学可以去选修一门“计算复杂性”的CS课。哈哈 


楼主的文章很好,尤其是介绍密码机原理部分。谢谢。
请您先登陆,再发跟帖!

发现Adblock插件

如要继续浏览
请支持本站 请务必在本站关闭Adblock

关闭Adblock后 请点击

请参考如何关闭Adblock

安装Adblock plus用户请点击浏览器图标
选择“Disable on www.wenxuecity.com”

安装Adblock用户请点击图标
选择“don't run on pages on this domain”