克莱因的书“数学:确定性的消失”(Mathematics: The Loss of Certainty,Par Morris Kline),追溯数学在19世纪、20世纪的发展,从非欧几里得几何、悖论、公理化运动到哥德尔不完备定理,揭示了人们对数学的认识从“确定性”到“不确定性”的变化。“确定性的消失”一说,指当人们看到数学的“不确定性”如沉在海水下面的冰山开始崭露头角时的困惑,如罗素所说:“我在数学里总是希望得到的那种壮丽的确定性,消失在不知所措的困惑之中了”,此“不确定性”与关于数学基础的反思密切相关,谓之“问题的问题”,。。。 后起之秀的计算机科学,在20世纪30、40年代,伴随着数学的公理化运动,为了定义什么是机器可以计算的问题,提出“可计算性”概念,进一步表达为“图灵-丘奇定律”。于可计算问题,计算与判断一致,故“可计算问题”具有“确定性”。与哥德尔不完备定理的角度不同,图灵是从计算的角度,证明了存在着“不可计算问题”-“停机问题”,“停机问题”不可判断,也就是说,“停机问题”具有“不确定性”。 然而随着计算机运用的广泛开展,相对于算法可以求解的问题(P),出现了某些实际问题算法求解困难(NP)。从可计算性的角度,问题可以算法求解实际上就是指“可计算性”,只是这里人们用算法的“多项式时间复杂度”表达了“可计算性”,指机器的能力与问题实例的规模增长相匹配,故机器对这样的问题具有计算的能力:P是可计算的;而问题算法求解困难就是指“不可判定性”,即可计算性意义的算法的存在出现了问题,机器对这样问题不具有(精确)计算的能力:NP“难”到不可计算。然而,就是在这里人们的认知开始出现了偏差:没有看透“多项式时间复杂度”的本质是“可计算性”,仅仅局限于具体问题,混淆了“多项式时间复杂度”与实际计算的“多项式时间”的本质区别(见博文: 对“多项式时间复杂度”的误解 )!从而,把P认为是一类可计算问题,而NP是另一类可计算问题,NP由此失去了“不确定性”的本质(见博文: NP是可计算的吗?- “问题”的分类 )。 在这种意义上,我们或许也可以说,“流行的算法理论:不确定性的消失”!但是,这里的“不确定性的消失”是一种认知的迷失,而克莱因所说的“数学:确定性的消失”的困惑,实际上是一种认知的觉醒。正如克莱因在书的开篇所说: -战争、饥荒和瘟疫能引起悲剧,然而,人类思想的局限性也能引起智力悲剧。(There are tragedies caused by war, famine, and pestilence. But there are also intellectual tragedies caused by the limitations of the human mind.)
“判断”是人最基本的思维活动之一。 于汉字(汉字基因): 判═半刀,分也,辨也,斷也; 斷═絲斧,使不連續,折也,判也,絕也,無也。 判斷者,分辨後令之不再連續也。 按西方哲学的传统观念,也是人们现在普遍接受的观念,人的思维活动包括:概念、判断、推理。为此,我们引用在西方语言、逻辑学中占有重要地位的书“Grammaire générale et raisonnée(普遍唯理语法),Antoine Arnauld (1612-1694)和Claude Lancelot (1615-1695)”中一段话: Tous les philosophie enseignent qu'il y a trois opérations de notre esprit: concevoir, juger, raisonner. Concevoir, n'est autre chose qu'un simple regards de notre esprit sur les choses, soit d'une manière purement intellectuelle, comme quand je connaît l'être, la durée, la pensée, Dieu; soit avec des images corporelles, comme quand je m'imagine un carré, un rond, un chien, un cheval. Juger, c'est affirmer qu'une chose que nous concevons est telle, ou n'est pas telle: comme lorsqu'ayant conçu ce que c'est que la terre, et ce que rondeur, j'affirme de la terre, qu'elle est ronde. Raisonner, est se servir de deux jugements pour en faire un troisième: comme lorsqu'ayant jugé que toute vertu est louable, et que la patience est une vertu, j'en conclus que la patience est louable. “所有的哲学家都教导说,我们头脑中有三类活动,即:概念、判断、推理。 概念,指我们头脑简单地观察事物所得,或者是纯粹抽象的,如当我想到存在、时间、思想或上帝;或者是有形象的,如当我想到一个正方体、一个圆形、一只狗或一匹马。 判断,指断定我们构想的事物是这样的或者不是这样的,如当我构想什么是地球和什么是圆形以后,对地球作出判断,认为地球是圆的。 推理,是运用两个判断来求出第三个判断,如当我判断一切美德都是值得赞扬的,并且耐心是一种美德,就得出结论,耐心是值得赞扬的。” 也就是说,按一般的理解,“判断”指对事物的某种性质进行肯定或否定的断定。但是如果我们仔细推敲,就会发现“判断”是有层次之别的。 比如,一个人早上起来,对“昨晚是否下雨”进行判断,若他看到地上有雨水等现象,可肯定:“昨晚下雨了(yes)”,或否定:“昨晚没下雨了(no)”。 他还可以对“明天是否下雨”作出判断,若借助天上压得很低的云等现象,他可断定:“明天下雨(yes)”,或者:“明天不下雨(no)”。 但是,这二个判断却有本质的区别。于前一判断“昨晚是否下雨”,事件已结束, 结果 已形成,故能与 结果 对照,验证 判断的 “对错 / 真假 ”,故此判断是“确定性”。但于后一判断“明天是否下雨”,因 事件仍在进行中, 结果 尚未形成,无 结果 可对照,以验证其“ 对错/ 真假”,故此判断是“不确定性”的。 在P问题和NP问题中,涉及到的正是这二种本质完全不同的“判断”,但因人们忽视了二者的本质区别,造成了现今理解“NP问题”的困难,故我们称之为“不确定性的困惑”。