首页 >> 图灵机

这么多,记不住,头好晕……

计算的极限(四):机械计算的圭臬

Filed under: 数学,计算机科学 发表于 2013-10-21 13:11

图灵知道,丘奇也知道,他们已经踏入了一个新领域。昔日希尔伯特在他的二十三个问题中,一语带过的那个“机械化的运算”,即将被赋予精确的数学含义。但正因如此,踏出的第一步必须慎之又慎,尤其对于“可计算性”这个最基础的定义,必须做到毫不含糊。为此,为了消除模棱两可之处,图灵机与λ演算是否能力相当,这是个必须回答的问题。

QQ20121116-1

计算的极限(一):所有机器的机器,与无法计算的问题

Filed under: 专题:图灵,学科,数学 发表于 2012-11-16 10:36

虽然看上去简单,但实际上图灵机能做的事情远远超出一般的想象。只要有足够长的纸带和足够好的耐心,今天的电脑能做的计算,一台精心设计的图灵机也能完成。也就是说,从原则上来说,只要配备适当的输入和输出设备,以及极其好的耐心,我们完全可以用图灵机上网、玩游戏甚至执行自己写的程序。

计算的极限(零):逻辑与图灵机

Filed under: 专题:图灵,数学,计算机科学 发表于 2012-07-17 06:45

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。第一位发现这一点的,便是图灵。

惠普实验室研究员声称证明世纪数学难题P!=NP

Filed under: 资讯,资讯 数学 发表于 2010-08-09 16:18

惠普实验室的研究员Vinay Deolalikar声称证明了P不等于NP。P vs NP是克莱研究所的千禧年难题大奖中宣布的7道数学世纪难题中的一道。这7道难题分布在数学的不同分支,任一道难题的解决都被认为会对相应的分支有重大的影响。目前为止,这七道难题中唯一被确认证明的是庞加莱猜想。