首页 >> 计算的极限

计算的极限(十三):数字空间的幽灵

Filed under: 计算机科学 发表于 2017-07-12 07:09

病毒和杀毒软件的攻防战线广阔异常,从磁盘到内存甚至显卡,都是它们的战场,而攻防策略之多,无论如何列举都只能是挂一漏万。计算机病毒和杀毒软件,两者你追我赶,永无止尽。注定这两者命运的,正是一条数学定理。

bluescreen1

计算的极限(十二):不会出错的程序

Filed under: 数学 发表于 2016-01-06 20:46

相信每个人都见识过Windows那令人忧郁的蓝屏或者黑屏吧。有时因为它,一个上午的工作一瞬间毁于一旦,这就不仅是令人忧郁而是令人抓狂了。在这个时候,你是否会在心中大声咒骂那帮写程序不小心让蓝屏一而再再而三出现的程序员呢?

来自Wikimedia

计算的极限(十一):黄金时代

Filed under: 数学,计算机科学 发表于 2015-10-29 11:22

哥德尔、图灵、丘奇、波斯特、克林……这些开创者们,告诉了我们“计算”到底是什么,而计算之外又有什么。但平心而论,我们给这些开拓者的颂扬还远远不够。在一般人心中,他们仍然寂寂无名。这些开拓者们,生前大多没有什么好的结局,就连死后也没有得到多少廉价的赞赏。他们为我们开拓了一个信息化自动化的黄金时代,但他们又得到了什么呢?

来自Wikimedia

计算的极限(十):无限绵延的层级

Filed under: 数学,计算机科学 发表于 2015-10-12 17:59

尽管人力能及的只有可计算的问题,但通过逻辑推演,我们能认识到,在那些我们无法解答的问题中,竟然还存在着一个精巧的结构。而正是波斯特向我们首次展示了这个无法触及的世界。

来自Wikipedia

计算的极限(九):叹息与奋斗

Filed under: 数学,计算机科学 发表于 2015-09-17 20:42

在数学界,证明就是一切。没有证明,即使看上去再确定无误的结论,哪怕拥有再多的间接证据,哪怕是最优秀的数学家的想法,都只能是猜想,而不是定理。要确立一个定理,就必须有一个滴水不漏的证明。这就是数学界的规则。而很不巧,本篇文章的主角,波斯特的研究风格比图灵更依赖直觉,换种说法就是更不严谨。

The Mathematicians

计算的极限(八):符号的框架

Filed under: 数学,计算机科学 发表于 2015-09-07 19:33

要知道,逻辑体系种类繁多,从弗雷格电路图一般的“概念文字”,到罗素和怀特黑德的《数学原理》中略显奇异的近代逻辑符号,再到现代一般使用的一阶逻辑,又到更复杂的模态逻辑与线性逻辑,甚至到现代如雨后春笋层出不穷的新逻辑体系,它们无论是符号、意义还是表达范围都千奇百怪,要找到一个能囊括过去、现在甚至未来出现的定义,这无疑是个令人挠头的工作。

QQ20150519-1

计算的极限(七):宛如神谕

Filed under: 数学,计算机科学 发表于 2015-05-19 15:52

图灵的这段文字其实定义了一种新的图灵机,图灵把它叫做“o-机”,而它的现代术语叫“谕示机”。一台谕示机就是一台有点特别的图灵机,仅仅多了一个新功能,就是能“免费”得到某一个特定的判定问题的答复。

counting something

计算的极限(六):无穷的彼岸

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

实际上,许多关于无穷的看似矛盾结论,都可以归根于我们在日常经验中对数量与顺序的混淆。比如说有人会认为偶数比自然数少,是因为自然数除了偶数之外还有奇数,但实际上这种说法隐含了“先数偶数再数奇数”的这一清点顺序。

计算的极限(五):有限的障壁

Filed under: 数学,计算机科学 发表于 2014-07-15 17:11

图灵在普林斯顿的生活踏入第二年。作为博士导师的丘奇,向图灵提出了一个新的题目:探求超越哥德尔不完备性定理的方法。

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

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

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

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

计算的极限(三):函数构成的世界

Filed under: 学科,数学,计算机科学 发表于 2013-04-07 10:03

在中学数学中,说到函数,自然会联想起它在平面直角坐标系的图像。这是因为中学数学中的函数,大部分情况下不过是从实数到实数的映射而已。而数学家眼中的函数,可能与程序员眼中的函数更相似:它们更像是一个黑箱,从一边扔进去某个东西,另一边就会吐出来另一个东西。

QQ20121211-1

计算的极限(二):自我指涉与不可判定

Filed under: 专题:图灵,学科,数学,计算机科学 发表于 2012-12-12 14:04

要证明某种东西存在,只要举出一个例子就可以了;但要证明某种东西不存在,就要想办法排除所有的可能性,而在现实生活中,这几乎是不可能的。但在数学中,情况大不相同:通过形式逻辑的方法,我们可以确实地证明某种数学对象不存在。这都要归功于数学那彻底的抽象化和形式化。

QQ20121116-1

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

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

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

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

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

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