离散数学范式的特征及其价值摘要：20世纪中叶以来, 随着计算机的诞生及其对科学与社会日渐显现的影响力, 离散数学的思想和方法迅速发展, 展现出了更为多样和充满活力的知识形态。
离散数学的知识创新具有典型的数学范式革命性。
作为对微积分范式的一种突破, 离散数学超越了传统数学的知识界线, 展现出在数学本体论、认识论与方法论上的新的哲学特征。
与计算机与信息科学的发展相得益彰, 离散数学范式具有离散化、算法化、计算性、复杂性以及与科学更为紧密的交互性等显着的当代科学革命特征, 并显现出学科知识群与复杂性科学等独特的意蕴。
关键词：离散数学; 范式革命; 图灵计算; 量子计算; 计算复杂性;Abstract：Since the middle of 20 thcentury, with the birth of computer and its increase effect on science and society, the thought and method of discrete mathematics have developed rapidly and new forms of knowledge with more multiple, tensions and vigor were emerged. The knowledge innovation of discrete mathematics has representative paradigm revolutionary character. As a breakthrough and transcending of the paradigm of calculus, the discrete mathematics has gone beyond the bound of traditional mathematics and showed new philosophical features in ontology, epistemology and methodology of mathematics. Complement with the development of computer and informationscience each other, the discrete mathematics demonstrated the contemporary scientific revolution features such as discretization, algorithmization, complexity and more tightly interaction with science, as well as the unique implication of group of disciplinary knowledge and complex science.Keyword：discrete mathematics; paradigm revolution; turing machine; quantum computation; computational complexity;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岁的图灵发表了影响深远的论文“论可计算数及其在判定问题中的应用” (on computable numbers, with an application to the Entscheidungsproblem) 在这篇论文中, 图灵首次定义了“可计算数”的概念:“‘可计算’数可以简要地描述为其小数表达式可以通过有限方法加以计算的实数”[3]。
图灵可计算性(Turing computability) 和图灵机(Turing machine) 的概念由此诞生2。
图灵所研究的“可计算性” (computability) 以及图灵机TM (是Turing’s machines的缩写) 概念, 作为假想的理想机器, 图灵机奠定了最终导致计算机发明的理论基础。
随着理论计算机科学的不断发展, 人们又提出了“超计算” (hypercomputation) 的概念。
所谓“超计算”是指“无法在图灵意义(即一个计算者用纸和笔在有限步骤里进行的有效计算) 上进行计算的函数和数的计算”[5]。
而以超级计算概念设计的超级计算机(hypercomputer) 则超越了图灵机的范围, 能够进行更多的函数、数、问题解决和任何任务的计算。
1.3、量子计算与量子计算机引领离散数学发展的新方向近数十年来, 量子计算和量子计算机的概念开始逐步成为理论计算机科学研究的一个前沿。
英国数学家阿迪亚(M.Atiyah) 在着名的“20世纪的数学”一文中曾预测说:“21世纪将会是怎样的?我已经说了21世纪将会是量子数学的时代。
……量子数学可能意味着我们能够尽我们所能地理解分析、几何、拓扑和各种各样的非线性函数空间的代数”[6]。