柯尔莫哥洛夫：“复杂性研究中的欧几里德”，本文主要内容关键词为：欧几里德论文,洛夫论文,复杂性论文,柯尔论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
〔中图分类号〕K81 〔文献标识码〕A 〔文章编号〕1000-0763(2003)06-0089-06
安德烈·尼古拉耶维奇·柯尔莫哥洛夫（Andrei Nikolaevich Kolmogorov，1903年4月25日—1987年10月20日），由于在概率论中做了公理性奠基工作，他被美誉为“概率论中的欧几里德”，著名的KAM理论中打头的字母K指的就是他，[1]他毫无疑问是20世纪苏联最伟大、最著名的数学家，也是20世纪世界最伟大的数学家之一。
2003年是柯尔莫哥洛夫诞辰100周年。作为从事复杂性哲学问题研究的中国学者，我们非常钦佩柯尔莫哥洛夫在复杂性概念发展过程中所做出的开创性的工作和贡献，20世纪后半叶发展起来的复杂性学科探索可以说绝大部分建基于柯尔莫哥洛夫复杂性概念基础上或是受到柯尔莫哥洛夫复杂性研究的激励的。因此，我们改那个美誉为“复杂性研究中的欧几里德”，并以此文纪念柯尔莫哥洛夫及其复杂性研究工作。[2]
一、人生旅程：生平和荣誉
柯尔莫哥洛夫于1903年4月25日出生在俄国的坦博夫(Tambov)市，1987年10月20日逝世于莫斯科。据圣安德鲁斯大学关于柯尔莫哥洛夫的传记介绍，柯尔莫哥洛夫的父亲尼古拉依·卡塔耶夫(Nikolai Kataev)，一个牧师的儿子，是一个被沙俄流放的农艺学家，十月革命后曾经做过政府农业部的头，1919年死于战斗。柯尔莫哥洛夫的母亲玛利亚·雅科夫列夫娜·柯尔莫哥洛娃(Maria Yakovlena Kolmogorova)难产而死。于是姨妈抚养了他，成为他的真正意义上的母亲。柯尔莫哥洛夫对他的姨妈维拉·雅科夫列夫娜·柯尔莫哥洛娃(Vera Yakovlena Kolmogorova)怀有很深的感情。柯尔莫哥洛夫的童年时代是在伏尔加河畔的俄罗斯西部城市雅罗斯拉夫尔的外祖父家（后来在柯尔莫哥洛夫6岁时迁居到了莫斯科）渡过的。柯尔莫哥洛夫这一姓氏就来自于他的外祖父雅科夫·斯捷潘诺维奇·柯尔莫哥洛夫(Yakov Stepanovich Kolmogorov)。
据说，柯尔莫哥洛夫的青少年生活十分艰难。第一次世界大战以及当时俄国布尔什维克革命后的流血冲突，内战和随之而来的饥荒，苏联红军与白军争夺政权时拉锯般的流血和恐怖，年少的柯尔莫哥洛夫自然躲也躲不过去。但是，外祖父家境毕竟还是不错，所以，柯尔莫哥洛夫6岁被送入当时最好的一个法文学校学习。据说在智慧和学习方面，柯尔莫哥洛夫5-6岁时就表现出来数学天才。发现了：1=1×1,1+3=2×2,1+3+5=3×3,1+3+5+7=4×4。
1919-1920年革命刚刚结束以后的一段时间，柯尔莫哥洛夫离开学校在铁路做过工作以维持生计。1920年，17岁的柯尔莫哥洛夫进入莫斯科大学学习。但是开始时，他并不完全钟情于数学，而是把兴趣安置在历史方面，除数学外，他“研究”了冶金和俄罗斯历史。当然，历史不是这段他研习课程的唯一主题，事实上他很严肃的写了一篇关于15-16世纪诺夫哥罗德城的财产主权的科学文章。关于这篇文章的写作，肯德尔(Kendall)等人讲述了一个佚事：老师看了这篇文章后对柯尔莫哥洛夫说，你只为你的报告提供了一个证据，在数学上你的研究或许是充足的，但是我们的历史学研究至少需要10个证据。[3]柯尔莫哥洛夫一听，数学的严谨性和确定性与历史的模糊性和歧义性的差异是如此之大，于是柯尔莫哥洛夫转向了数学，他更喜欢可以严谨使用唯一证明的学科。柯尔莫哥洛夫后来常常把它作为一个笑话来谈。但是，数学只需要一个证明就可以的说法，也许当真就驱使柯尔莫哥洛夫更喜好数学了呢。柯尔莫哥洛夫进入莫斯科大学注册时是在冶金化学系，但是很快改学数学的决定可能与此有关，这使得柯尔莫哥洛夫从此再也没有离开过莫斯科大学数学和力学系。
成为学生的第一年，他在学习方面遇到了三位苏联著名数学家——鲁金（也有译为卢津，N.N.Luzin）、弗拉索夫(P.S.Urysohn)、斯捷潘诺维夫(V.V.Stepanov)，他们分别在函数理论、射影几何和三角级数方面有很深的造诣。而他妻子安娜的父亲，莫斯科大学知名教授依戈罗夫可能也对他影响很深。在他们主持的讨论班上，柯尔莫哥洛夫显示了自己的数学直觉天才，而且其数学技能也得到了飞速发展。第一年，即18岁时，他完成了一项关于三角级数方面的研究；第二年，他的有关集合论的一个研究成果发表；而在第三年，即1922年，他构造的一个几乎处处发散的三角级数例子，解决了傅立叶级数密切相关的重要问题，这个成果发表后，立刻使他赢得了苏联数学科学界的认可。
柯尔莫哥洛夫1925年毕业于莫斯科大学，由于他在数学方面的出色表现——1922年到1925年他还是学生时期就已经解决了若干重要数学问题，分别发表了10篇论文（1923年2篇，1924年2篇，1925年6篇）——立刻成为鲁金的学生和助手。
柯尔莫哥洛夫直到39岁时（1942年）才结婚。他的妻子是安娜·达米特耶维娜·依戈罗夫(Anna Dmitri yevna Egoroy)，他们没有自己的孩子。安娜的父亲达米特·费德罗耶维奇·依戈罗夫也是莫斯科大学一个当时很有影响的数学教授，然而他具有很深的宗教倾向，并且反对在大学里讲马克思主义的方法论，1929年被解除了莫斯科大学数学和物理研究所主任职务，随后不久被作为宗教宗派主义者、反动分子而逮捕并被投入监狱，据说依戈罗夫曾以绝食抗争，后终因身体衰弱等原因于1931年在狱中逝世。从柯尔莫哥洛夫的事业发展看，这件事情并没有影响柯尔莫哥洛夫本人，虽然柯尔莫哥洛夫是在11年后娶依戈罗夫的女儿为妻的。反过来看，在20世纪40年代二战期间的苏联，柯尔莫哥洛夫能娶安娜为妻，也反映了柯尔莫哥洛夫的人格品德。当然在苏联学者和官方的传记里，向来对此讳莫如深。
下面是柯尔莫哥洛夫的学术生涯的一个并非完整的履历清单：
1929年获得了博士学位；同时进入莫斯科大学任教。
1931年成为莫斯科大学数学教授。
1933到1939年，莫斯科大学数学科学研究所主任。
1938到1966年，在莫斯科大学，一直主持概率论讲座。
1939年当选为苏联科学院院士并且担任了数学物理部的秘书，苏联大百科全书的数学部分的主编。
1946年到1954年，并从1983年起他一直是苏联数学研究杂志的主编(Editor-in-chief of Uspekhi Math.Nauk(Russian Mathematical Surveys))。
1951年到1953年，莫斯科大学数学和力学所主任。
1954年到1956年，1978年到至少1983年，数学和力学系的数学部主任。
1954年到1958年，大学数学和力学学院院长。
1965年首次获得列宁奖章(Lenin Prize)，他还获得过十月革命奖章和苏联英雄的称号。
1964年到1966年，并从1976年到1983年，柯尔莫哥洛夫一直是莫斯科数学学会的会长。
1966年到1976年，全苏联统计方法实验室主任。
1976年到1980年，他是他所创立的数学统计学学会的主席。
从1980年起，他是数理逻辑学会的主席。
柯尔莫哥洛夫是苏联数学家中当选国外科学院和科学社团会员最多的一个，大约超过20个，其中包括：荷兰皇家科学院(Royal.Netherlands Academy of Sciences,1963)；伦敦皇家学会(he London Royal Society,1964)；美国国家学会(the USA National Society,1967)；巴黎科学院(the Paris Academy of Sciences,1968)；波兰科学院(the Polish Academy of Sciences,1956)；罗马尼亚科学院(the Rumanian Academy of Sciences,1956)；德国利奥波德尼亚科学院(the German Academy of Sciences Leopoldina,1959)；波士顿的美国科学和艺术院(the American Academy of Sciences and Arts in Boston,1959)。他还被巴黎、柏林、华沙、斯德哥尔摩等大学授予荣誉博士学位；他也是莫斯科、伦敦、印度和加尔各答数学学会、伦敦皇家统计学会、国际统计学会和美国气象学会的荣誉会员。
1963年，被授予国际巴尔扎恩奖(Bolzano Prize)。
1980年，获得具有数学领域终身成就奖的沃尔夫奖(Wolf Prize)。
二、前赴后继：科学教育与学生培养
柯尔莫哥洛夫在数学之外也具有许多浓厚兴趣，例如他曾经研究过数学教育和一般社会问题。特别在学生培养方面，他堪称大师。在研究所里他不仅指导自己的学生，而且关心其他学生的成长。他经常和挚友亚历山德罗夫带领学生在莫斯科郊外远足郊游，这种远足有时长达40公里，远足后在他们郊外的别墅举行宴会。这时，柯尔莫哥洛夫的幽默和睿智就发挥的淋漓尽致，而柯氏的学生们便大大受益了，师生的交流象涓涓溪流一样汇入苏联数学的“伏尔加河”，使它源源不断、向前流去。
柯尔莫哥洛夫非常善于启发学生，由于他在思考数学重大问题的那种直觉，他经常能够触及到问题的本质，但是其后的证明的问题，他常常把它们留在他指导学生的教学黑板上。象希尔伯特的第十三个问题，他的思想就启发了他的学生阿诺德，最后由阿诺德解决了这个难题。智力的刺激和广泛的文化熏陶对学生成长起了重要作用。
柯尔莫哥洛夫一生当中直接培养的学生有60-70名，其中包括：
成为苏联科学院院士的，米林斯奇科夫(M.D.Millionshchikov)，后来成为苏联科学院副院长；马尔采夫(A.I.Mal'tsev)；尼科尔斯基(S.M.Nikol'skii)；盖尔范德(I.M.Gel'fand)；史拉兹丁诺夫(S.C.Sirazhdinov)；普罗霍罗夫(Yu.V.Prokhorov)；奥布霍夫(A.M.Obukhov)。
成为苏联科学院通讯院士的，博尔舍夫(Bolshev)；布罗夫科夫(A.A.Borovkov)；莫宁(A.S.Monin)；阿诺德(V.I.Arnold)；塞瓦斯梯亚诺夫(B.A.Sevastiyanov)。
成为乌克兰科学院院士的，格涅坚科(B.V.Gnedenko)；米哈列维奇(Mikhalevich)。
其他还有：巴维利(Bavli)，维奇琴科(Verchenko)，希罗夫(Shilov)，和布林斯基(Bulinskii)等数十人。这些学生的研究领域主要分布在理论地球物理学(theoretical geophysics)、数理逻辑(mathematical logic)、泛函分析(functional analysis)、概率论(probability theory)、函数论(function theory)等方面。
自1978年到2001年全世界共有39名数学家获得Wolf奖，其中俄罗斯或苏联数学家共6名，而柯氏及其学生就占了其中4位。而且特别有意思的是，这四位中，首先是学生盖尔范德，他主要因为对泛函分析、群表示论的工作而获得1978年首届Wolf奖；然后是老师柯尔莫哥洛夫本人（1980年，因为对概率论、调和分析、动力系统作出重要贡献而获奖）；再次是赛奈，他因为对统计力学中数学严格方法、动力系统的遍历理论作出重要贡献而获得1997年Wolf奖；最后是柯尔莫哥洛夫最得意的门生阿诺德，他因对动力系统、微分方程、奇点理论作出重要贡献而获得2001年Wolf奖。看看这些获奖工作的主要方向，人们不难发现，它们都与柯尔莫哥洛夫所开先河的工作以及在柯尔莫哥洛夫更先前的俄罗斯数学家的工作有关。
柯尔莫哥洛夫晚年始终关心苏联的数学教育，特别是数学的基础教育。他花费了大量精力，从事数学普及工作，写作教科书，培养数学基础人才。苏联之所以保持为一个数学的超级大国地位，其中也有这位苏联数学教育家的重要贡献。
三、奠基研究：概率论、信息论和复杂性
除了数论外，柯尔莫哥洛夫的研究覆盖了几乎所有的数学研究领域，在其一生中，他发表了超过300篇的研究论文，专论和教科书。柯尔莫哥洛夫极富数学直觉的天赋，他不但能够迅速识别问题的重要性，而且能够迅速领悟问题可能的答案，直接到达研究的彼岸。其次，柯尔莫哥洛夫在研究上是一个“快枪手”。他的同事和挚友亚历山德罗夫说，“数学天才有两类：‘快’的和‘慢’的。希尔伯特属于‘慢’的天才，而柯尔莫哥洛夫无疑是‘快’的天才”。[4]就研究贡献看，概率论的基础完善、信息论概念的清晰化和复杂性概念的建立无疑是柯尔莫哥洛夫留给后人的最卓著的成就。
柯尔莫哥洛夫对概率论的兴趣产生于1924年，1933年他以类似欧几里德的几何学的基础公理方法建立了严格的概率论。因此，他的学生、合作者，解决了希尔伯特著名的第13个问题的数学家，也是著名的KAM理论的创始人之一的阿诺德称柯尔莫哥洛夫为“概率论中的欧几里德”。
在1924年时，有关概率论方面的研究非常多，但却缺乏基础性意义。1931年，柯尔莫哥洛夫发表了论文“概率论中的分析方法”，奠定了现代马尔可夫过程理论(the modern theory of Markov processes)的基础。他在1933年出版的德语著作《概率演算的基础》深入地研究了概率论前提假设（米泽斯[R.von Mises]的频率稳定性），重新建构了概率论的逻辑基础，成为他开创随机过程理论的一个必要基础。格涅坚科对柯尔莫哥洛夫在概率论方面的工作评价中写道：“在概率论的历史中，难以找到以如此决定性的方式改变已经建立起来的观点和基本倾向的研究著作，它标志着概率论一个新的发展阶段的开始。”[5]
概率论所处理随机事件在数学形式意义上和在直觉意义上的涵义上往往并不相同。直觉意义上的随机事件指的是那些我们不能发现任何规律性以使我们预测它们行为的现象。柯尔莫哥洛夫认为没有任何直接理由说明这种意义上的随机事件遵守概率论。然而，为什么概率论完全可以应用到现实世界的随机现象中呢？该问题的本质内涵可以通过算法理论和递归函数论作出解答。
从历史上看，柯尔莫哥洛夫对概率论逻辑基础的考察根植于米泽斯关于随机的无限序列的概念。米泽斯提出了概率论应用的基本假设为频率的稳定性，即概率的传统定义为，其经验基础是自然界中的许多现象具有频率稳定性特点。对这一直觉观念的考察以及试图用形式化的数学语言给予表述就成为概率论应用的一个重要逻辑前提。它表示的是所有事件结果中占优势的结果数目与总数目的比率。
柯尔莫哥洛夫认为直接把它作为概率论的一个定理应该作进一步的规范，这就提出了把算法作为概率论基础的基本思想。实际上，第一个把算法和递归函数应用到概率论的是丘奇(A.Church)。1940年丘奇已经提出了一个米泽斯随机序列的算法形式，但是结果并不令人满意。柯尔莫哥洛夫在对直觉主义逻辑、递归函数论和算法理论所做的发展的基础上指出：这样的选择规则可以由一个算法（或图灵机）得到。
信息论出现后不久，柯尔莫哥洛夫立刻觉察到它的重要性。针对申农等人把信息概念建立在概率基础上的倾向和做法，柯尔莫哥洛夫立刻发现这可能存在问题，他认为“信息量定义的逻辑方法对任何概率论假设〔具有〕逻辑独立性”，并且提出了一个全新的观点：“信息论在逻辑上要先于概率论出现，而不是以后者为基础”。[6]他认为信息论的逻辑基础应该为有限组合。
用熵来定义信息是传统信息论的基础，但柯尔莫哥洛夫并没有停留在这一层面上，而是深入考察熵的定义，对信息论前提作了重要的批判工作。一般地，熵的概念用概率定义。其含义与个体对象无关，而只是与“随机”事件（对象）的概率分布有关。这间接地决定了信息概念在含义上也是一个统计意义上的概念，与个体对象无关。然而并不是所有的信息论应用都满足这种统计要求。
为了弥补信息的概率定义的这一局限，柯尔莫哥洛夫“把概率计算问题归结为组合问题。”[7]如果有n（n很大）个相互独立事件，且每个事件有s个可能结果，那么，为了确定其中的一个事件，我们需要大约nH个二进制位数。但这一结果在完全组合的假设情况下有效。为了得到事件的结果，只要知道每一事件的出现的次数
和事实上（可能）发生的结果的数目
此时，我们只需要不超过个二进制位数就可以。当n足够大时，上式变为
这一结果不但满足大数定理，也适合单个事件的情况，信息的概率定义可以作为信息的组合定义的一种特殊情况，因此它具有更大的普适性。
1965年他把复杂性测度引入随机性算法理论，建立了复杂性概念，即现在提及的柯尔莫哥洛夫复杂性(KolmogorovComplexity)。按照柯尔莫哥洛夫，一个对象的复杂性就是能够再现该对象的计算机程序的最短长度。他认为，随机对象本身就是它们的最短描述。于是，周期序列就具有很低的柯尔莫哥洛夫复杂性，这表明，柯尔莫哥洛夫复杂性概念是一种随机性测度，接近于一个信息源的申农(ClaudeShannon)熵的概念。
直观意义上的“复杂性”是和“简单性”相对而言的，它们与“真”和“能行过程”一样都是非形式化概念。信息论的出现，使得“复杂性”概念的形式化成为可能。一般来讲，如果一个对象是“简单的”，对于它的描述需要很简短的表述，即需要很少的信息，如果一个对象是“复杂的”，对它的描述需要很长的表述，即需要更多的信息。因此，复杂性的涵义在于：复杂性的对象需要更长的描述，“复杂性”的定义自然地与对象的描述长度联系起来。然而，由于概率概念是当事件函数量趋于无穷时的极限概念，决定了信息的概率概念具有同样的特点，因此不能证明可以把概率信息概念应用到只有有限事件的实际问题中去，即复杂性不能用传统概率信息所表征的描述长度度量。
随着有限对象的一般描述以及描述复杂性、随机性和先验概率概念的递归不变方法的发现，柯尔莫哥洛夫建立了信息论的算法逻辑基础。正如柯尔莫哥洛夫所说的，“除了已经接受的信息量的概率论定义外，在许多情况下，其他方法是可能的和自然的：组合方法和代数学方法导致一个新的科学分支——算法信息论即柯尔莫哥洛夫复杂性理论的出现。”[8]1965年，柯尔莫哥洛夫在不知索罗莫戈洛夫工作的情况下，用算法理论把描述有限对象的复杂性定义为算法上可构造的可生成对象的最短程序长度。
柯尔莫哥洛夫的其基本思想如下：把所描述的对象集合中的元素通过一个映射枚举出来，形成函数n=S(p)。进一步地，如果该函数是可计算的，则这种表达方式被称为是“有效的”。在所有这些描述中，把最小描述长度作为“复杂性”的量度，即柯尔莫哥洛夫复杂性定义为
可以看出，柯尔莫哥洛夫算法复杂性概念的逻辑基础为：递归的、可枚举的和可计算的。因此，算法复杂性是对一类复杂对象的描述。柯尔莫哥洛夫还指出了该复杂性定义的一个基本缺陷：它没有考虑用程序P生成对象x的“困难”。这一缺陷成为后来在复杂性研究中的一个重要概念——“深度”(depth)的研究动力和起点；与此相对应，我们估价根据复杂对象得到它的图式，即程序P的“艰难性”也成为度量复杂性的新维度——“荫蔽性”概念的思想源泉。它们都是衡量人们在认识复杂对象过程中所付出的“代价”。
传统的“随机性”(randomness)通常指的是缺乏“规则性”(regularity)。规则性好的序列其描述长度必定很短，如对十进制序列127403112740311274031……，的描述可以用“重复打印127403”来表示，其复杂性很小；而规则性差的序列其描述长度也不一定很长，如序列的值3.141592……，它满足几乎所有的随机性测试，但是用很短的描述“打印”即可得到该序列，但其复杂性很大。因此，柯尔莫哥洛夫复杂性并不是传统随机性大小的量度。
根据米泽斯的观点，传统概率论应用的基础是频率稳定性假设。例如，假设有一串用0-1表示的长度为n且有m个1的事件结果序列1101000111001011……，如果1出现的概率m/n～p并不随着其子序列的选择而发生变化，那么，就认为1的出现是随机的。
柯尔莫哥洛夫进一步证明了，如果序列的复杂性满足某种条件，则米泽斯的频率稳定性条件自动得到满足。由此可以得到，如果一个有限对象的复杂性不少于对它本身的描述长度，那么自然地认为该对象是随机的。
在对一些对象的表述中，如果其他一些对象是已知的，那么，它的复杂性可能减少。这一事实反映了条件复杂性的定义，即在已知对象的情况下，的复杂性为
如果条件复杂性
比非条件复杂性K(x)小，那么，我们自然认为对象y包含“关于对象x的信息”。其差值
被认为是包含在中的信息量。
在上式中，令y=x，则有
表示包含于对象本身中的信息量。这样，柯尔莫哥洛夫用复杂性概念定义了信息量概念，在逻辑上与用信息定义复杂性相反。于是，在柯尔莫哥洛夫的研究道路上，柯尔莫哥洛夫自然而然的通过概率论、信息论和随机性的研究，最终走上了对复杂性研究的道路，并且使得柯尔莫哥洛夫复杂性概念成为复杂性研究中一个最基础性的概念，从而成为21世纪复杂性的进一步研究的历史和逻辑的起点。
1973年，苏联科学院数学部、莫斯科数学学会和苏联数学学报编辑部在柯尔莫哥洛夫诞辰70周年之际对他所研究的领域及做出的成就作了一个概括，我们愿意把它仍然作为对柯尔莫哥洛夫一生的研究和教育事业的评价，来表达对柯尔莫哥洛夫及其复杂性研究的崇敬：“您对现代数学的发展及其应用做出了杰出的贡献。您的基础性研究决定了20世纪数学领域许多分支的整个发展图景。三角级数理论、测度论、集合论、积分理论、可构造性逻辑、拓扑学、渐近理论、概率论、随机过程理论、信息论、数理统计、动力系统、有限自动机、算法理论、数理语言学、湍流理论、天体力学、积分方程、希尔伯特的第13问题、弹道理论和在生物学、地理学、金属结晶学中的数学应用，是您所涉及到的数学分支和您深邃的思想所丰富起来的理论应用的一个不完备列表。您总是把数学应用与数学和其他学科建立起重要的联系。您广博的研究兴趣和教育天赋总能吸引许多年轻的科学家。”[9]
〔收稿日期〕2003年3月25日
标签：莫斯科大学论文; 数学论文; 信息论论文; 概率论论文; 苏联数学论文; 柯尔莫哥洛夫论文; 概率计算论文; 数学文化论文; 基础数学论文; 随机算法论文; 应用数学论文; 统计学论文;