离散数学范式的特征及其价值.docx
- 文档编号:14832716
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:13
- 大小:29.92KB
离散数学范式的特征及其价值.docx
《离散数学范式的特征及其价值.docx》由会员分享,可在线阅读,更多相关《离散数学范式的特征及其价值.docx(13页珍藏版)》请在冰点文库上搜索。
离散数学范式的特征及其价值
离散数学范式的特征及其价值
摘要:
20世纪中叶以来,随着计算机的诞生及其对科学与社会日渐显现的影响力,离散数学的思想和方法迅速发展,展现出了更为多样和充满活力的知识形态。
离散数学的知识创新具有典型的数学范式革命性。
作为对微积分范式的一种突破,离散数学超越了传统数学的知识界线,展现出在数学本体论、认识论与方法论上的新的哲学特征。
与计算机与信息科学的发展相得益彰,离散数学范式具有离散化、算法化、计算性、复杂性以及与科学更为紧密的交互性等显着的当代科学革命特征,并显现出学科知识群与复杂性科学等独特的意蕴。
关键词:
离散数学;范式革命;图灵计算;量子计算;计算复杂性;
Abstract:
Sincethemiddleof20thcentury,withthebirthofcomputeranditsincreaseeffectonscienceandsociety,thethoughtandmethodofdiscretemathematicshavedevelopedrapidlyandnewformsofknowledgewithmoremultiple,tensionsandvigorwereemerged.Theknowledgeinnovationofdiscretemathematicshasrepresentativeparadigmrevolutionarycharacter.Asabreakthroughandtranscendingoftheparadigmofcalculus,thediscretemathematicshasgonebeyondtheboundoftraditionalmathematicsandshowednewphilosophicalfeaturesinontology,epistemologyandmethodologyofmathematics.Complementwiththedevelopmentofcomputerandinformationscienceeachother,thediscretemathematicsdemonstratedthecontemporaryscientificrevolutionfeaturessuchasdiscretization,algorithmization,complexityandmoretightlyinteractionwithscience,aswellastheuniqueimplicationofgroupofdisciplinaryknowledgeandcomplexscience.
Keyword:
discretemathematics;paradigmrevolution;turingmachine;quantumcomputation;computationalcomplexity;
20世纪中叶以来,随着计算机的迅猛发展,核心数学呈现出新的迹象。
一种异于微积分的数学新范式———离散数学喷薄而出,成为推动当代数学与科学发展的一种主导力量。
离散数学是数学研究范式的一次重大转向。
与20世纪的科学进步和革命相互辉映,在离散数学领域中持续发生的数学知识创新与革命性突破书写了20世纪以来绚丽多彩、恢宏壮观的科学画卷,成为当代科学革命的重要标志之一,具有重要的科学里程碑意义。
1、离散数学的知识创造及其发展
20世纪中叶以来,数学的知识进步呈现出新的特征,它从单纯的知识量的积累转变为产生一系列具有革命性意义的知识变革。
而突破传统的微积分范式的知识创造也正在悄然发生。
其中尤其是以离散数学的崛起和兴盛最具范式革命性意义。
离散数学是数学中若干分支的总称,研究的对象是基于离散空间而不是连续空间的数学结构。
离散数学的基本内容包括集合与数据结构、代数结构、计数理论、数值分析、数理逻辑、图论、自动机理论、递归函数、数论、组合数学、离散概率、计算群论、计算组合学、计算图论等。
更一般地说,离散数学可以被视为建立在可数集合之上的数学分支。
与连续型数学模型相比,由于计算机的运算在本质上是离散型的,因而直接从实际问题建立离散的数学模型,比传统上先建立连续的模型再予以离散化更为便捷。
如此,离散数学就创制了一种迥然不同于微积分连续数学的新范式———离散数学的知识范式。
1.1、离散数学的理论准备与计算机时代“算法”的涵义
离散数学的异军突起与计算机的诞生密不可分。
计算机的发明是人类科技史上一次重大的创造。
受到计算机迅猛发展的影响,20世纪后半叶以来,数学发展开始从较为单一的微积分主线中分离出来,离散数学的思想方法由于其与计算机的紧密联系而日益受到数学共同体的青睐。
因为无论是具有多么强大功能的计算机,也只能进行有限的计算和处理有限的数据。
而不能完成实在无限的过程。
这样,微积分的思想和理论就不能直接用于计算机,而必须做离散化的处理,才能发挥其效力。
离散数学的兴起,是数学知识创新与当代科学发展交互作用的共同结果。
作为一种新的数学范式,离散数学在知识构成中有两个必备的数学理论条件。
第一个是集合论的语言与方法。
19世纪末集合论的诞生,使得数学研究对象获得了极大的扩展。
在微积分范式中,实数系(最多到复数系)构成了所有理论的基础性平台。
在复变函数范式中,复数系构成了其知识建构的平台。
20世纪以来,集合论替代了以前的各种平台,成为几乎所有新的数学分支的主要平台。
“对20世纪数学的另一个重大影响,是康托尔在19世纪末把无穷集引入数学词汇。
许多长期存在的问题,可以用集论提供的丰富语言来重新描绘或重新解决”[1]。
任何抽象的对象所构成的集合,只要满足一定的条件、关系、规则和法则,都可以成为数学的研究对象。
因此,集合论堪称数学知识范式的一场革命。
集合论在离散数学具有特别重要的基础地位。
第二个是理论计算机的科学基础,特别是其数学基础的形成、发展与成熟。
值得注意的是,计算机科学中许多重要的理论基础是从曾被认为是极为抽象和缺乏现实意义的数理逻辑和形式主义数学的研究中逐步发展起来的。
例如数理逻辑,20世纪30年代后,随着哥德尔定理的诞生,数理逻辑等纯粹数学研究出现了一些与理论计算机的诞生紧密相关的新的语境。
其中一个重要的方向就是对“算法”的研究。
“算法”有许多不同的定义,其最朴素的含义是“一步接一步的方法”[2]。
在计算机时代,“算法”特指的是与计算机的程序运行相关的计算方法1。
1.2、“计算”作为离散数学核心概念的革命性演进:
从可计算到超级计算
20世纪后半叶以来,以计算机的理论发展和应用为平台的离散数学体系开始迅猛发展,并对传统的以连续数学为核心的数学知识结构与体系造成了巨大的挑战。
由于计算机本质上是离散型的机器,因此,随着计算机的发明,离散数学的思想、观念和方法的重要性开始在20世纪中叶以来的数学研究中日益显现出来。
数学的核心领域发生的持续的知识更新与创造可谓日新月异。
以下就以离散数学中最核心的概念之一———“计算”概念作为其知识范例,对离散数学的革命性演进予以分析。
如果一个函数可以在规定的程序内通过有限步计算达到所需要的结果,那么这样的函数就被称为“可计算”的。
在这方面,英国数学家图灵(A.M.Turing)的工作是开创性的和最为引人注目的。
1936年,剑桥大学国王学院年仅23岁的图灵发表了影响深远的论文“论可计算数及其在判定问题中的应用”(oncomputablenumbers,withanapplicationtotheEntscheidungsproblem)在这篇论文中,图灵首次定义了“可计算数”的概念:
“‘可计算’数可以简要地描述为其小数表达式可以通过有限方法加以计算的实数”[3]。
图灵可计算性(Turingcomputability)和图灵机(Turingmachine)的概念由此诞生2。
图灵所研究的“可计算性”(computability)以及图灵机TM(是Turing’smachines的缩写)概念,作为假想的理想机器,图灵机奠定了最终导致计算机发明的理论基础。
随着理论计算机科学的不断发展,人们又提出了“超计算”(hypercomputation)的概念。
所谓“超计算”是指“无法在图灵意义(即一个计算者用纸和笔在有限步骤里进行的有效计算)上进行计算的函数和数的计算”[5]。
而以超级计算概念设计的超级计算机(hypercomputer)则超越了图灵机的范围,能够进行更多的函数、数、问题解决和任何任务的计算。
1.3、量子计算与量子计算机引领离散数学发展的新方向
近数十年来,量子计算和量子计算机的概念开始逐步成为理论计算机科学研究的一个前沿。
英国数学家阿迪亚(M.Atiyah)在着名的“20世纪的数学”一文中曾预测说:
“21世纪将会是怎样的?
我已经说了21世纪将会是量子数学的时代。
……量子数学可能意味着我们能够尽我们所能地理解分析、几何、拓扑和各种各样的非线性函数空间的代数”[6]。
这一预测可谓具有很好的前瞻性。
在量子数学中,一个迅猛发展的领域就是量子计算的概念。
与电子计算机中的计算概念不同,量子计算的概念与量子计算机紧密相关。
量子计算机是建立在量子力学所使用的计算模型基础上的计算机[7]。
与“超级计算”的概念相比,“量子计算”具有更奇特的威力。
量子计算的思想是物理学、数学与计算机科学的一个结合,其想法源自于量子力学理论[8]。
1982年,在着名的“模拟物理与计算机”一文中,量子计算机的开创者之一费因曼(R.P.Feynman)提出了依据量子力学公设获得量子计算的数学框架的设想[9]。
1985年,牛津大学的多伊奇(D.Deutsch)提出量子图灵机(quantumTuringmachine)的概念,量子计算开始具备了数学的基本型式[10]。
与传统的计算机不同,“潜在的量子计算机的核心是微观系统的能力,一个原子或一个单个光子,会同时处于超过一个的量子态———叠加的状态”[11]。
一束激光可以把一个原子激发到一种兼具原态和激发态的叠加状态。
如果这两种状态分别表示二进制的1和0,叠加状态就可以立刻同时作用于两种值。
一个量子计算机在叠加态时如果有n个原子,就可以同时完成2n次运算,这种并行度是传统电子计算机所无法比拟的。
在量子计算中发展出了各种量子算法。
其中,量子绝热算法是一个研究热点。
量子绝热算法(quantumadiabaticalgorithm)以及量子绝热超级计算机(Thequantumadiabatichypercomputer)是近年来发展迅猛的量子计算领域。
在量子计算中,利用绝热量子演化原理进行计算的过程称为绝热量子计算。
量子绝热进化算法可以有效地解决若干NP完全问题[12]。
“绝热量子计算与传统量子计算在处理Hamilton量上本质的区别:
前者并不以显式的酉变换改变系统Hamilton量来控制量子计算的过程,而是设定绝热量子演化条件,让系统在物理定律的支配下自行进行时间演化”[13]。
量子计算促进了数学与物理学更紧密的结合。
量子计算的思想作为物理学、数学与计算机科学的一个美妙结合,体现了数学、计算机和物理学的内在本质联系。
量子计算作为一种新型算法,体现了量子力学的基本思想在计算当中的威力。
数学与物理学相互之间都给对方提供必要的方法(包括算法),这是数学与物理学相互关系达到更高境界的基本标志。
可以期待的是,量子计算将成为未来数学知识的重要形态。
2、离散数学的范式革命性及其特征
如何看待离散数学在当代数学中所扮演的角色?
与之相应的一个首要问题是如何评价经典微积分范式在当代数学中的地位。
拉尔斯顿(A.Ralston)在“离散数学会在重要性上超越微积分吗?
”一文中给出的判断是:
“随着纯数学在20世纪的快速增长,‘数学之树’中根植于微积分的比例显着地下降了”[14]。
拉尔斯顿特别强调了数值分析、算法、图论、多值逻辑、快速傅里叶变换、数理逻辑、计算复杂性等离散数学分支在当代数学和计算机科学中日益增长的重要性。
概括起来,离散数学有以下一些重要的革命性指向需要特别予以关注。
2.1、离散数学具有突破并超越微积分范式的革命性指征
与微积分范式相比,离散数学范式具有以下三个显着的革命性特征:
第一,从数学的应用性看,离散数学具有与当代社会生产力形态更好的匹配力和适应性。
“正如古典分析是在第一次工业革命中培育并得到发展的,离散数学则是由第二次工业革命所支撑并得到进步的”[14]。
第一次工业革命的对象是物质世界,而第二次工业革命处理的是非物质———知识、通讯、信息等。
相对来看,微积分的应用对象是第一自然,而离散数学的应用领域则更多的是人工自然。
因此,如果说与微积分相比,离散数学处于数学发展的更高阶段,这一判断是合理的。
第二,离散数学范式具有与微积分范式迥然有别的思想方法、知识领域和知识结构。
微积分用连续变化的观念去对客体做出一种刻画,在许多情况下只是一种简单化和理想化。
微积分假设了研究对象的许多理想的属性,如连续,可微,光滑,收敛,一致收敛,可积等。
如果对象不具有这样的属性,微积分思想方法就会出现散焦现象,难以对这些对象进行很好的理论描绘。
与微积分相比,离散数学的突出特征之一就是离散化的思想与方法。
而离散数学仅能处理有限对象,或通过近似或逼近的方式接近潜在无限。
这就使得离散数学具有可以直接处理客观对象的特征,因为任何客观事物都是有限性的存在。
从严格性和证明的角度看,在离散数学中,其严格性的标准与构造性和计算性紧密相关。
比如,在离散数学中对证明性的要求(尤其是纯粹的存在性证明)大幅降低,而构造性的要求则大大提高。
第三,在离散数学中,猜测、算法、试错和计算机实验成为基本的方法,这是数学方法论的重大转变,具有典型的方法论革命意义。
计算机辅助化成为做数学的基本方法,如1976年阿佩尔和哈肯对四色定理的计算机证明,就颠覆了传统数学手工证明的观念。
计算机还有助于更多的数学发现,典型的例子是对孤立子的研究。
计算机实验也逐渐成为做数学的一种基本方式。
贝克(AlanBaker)在“实验数学”一文中,把“使用计算机”和“归纳支撑”作为“实验数学”的两个基本特征[15]。
贾弗和奎因在“‘推测数学’:
走向数学和理论物理的文化综合”一文中提出,应该借鉴物理学中理论物理和实验物理的各自分工,把数学分为“证明数学”和“假设数学”,从而允许“推测数学”的存在[16]。
2.2、离散数学与连续数学的范式差异性与可通约性
离散数学的诞生,彻底改变了连续数学(包括微积分理论以及与之密切相关的古典应用数学)一统数学天下的格局。
在计算机诞生之前,连续数学在数学世界里可谓独一无二的王者。
20世纪下半叶以来也许是连续数学(以微积分为核心)范式一枝独秀局面让位于与离散数学范式分庭抗礼的重要时期,更准确地说是在范式的差异与转换中走向了两种范式的相互辉映。
虽然在数学的发展中,由于问题、理论、研究对象和方法的不同,数学曾被分成纯粹数学和应用数学两大类。
尽管在纯粹数学范式中,连续数学依然占据着某些领域的统治地位,但它们之间又不是截然分割和孤立的。
在离散数学与连续数学的范式关联性中,库恩在科学革命的语境中所表达的范式之间的不可通约性遭受了挑战。
表面上看起来,离散数学范式似乎是对连续数学范式的一种远离或背离。
然而,这种背离却并不是沿着与连续数学完全相反的思想逻辑和方法路径行进的,而是与之具有了一种范式可通约性。
“连续的经典数学的世界与离散的当代计算是互补的”[17]。
事实上,纯粹数学从应用中获得的动力,与应用数学从抽象理论中获得灵感,都是有大量的案例的。
正如有学者论证的,“纯粹数学与应用数学是不可分割地缠绕在一起的”[18]。
连续数学的离散近似就是这样一种相互结合的知识典型。
离散化关注将连续模型或等式转化为离散形式的过程,通常是基于简化计算的目的。
很多的连续数学概念都有离散数学的版本。
可以预见的是,未来的数学发展必将使得连续数学与离散数学获得更为紧密和高层次的结合。
已出现了许多把两者结合起来的数学理论创新。
例如:
离散微积分;离散概率分布;离散傅里叶变换;离散几何;离散对数;离散微分几何;离散外微分;离散莫尔斯理论;差分方程;离散动力系统等。
在应用数学中,离散模型是连续模型的离散近似。
在离散模型中,离散方程由数据所确定。
使用递推、递归迭代等关系是这种建模的一般方法。
由此,传统意义上的微积分范式亦获得了计算机时代特有的离散数学思想方法的新内涵。
因此,两者之间进一步形成的张力和相互融合是未来数学发展值得期待的一个方向。
2.3、计算机科学的发展推动传统数学并催生新的数学知识分支
计算机的广泛使用对数学研究具有积极的推动作用。
例如着名难题四色问题就是被计算机证明的。
在问题的求解过程中,许多具有实用价值的数学分支如数论、分析几何、小波分析、仿生计算、数值计算中的有限单元方法等等都是与计算机和人工智能紧密相关的。
以复动力系统来看,“近十多年来非常活跃的一个数学分支—复动力系统,其研究起源于1920年前后法国数学家法图(P.J.L.Fatou)与朱里亚(G.Julia)的工作。
当时,他们已经对有理函数的动力系统作了很完整的研究,然而没有电子计算机,也缺乏数学上的一些准备,这个领域沉寂了60年。
1980年以后,复动力系统引起了许多数学家的兴趣,成为研究的热点之一。
发生这样大变化的一个原因就是计算机的功用。
借助于计算机,可以将有理函数的朱里亚集完全描绘出来,而朱里亚集是复动力系统里的一个最重要和基本的概念。
当有理函数作一点微小的变化,其朱里亚集就会产生很大的改变。
许多实际对象,比如一片树叶,我们可以找到一个函数,其朱里亚集与这片树叶的形状是一样的”[19]。
我国着名数学家、科学院院士王梓坤教授把数学内部各分支间的相互渗透、数学与其他科学(如控制论)的相互渗透、电子计算机的出现看作是当代数学三个新的特点[20]。
这一判断是准确和全面的。
离散数学不仅推动传统数学的发展,而且催生了大量新的数学分支。
例如,在离散数学知识群中,AI(人工智能)是一个近年来愈加活跃的领域。
与计算机相比,一般来说,人脑具有处理模糊信息的能力,善于判断和处理模糊现象。
但计算机对模糊现象识别能力较差,为了提高计算机识别模糊现象的能力,就需要把人们常用的模糊语言设计成机器能接受的指令和程序,以便机器能像人脑那样简洁灵活地做出相应的判断,从而提高自动识别和控制模糊现象的效率。
这就需要寻找一种描述和加工模糊信息的数学工具,进而推动数学家深入研究模糊集合、模糊逻辑和模糊数学。
3、离散数学知识创新的意义
离散数学的知识创新具有不同于连续数学的独特、深刻和显着的意义。
作为一种数学家的工作哲学,离散数学的哲学是活生生的、充满生机的与当下科技进步紧密相关的数学哲学。
这种具有实践哲学倾向的数学范式缩小了数学与数学哲学的距离,改变了传统数学哲学与实际数学研究脱节的局面,堪称当代数学哲学实践转向的一个范例。
3.1、离散数学开创了“学科群”知识新范式并赋予数学新的统一性
与传统数学相对孤立的学科类型相比,离散数学具有数学不同分支的学科交互性。
这种交互性体现在离散数学不是一个孤立的分支,而是一个“学科群”,即由一簇相互紧密关联的学科组成的知识集合。
数学的统一性是数学保持生命活力的一个基本前提。
在离散数学范式获得主流数学地位之后,一种新的数学统一性亦开始形成。
这种统一性既不是依照“逻辑主义”或“元数学”的基础,甚至也不是按照“结构主义”或“经验主义(包括拟经验主义)”的标准来获得的,而是以不同学科的相互渗透、相互交叉为特点。
阿迪亚这样描述了20世纪后半叶以来的数学发展特征:
“20世纪的后半叶更多地是我愿意称之为‘统一的时代’。
在这个时代里,各个领域之间的界限被打破,各种技术可以从一个领域转移到另一个领域,不同事物的交叉性达到了空前的范围”[6]。
在离散数学学科群中,学科之间壁垒被打破,不同学科之间相互交织、相互映衬,学科之间没有严格的知识界线。
离散数学范式不仅拓展了数学研究的领域和范围,而且在更高的层次上实现了与以微积分为主体的连续数学的相得益彰和互补平衡,使得数学在不同“子范式”和“学科群”的有机多样联系中实现了新的统一。
3.2、对传统数学哲学本体论、认识论和方法论的突破与挑战
在离散数学范式中,关注现实的数学、计算机、信息科学等前沿科学问题与其高度的、广覆盖率的应用性是其鲜明的特色。
平考克(C.Pincock)在“走向应用数学哲学”一文中写道:
“如果在当代数学哲学中有什么新的趋势可以称得上是‘新浪潮’的,那肯定就是把注意力转向了对被工作数学家所热捧的实践与优先发展领域的呼唤”[21]。
由于与计算机科学和信息科学等领域天然的和紧密的学科间性,在离散数学范式及其共同体中,许多传统的、形而上学色彩浓厚的数学哲学认识论话题、难点和焦点都变得不再重要或不再被关注。
如数学哲学家贝纳塞拉夫在“数不可能是什么”一文中所提出的着名的“贝纳塞拉夫论证”(Bena
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 范式 特征 及其 价值