柯尔莫哥洛夫：复杂性研究的逻辑建构过程评述，本文主要内容关键词为：洛夫论文,复杂性论文,逻辑论文,过程论文,柯尔论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：N031
文献标识码：A
柯尔莫哥洛夫(A.N.Kolmogorov,1903.4.25-1987.10.20)是20世纪苏联最伟大的数学家之一，也是20世纪世界极有成就的数学家之一。苏联科学院数学部、莫斯科数学学会和苏联数学学报编辑部在柯尔莫哥洛夫诞辰70周年之际对他所研究的领域及做出的成就作了如下概括：“您对现代数学的发展及其应用做出了杰出的贡献。您的基础性研究决定了20世纪数学领域许多分支的整个发展图景。三角级数理论、测度论、集合论、积分理论、可构造性逻辑、拓扑学、渐近理论、概率论、随机过程理论、信息论、数理统计、动力系统、有限自动机、算法理论、数理语言学、湍流理论、天体力学、积分方程、希尔伯特的第13问题、弹道理论和在生物学、地理学、金属结晶学中的数学应用，是您所涉及到的数学分支和您深邃的思想所丰富起来的理论应用的一个不完备列表。您总是把数学应用与数学和其他学科建立起重要的联系。您广博的研究兴趣和教育天赋总能吸引许多年轻的科学家。”[1]按照他的简短传记[2]，他1925年毕业于莫斯科大学，1929年获得博士学位，同年进入莫斯科大学任教，1931年成为该大学教授。1939年他当选为苏联科学院院士，苏联大百科全书的数学部分的主编。1963年他获得国际巴尔扎恩奖(Balzano Prize)；1965年首次获得列宁奖章(Lenin Prize)，他还获得过十月革命奖章和苏联英雄的称号。1980年获得了沃尔夫奖(Wolf Prize)，他也是担任外国科学院和科学社团成员最多的苏联科学家之一。
柯尔莫哥洛夫在许多方面都取得了重大科学成就，他是位科学巨匠。我们特别注意到他的工作为21世纪的复杂性科学研究奠定了重要基础。柯尔莫哥洛夫具有深刻的洞察力和科学批判精神，他总是把有待研究的问题与该理论的逻辑数学基础联系起来，深入到理论体系的逻辑底层，对逻辑前提的批判考察和逻辑体系的缜密建构是他具备驾驭不同科学分支及整个科学理论体系发展能力的一个重要的因素。本文试图理清柯尔莫哥洛夫通过对直觉主义逻辑、信息论、概率论的批判与建构，发现复杂性的逻辑发展脉络；把柯尔莫哥洛夫“复杂性”概念置于逻辑发展过程中理解并阐明其出现的逻辑必然性，以纪念柯尔莫哥洛夫诞辰100周年。
1 从传统直觉主义逻辑出发
对数理逻辑系统的看法主要存在两种不同观点：纯形式主义逻辑和直觉主义逻辑。二者对于满足一致性但不可证明的命题的真假问题结论完全不同：对于形式主义观点而言，这种命题的真假问题是无意义的，这种命题的存在只能表明公理系统本身不完备，可以根据方便性需要把该命题或其否定形式作为公理系统的一个新公理，以使系统完备化；对直觉主义观点而言，可能存在两种情况，第一，该命题的真假可以由直接观察做出判断。在这种情况下，可以把该命题（如果它为真）或其否定命题（如果它为假）作为一个新公理。第二，不能通过直接的观察判断其真假。这时，要么从其他明显为真的命题中试图推导出该命题，如果这种做法失败，要么认为该命题是不确定的，它的真假可能根据以后新接受的公理得出。在该命题得出真假值之前，直觉主义观点不赋予它在逻辑系统中合法的公理地位。也就是说，我们在直觉上无法构造一个具有实际意义的能被人们接受的程序得出它的真假。
纯粹形式主义逻辑作为人类认识世界的思维工具没有给直觉上的“真”以合法的公理地位，这使得其公理系统的完备化具有很大的自由度，因为它仅仅需要满足一致性条件且本着方便性原则对那些不能被证明但具有一致性的逻辑命题做出选择以作为该逻辑系统的一条公理。建立在此基础上的科学理论体系往往不具有可靠的经验基础。而直觉主义在公理的确立及完备化上归根到底有一个约束机制，即必须是直觉上可接受的（能行可判定的），有效地减少了理论建构的随意性。建构在此基础上的科学理论体系就有了扎实的经验事实基础，也是用实践检验真理的理论依据。
柯尔莫哥洛夫对传统直觉主义作了批判，他写道：“我们否认数学对象是简单的精神活动的成果，……事实上是独立于我们思维的现实存在形式的抽象”[3]。有限推理的合理性证明经常由无限推理构成，这自然使柯尔莫哥洛夫深入到无限推理的逻辑前提，探讨它们的意义。柯尔莫哥洛夫在其两篇论文“论排中律”（简称TNDP）和“关于直觉主义逻辑的解释”（简称IIL）中致力于对直觉主义逻辑的进一步研究，否认第5公理和排中律作为逻辑系统公理的合法地位。美国著名数理逻辑学家王浩(Wang Hao)，在TNDP的英译本前言中写道：“该论文不仅希望对Heyting的直觉主义逻辑形式化作进一步扩展，而且促成了传统数学与直觉主义数学的可变换性，确立了直觉主义数学基础在其他方面研究的重要关系。”[4]柯尔莫哥洛夫对传统直觉主义进行了革命性的改造，他给数学命题赋予了实际意义。
然而，排除第5公理和排中律使希尔伯特逻辑系统产生很大局限性，事实上存在许多不用排中律就无法证明的命题。如布劳威尔给出的一个很好的例子：每个实数可以被表示成为一个有限的十进分数这一命题不能被认为是已被证明了的。它的证明必须借助于排中律。鉴于此，柯尔莫哥洛夫对传统直觉主义逻辑在数学上作了进一步地扩展。他指出：“尽管排中律不能作为一般命题逻辑的公理，但是，在命题的有限范围（布劳威尔把它们称为有限命题）内它是有效的。”[5]在TDNP一文中，柯尔莫哥洛夫把一般命题逻辑系统（希尔伯特公理系统中的四个蕴涵公理和一个否定公理）扩展成为有限命题逻辑系统（在一般命题逻辑系统中引入双重否定公理
）。柯尔莫哥洛夫发展的有限命题逻辑系统成为建构递归函数论、算法理论以及算法信息论逻辑基础。
柯尔莫哥洛夫发展起来的直觉主义的逻辑既承认经验在人类认识中的基础性作用和形式化（经验上为真的命题作为公理）的合理性，又强调以逻辑推理为主要形式的理性思维在把握客观世界和其他认识对象的重要性；逻辑命题的真假问题的判定是能行可构造的（IIL提出的语义学使直觉主义逻辑转变为可构造性逻辑成为可能）。这一思想成为他建构理论的逻辑起点，并贯彻到了递归函数论、算法理论、信息论和概率论的基本概念中，成为许多分支学科的基石和许多理论体系得以建立和发展的一颗充满生机的种子。
2 直觉概念的形式化
柯尔莫哥洛夫对排中律进行的批判和对传统直觉主义逻辑的发展，为直觉概念的形式化和开创新学科或新学科分支奠定了基础。他认为“只要引入一个适当的符号系统，我们就可以形成一个用符号构造的求解图式系统的一个形式演算”[6]。既然我们所考虑的对象是实际问题，柯尔莫哥洛夫试图用问题演算涵盖命题演算，建立处理两类对象——命题和问题的一个统一的逻辑工具。柯尔莫哥洛夫认为，对命题公理系统的批判性研究绝不是定义基本概念和证明命题逻辑公理的问题，而是如何使用这些逻辑概念和方法的直觉源泉。同样，直觉概念形式化系统的构建首先关注的是这些逻辑概念和方法的直觉源泉，进而建立起直觉概念于逻辑系统之间的内在关联。
(1)建立算法和递归函数在直觉意义上的等价关系 递归函数是指由一些可计算的基本函数根据一定的演算规则复合而成的函数。其中基本函数（以及后继函数等）的可计算性被认为是人类的最基本的计算能力所能够达到的；演算规则被认为是符合人类最简单的逻辑推理能力规则。递归函数及其演算相当于一个形式逻辑系统，基本函数相当于逻辑前提，演算规则相当于逻辑推理运算。递归函数是把实际问题的求解过程形式化为逻辑命题演算的桥梁。
直觉主义的能行可构造性在数学或计算机科学中形式化为能行可计算性。柯尔莫哥洛夫考察了四种关于“算法”的直觉概念后认为，用严格的数学术语定义一个严密的反映所有这些算法直觉概念的定义是可能的。为了得到算法的更一般的数学形式，柯尔莫哥洛夫又分析了五种算法或可计算函数的不同形式的数学定义，进而明确地地指出，算法的最一般概念很自然地与部分递归函数联系起来。因此，定义一个算法问题在本质上等于定义一个可计算函数即递归函数的问题。
算法概念的形式化成为今天人类的主要认识手段——计算机科学和信息论在逻辑基础建设过程中的重要环节，并且催生了计算和算法复杂性概念的诞生。
(2)概率论的直觉主义逻辑基础 柯尔莫哥洛夫对概率论的研究兴趣始于1924年。当时，有关概率论方面的研究非常多，但却缺乏基础性意义。1931年，柯尔莫哥洛夫发表了论文“概率论中的分析方法”，奠定了现代马尔可夫过程理论的基础。他在1933年出版的德语著作《概率演算的基础》深入地研究了概率论前提假设（R.von Mises的频率稳定性），重新建构了概率论的逻辑基础，成为他开创随机过程理论的一个必要基础。Gnedenko对柯尔莫哥洛夫在概率论方面的工作评价中写道：“在概率论的历史中，难以找到以如此决定性的方式改变已经建立起来的观点和基本倾向的研究著作，它标志着概率论一个新的发展阶段的开始。”[7]
概率论所处理随机事件在数学形式意义上和在直觉意义上的涵义上往往并不相同。直觉意义上的随机事件指的是那些我们不能发现任何规律性以使我们预测它们行为的现象。柯尔莫哥洛夫认为没有任何直接理由说明这种意义上的随机事件遵守概率论。然而，为什么概率论完全可以应用到现实世界的随机现象中呢？该问题的本质内涵可以通过算法理论和递归函数论做出解答。
从历史上看，柯尔莫哥洛夫对概率论逻辑基础的考察根植于R.von Mises关于随机的无限序列的概念。Mises提出了概率论应用的基本假设为频率的稳定性，即概率的传统定义为：
p=m/n (1)
其经验基础是自然界中的许多现象具有频率稳定性特点。对这一直觉观念的考察以及试图用形式化的数学语言给予表述就成为概率论应用的一个重要逻辑前提。定义（公式1）表示的是所有事件结果中占优势的结果数目与总数目的比率。假设有一个由0-1组成的长为n，包含m个“1”的序列。可以通过某种方法从该序列中得到两个子序列，比较每个子序列中“1”的频率之差
柯尔莫哥洛夫认为直接把它作为概率论的一个定理应该作进一步的规范，即限定子序列的选择规则。实际上，第一个把算法和递归函数应用到概率论的是丘奇(A.Church)。1940年丘奇已经提出了一个Mises随机序列的算法形式，但是结果并不令人满意。柯尔莫哥洛夫在对直觉主义逻辑、递归函数论和算法理论所做的发展的基础上指出：这样的选择规则可以由一个算法（或图灵机）得到。
3 对信息论逻辑基础的批判、建构与复杂性概念的建立
柯尔莫哥洛夫对信息论的研究主要受到维纳(N.Wiener)和香农(C.Shannon)20世纪50～60年代在信息论方面的工作的影响。
(1)信息论的组合基础 柯尔莫哥洛夫的数学家眼光和批判精神使他直接深入到信息论的根基，把信息论的逻辑前提放在一个更加基础的背景下考察。柯尔莫哥洛夫特别强调“信息量定义的逻辑方法对任何概率论假设的逻辑独立性”，[8]并且提出了一个全新的观点：“信息论在逻辑上要先于概率论出现，而不是以后者为基础”；信息论的逻辑基础应该为有限组合性质。
香农的信息公式是基于概率论的，即
通常用熵表达信息的基本概念。柯尔莫哥洛夫给出了最基本的条件熵的数学表达形式
H（x｜y）=H(x)-H(x,y)
(4)
即条件熵H(x｜y)为在y已知的情况下x的熵。用φ表示“必然知道的对象”，我们得到条件熵
H（x｜φ）=H(x)
这样，(1)(2)两式的差就可以表示在y中所包含的x的信息
自然地，我们有
I（x｜x）=H(x)
用熵来定义信息是传统信息论的基础，但柯尔莫哥洛夫并没有停留在这一层面上，而是深入考察熵的定义，对信息论前提作了重要的批判工作。一般地，熵的概念用概率定义，形式同(3)。其含义与个体对象无关，而只是与“随机”事件（对象）的概率分布有关。这间接地决定了信息概念在含义上也是一个统计意义上的概念，与个体对象无关。然而并不是所有的信息论应用都满足这种统计要求。
为了弥补信息的概率定义的这一局限，柯尔莫哥洛夫把概率计算问题归结为组合问题。公式(3)表示：如果有n（n很大）个相互独立事件，且每个事件有个可能结果，那么，为了确定其中的一个事件，我们需要大约nH个二进制位数。但这一结果在完全组合的假设情况下有效。为了得到事件的结果，只要知道每一事件的出现的次数
和事实上（可能）发生的结果的数目
这一结果与公式(3)相比不但满足大数定理，也适合单个事件的情况，因此它具有更大的普适性，而信息的概率定义可以作为信息的组合定义的一种特殊情况。
(2)“柯尔莫哥洛夫复杂性”定义 直观意义上的“复杂性”是和“简单性”相对而言的，它们与“真”和“能行过程”一样都是非形式化概念。信息论的出现，使得“复杂性”概念的形式化成为可能。一般来讲，如果一个对象是“简单的”，对于它的描述需要很简短的表述，即需要很少的信息，如果一个对象是“复杂的”，对它的描述需要很长的表述，即需要更多的信息。因此，复杂性的涵义在于：复杂性的对象需要更长的描述，“复杂性”的定义自然地与对象的描述长度联系起来。然而，由于概率概念是当事件的数量趋于无穷时的极限概念，决定了信息的概率概念具有同样的特点，因此不能证明可以把概率信息概念应用到有限事件的实际问题中去，即复杂性不能用传统概率信息所表征的描述长度度量。
随着有限对象的一般描述以及描述复杂性、随机性和先验概率概念的递归不变方法的发现，柯尔莫哥洛夫建立了信息论的算法逻辑基础。正如柯尔莫哥洛夫所说的：“除了已经接受的信息量的概率论定义外，在许多情况下，其他方法是可能的和自然的：组合方法和代数学方法导致一个新的科学分支——算法信息论即柯尔莫哥洛夫复杂性理论的出现。”[9]1965年，柯尔莫哥洛夫在不知索莫戈洛夫工作的情况下，用算法理论把描述有限对象的复杂性定义为算法上可构造的可生成对象的最短程序长度。
我们把所描述的对象集合中的元素通过一个映射枚举出来，形成函数n=S(p)。进一步地，如果该函数是可计算的，则这种表达方式被称为是“有效的”。在所有这些描述中，把最小描述长度作为“复杂性”的量度，即柯尔莫哥洛夫复杂性定义为
该定义似乎是依赖于所使用的算法。然而，证明存在描述对象复杂性的普适方法。尽管有许多优化方法，但是相应的复杂度之间的差别不超过某一附加常数。
可以看出，柯尔莫哥洛夫算法复杂性概念的逻辑基础为：递归的、可枚举的和可计算的。因此，算法复杂性是对一类复杂对象的描述。柯尔莫哥洛夫还指出了该复杂性定义的一个基本缺陷：它没有考虑用程序p生成对象x的“困难”。[10]这一缺陷成为后来在复杂性研究中的一个重要概念——“深度”的研究动力和起点；与此相对应，我们估价根据复杂对象得到它的图式，即程序p的“艰难性”也成为度量复杂性的新维度——“隐蔽性”概念的思想源泉。它们都是衡量人们在认识复杂对象过程中所付出的“代价”。
(3)用“复杂性”重构“随机性”前提假设 传统的“随机性(randomness)”通常指的是缺乏“规则性(regularity)”。规则性好的序列其描述长度必定很短，如对十进制序列127403112740311274031…，的描述可以用“重复打印1274031”来表示，其复杂性很小；而规则性差的序列其描述长度也不一定很长，如序列π的值3.141592…，它满足几乎所有的随机性测试，但是用很短的描述“打印π”即可得到该序列，其复杂性很大。因此，柯尔莫哥洛夫复杂性并不是传统随机性大小的量度。
根据von Mises的观点，传统概率论应用的基础是频率稳定性假设。例如，假设有一串用0-1表示的长度n为且有m个1的事件结果序列1101000111001011……，如果1出现的概率
m/n～p(7)
并不随着其子序列的选择而发生变化，那么，就认为1的出现是随机的。
这一要求可以用一个更简单方法描述：满足上式的0-1序列的复杂性不可能超过
nH(p)=n(-plogp-(1-p)log(1-p))
(8)
柯尔莫哥洛夫进一步证明了，如果序列的复杂性充分接近(8)式的上界，则von Mises的频率稳定性条件自动得到满足。由此可以得到，如果一个有限对象的复杂性不少于对它本身的描述长度，那么自然地认为该对象是随机的。这样柯尔莫哥洛夫从复杂性概念定义了随机性概念，而不是相反。
对柯尔莫哥洛夫的各个领域的工作做一个全面的总结是很困难的，人们越是沿着柯尔莫哥洛夫复杂性概念进行各个领域复杂性研究和探索就越是满怀着对这位数学天才和思想巨人的深深敬意，这种动力也推动人们不断在复杂性研究上继续探索下去。
收稿日期：2003-04-04
标签：数学论文; 信息论论文; 概率论论文; 命题逻辑论文; 递归函数论文; 概率计算论文; 柯尔莫哥洛夫论文; 公理系统论文; 基础数学论文; 逻辑函数论文; 随机算法论文; 关系逻辑论文; 形式化方法论文; 统计学论文; 应用数学论文;