停机问题 计算机不可计算的问题

最近开始学习python,没想到引出lambda演算,听着陌生的名字,翻了资料才发现是早就学过的内容,函数的定义也是一个参数,通过参数定义来确定。而停机问题更是turing里的基础命题:

图灵机停机问题: 能否给出一个判断任意一个图灵机是否停机的一般方法? 答案是NO.

这个问题实际上是问: 是否存在一台"万能的"图灵机 H, 把任意一台图灵机 M 输入给 H, 它都能判定 M 最终是否停机,输出一个明确的 "yes" 或 "no" 的答案? 可以利用反证法来证明这样的 H 不可能存在.假定存在一个能够判定任意一台图灵机是否停机的万能图灵机 H(M), 如果 M 最终停机, H 输出 "halt"; 如果 M 不停机,H 输出 "loop". 我们把 H 当作子程序, 构造如下程序 P:

function P(M) {

if (H(M)=="loop") return "halt";

else if (H(M)=="halt") while(true); // loop forever

}

因为 P 本身也是一台图灵机, 可以表示为一个字符串, 所以我们可以把 P 输入给它自己, 然后问 P(P) 是否停机.按照程序 P 的流程, 如果 P 不停机无限循环, 那么它就停机, 输出"halt"; 如果 P 停机, 那么它就无限循环, 不停机;这样无论如何我们都将得到一个矛盾, 所以假设前提不成立, 即不存在这样的 H. 或者说,图灵机停机问题是不可判定的(undecidable)。

有段时间不接触知识,就跟全新的一样了,当然了有快10年没拿起这些书本了,想起查资料时还是从一小姑娘的网站上找到,而我根据她的文章应该是被归为小老头一类了。

要不是最近想看ruby或django,朔本追源,开始看python,本来也是不用花很多时间来看这个的,毕竟语法格式都和C差不多,但是仔细读来,真真还是有好的思想在里面。学习的劲头很好,但是啊,我做这件事的起因是,只是想要研究研究twitter,然后发现还可以花点时间搞明白python上的框架,接着发现还必须研读python,幸好还不用从turbo或c开始学习……结果到现在我还只是看了python的一个开头,离我的目标还远着呢,不知道我能不能坚持到看完ror的一天。我觉着,这也是我一个很大的缺点,接触新知识不能浅尝辄止,非要刨出根源,重头开始,浪费了多少时间啊。如何又能保证自己花了这么多时间研究的内容能成为将来的主流呢?

不看了,睡觉去了

停机问题 计算机不可计算的问题

  

爱华网本文地址 » http://www.413yy.cn/a/25101017/327605.html

更多阅读

不可预料的压缩文件末端怎么解决? 不可预料的压缩文件

不可预料的压缩文件末端怎么解决?——简介有时候我们下载文件解压的时候会出现不可预料的压缩文件末端怎么解决,小编今天就遇到这个问题了,就是报错,辛苦下载的文件就不能用了,能否用办法解决呢?其实有方法的,看小小编是怎么解决的。不可

转载 “不可计数”的“数”的读音问题 转载读音

原文地址:“不可计数”的“数”的读音问题作者:蜓恋墨荷香巴金的《鸟的天堂》中一句“我有机会看清它的真面目,真是一株大树,枝干的数目不可计数。”此句中“数”读音争议比较大。网上的很多朗读视频都把“不可计数”的“数”读成“shù

工作笔记 有关土方量计算的问题 土方开挖计算公式

资料来源于网络......湘源控规6.0土方计算发布:langzui | 发布时间: 2012年11月3日湘源控规可谓算是一个比较庞大的软件,已经不局限于总规控规设计这一块了,这不,今天来说说湘源控规6.0软件的“土方计算”模块,土方计算是在做城市规划

不可遏制的冲动 不可遏制

人类哲学不可遏制的冲动曾大江认为每个人都想“随心所欲,为所欲为”,只是做不到而已。我也这样想,我也做不到。因此,我必须遏制住这个冲动。如果能够理解一切,那么就能最大限度地控制一切。理解是一切是可能的。因此,我不可遏制地要理解

试论计算机软件保护的途径 计算机软件保护条列

试论计算机软件保护的途径孔建会(中豪律师集团四川事务所主任律师/高级合伙人)内容提要:计算机软件的法律保护是计算机程序及其有关文档的保护。计算机软件盗版问题严重,导致国际国内对我国计算机软件法律

声明:《停机问题 计算机不可计算的问题》为网友败絮分享!如侵犯到您的合法权益请联系我们删除