Profiel van Wenjiefwjmath的相空间WeblogLijstenGastenboekMeer  |  Extra Help |
|
|
27 september 希尔伯特之梦，以及梦的破灭（作者删节版）注：本文遵守首页上的CC版权声明，严禁商业性媒体和网站未经本人同意的转载，个人转载请注明作者与出处，谢谢！ 本文来源：科学松鼠会。http://songshuhui.net/archives/20161.html Wir müssen wissen, wir werden wissen. 我们必须知道，我们必将知道。 你听到的，正是80年前，1930年，希尔伯特在他退休时演讲的最后六个单词，也是鼓舞一代数学家的六个单词。尽管当时第三次数学危机仍然阴魂不散，但他们坚信，数学大厦的基础是坚实的。他们也坚信，任何数学真理，只要通过一代又一代人的不断努力，都能用逻辑的推理将其整合到数学的大厦中。 这是何等的气魄！这是何等的梦想！ 但就在演讲前夕，他的同胞哥德尔，作出了一个断言，彻底打碎了这个梦。 希尔伯特计划希尔伯特是一位名副其实的数学大师，有人将他称为“数学界最后一位全才”，他看待数学的眼光也是相当深刻的。 师从林德曼，希尔伯特在23岁便以一篇关于不变量理论的论文跻身数学界。他的证明方法在当时相当具有争议性。在这篇论文中，他使用了非构造性的证明，也就是说他只能证明某个数学对象的存在性，却无法将它具体指出。另外，他的证明依赖于对无穷的对象使用排中律，从而遭到了不少人的质疑。 排中律，说的就是一件事非真即假，这再明白不过了，为什么还有反对的意见呢？ 比如说这样一个命题：pi中含有任意长度的连续数字9。如果我们接受排中律的话，这个命题非真即假。但无论这个命题是真是假，我们都无法在实际上验证，因为要验证这个命题，我们都要将pi无穷地计算下去，而这是不可能做到的。所以，人们对于将排中律用到这种无穷的情况仍有顾虑，因为这不是他们的直觉能掌握的范围。 我们不知道是否因为这件事，希尔伯特动起了为整个数学寻求一个坚实基础的念头，但我们可以知道，在经过多年在不同数学领域富有成果的涉猎后，希尔伯特将目光投向了整个数学。对平面几何学的严格公理化可能是他在这方面的第一个尝试，但他的思考绝不仅限于几何。他的目标是将整个数学体系严格公理化，然后用元数学——证明数学的数学——来证明整个数学体系是坚实的。 为了这个目标，他制定了著名的希尔伯特计划。 首先，将所有数学形式化，让每一个数学陈述都能用符号表达出来，让每一个数学家都能用定义好的规则来处理这些已经变成符号的陈述。 然后，证明数学是完整的，也就是说所有真的陈述都能被证明，这被称为数学的完备性；证明数学是一致的，也就是说不会推出自相矛盾的陈述，这被称为数学的一致性。 最后，找到一个算法，可以机械化地判定数学陈述的对错，这被称为数学的可判定性。 如果这个计划完成了，那意味着什么？在保证数学的一致性这个前提下，我们又有数学的完备性，也就是说只要是真的都可以证明。这其实就是说，对于任意一个数学猜想，不管它有多难，只要假以时日，通过一代又一代人的努力，总是可以知道这个猜想对不对，并且证明或否定它。 这是个雄心勃勃的计划，但希尔伯特并不认为这是不可能的。他提出，先在基础的数学系统进行这样的形式化，然后再将其推广到更广阔的数学系统中，最后实现整个计划。于是，整个计划便归结于在算术系统中进行这样的形式化，并且在它的内部证明它的完备性、一致性和可判定性。 这似乎不太困难。算术系统并不是一个很复杂的系统，它早在1889年就被皮亚诺归结成一个有5条公理的系统，其中只有最后一条数学归纳法公理比较复杂。我们可以想象，希尔伯特本人也认为这是可以解决的问题。他将算术公理系统的相容性列入了他那23道希尔伯特问题中，位列第二，希望20世纪的数学家能给出一个证明。这份1900年写出的问题表，后来证明是相当具有前瞻性的，即使情况并不一如希尔伯特预计的那样。 1931年，仅仅在他退休一年之后，希尔伯特第二问题即告解决，尽管解决的方式是希尔伯特所没有预料到的。 逻辑弄人。 哥德尔不完备性定理可以说，哥德尔粉碎了希尔伯特计划。 在希尔伯特退休之时，哥德尔才刚刚登上数学舞台。在某种意义上，正是希尔伯特间接将哥德尔引领到数理逻辑这个领域的。在希尔伯特和他的学生阿克曼合著的《数理逻辑原理》中，他们提到了这样一个问题：在形式系统中，真的命题是否都是可证明的？这正是哥德尔博士论文的主题。在这篇论文中，哥德尔证明了一阶谓词演算是完备的，这就是不太著名的哥德尔完备性定理。一阶谓词演算是一种能力比较弱的数学系统，如果只是应用它的话，我们连自然数都定义不了，就更别说做算术了。自然，哥德尔的目光是不会仅仅局限于此的。 在完成博士论文之后，哥德尔便着手探索更一般的数学系统。一年后，也就是1931年，他对算术系统的探索即告胜利。这个胜利，也就是希尔伯特计划的失败。他的结论，就是哥德尔不完备性定理，一共有两个。 第一，他证明了，对于任意的数学系统，如果其中包含了算术系统的话，那么这个系统不可能同时是完备的和一致的。也就是说，要是我们能在一个数学系统中做算术的话，那么要么这个系统是自相矛盾的，要么有那么一些结论，它们是真的，我们却无法证明。 第二，他证明了，对于任意的数学系统，如果其中包含了算术系统的话，那么我们不能在这个系统内部证明它的一致性。这就是希尔伯特第二问题答案的一部分。 哥德尔证明这两个定理的武器，就是希尔伯特在他的计划中使用的武器：形式化。在哥德尔的证明中，他先将所有的数学陈述以及它们的证明用符号形式地表达出来，然后利用哥德尔自己发明的一个重要技巧——哥德尔数化——将所有这些陈述和证明变为一个个的自然数。那么，借助数学归纳公理，我们可以递归地建立针对所有自然数的陈述，而一个这样的陈述同时又是一个自然数，所以它描述了自己。换句话说，这个陈述陈述了它自己。 这种自指的情况，在数学上很有用，也非常凶险。它是不少悖论的源泉。第一个例子当然是说谎者悖论：“这句话是错的”。第二个就是罗素悖论，它引起了第三次数学危机，这也可以说是希尔伯特计划的一个动因。 我们来看看它的一个通俗版本，叫理发师悖论。 在一个小镇内，只有一名理发师，他在理发店门外公布了这样一个原则：只为不会自己理发的人理发。那么，他的头发谁理呢？要是他自己理的话，他就会自己理发了，那么根据他的原则，他不应该为自己理发；要是他不给自己理发的话，根据他的原则，他倒是应该给自己理发。逻辑似乎在这里失效了。 这种逻辑上的混乱局面，背后就是罗素悖论：定义一个集合，它包含所有不包含自身的集合，它是否包含自身？从上面的分析，我们可以看到，一切问题在于“包含自身”这种自指的描述。后来，在策梅洛和弗兰克等逻辑学家的努力下，通过在集合论中添加正则公理等限制，才将这种危险的自指从集合论中排除。当然，这是后话了。 这种自指的性质，尽管危险，但在哥德尔的妙手中，它就变成了证明的利器。他构造了一个命题，这个命题说的正是它自身的不可证明性。如果用类似说谎者悖论的语言来表达的话，就是：“不存在对这个命题的形式证明。”如果它是真的，那么它是不可证明的，说明系统是不完备的，因为存在一个真的而又不可证明的命题。如果它是假的，那么存在一个它的证明，这样它应该是真的，说明系统是自相矛盾的、不一致的。这就是哥德尔的第一个不完备性定理：如果有自然数的话，完备性和一致性不可得兼，这个系统要么自相矛盾，要么存在不能证明也不能否证的命题。 然后，我们来仅仅考虑一致性的问题。假定系统是一致的，也就是说不会自相矛盾的，那么我们刚才提到的命题就是不可证明的。如果我们能在系统内部证明系统的一致性的话，我们就相当于在系统内部证明了那个命题，这与不可证明性是矛盾的。也就是说，我们做了错误的假设：能在系统内部证明系统本身的一致性。由此，哥德尔证明了他的第二个不完备性定理。 他的这两个不完备性定理，对于希尔伯特计划是个沉重的打击：计划的第二步被证明是无法实行的。如果我们假定数学不会自相矛盾的话，我们就必须承认数学是不完备的，也就是说有这么一些数学命题是不可判定的：我们既不能证明它们为真，也不能证明它们为假。但很多数学家仍然认为，这并不威胁数学的正常发展，因为他们觉得有意义的数学命题极不可能是这样的。换句话说，数学家们仍然相当乐观。 同样是哥德尔，这次连同科恩，给这些数学家敲响了警钟：数学家研究的“有意义”的数学命题也可能是不可判定的。他们解决的又是一个希尔伯特问题：由康托尔提出的连续统假设。这个问题位于列表之首，是一个纯粹的集合论问题。哥德尔证明了连续统假设和策梅洛-弗兰克集合论是相容的，也就是说二者之间没有矛盾；科恩证明了从策梅洛-弗兰克集合论出发不能证明连续统假设。这两个结果综合起来，其实就说明了连续统假设在策梅洛-弗兰克集合论中是不可判定的。要是你知道策梅洛-弗兰克集合论正是解决第三次数学危机的武器和现代数学的逻辑基础，你就会明白这到底意味着什么。 哥德尔的魔鬼第一次露出了真面目。希尔伯特第一问题竟然就是不完备性定理中预言的那类不知真假的怪异命题的一个实例，这实在令人泄气。 既然希尔伯特计划的第二步都被证明是不可行的，那么第三步也就没有必要继续下去了。第三步是寻求一个能机械证明所有数学定理的程序，著名的停机定理也否定了这种可能性。停机定理的证明相对比较简单，也是利用自指的技巧，证明这样程序是不可能存在的。 至此，希尔伯特那宏伟的计划宣告全盘失败。 有些事情，我们确实不知道，即使对于数字，这是逻辑说的。 余波令希尔伯特在天国的灵魂有所安慰的是，算术系统的一致性被证明了。这个证明用到了不在算术系统内的超限归纳法，它可以被视为一种加强版的数学归纳法，是用在无穷序数上的。这其实就假定了策梅洛-弗兰克集合论的一致性。当初康托尔建立无穷集合论时，曾遭到不少人的攻击，这时希尔伯特挺身而出，为康托尔和他的无穷集合论疾呼：“没人能将我们从康托尔创造的乐园中赶出来。”如今，康托尔的无穷集合论衍生出来的超限归纳法反过来又部分实现了希尔伯特的梦，这是冥冥之中的安排，还是希尔伯特的敏锐眼光所致？恐怕没人能说得清楚。 但哥德尔的魔鬼仍在肆虐。越来越多的数学问题被证明是不可判定的，这些不可判定的问题也越来越初等。乍看起来并非不可捉摸，但到头来却不可判定。比如说，如果我们用可数种颜色对每一个实数染色，是否必定存在4个互不相等的数a,b,c,d，使得它们的颜色都相同，而又满足a+b=c+d？这看起来怎么也不像没有一个确切结论的问题，但有人证明了它实际上和连续统假设的否定是等价的，也就是说，在策梅洛-弗兰克集合论内，它也是不可判定的。这就给数学家们心头压上了一块大石：谁也不知道自己辛辛苦苦做了十几年的题目，会不会突然有一天被证明是在现有数学体系中不可判定的。 尽管这样，哥德尔的不完备性定理仍然带给我们很多教益。至少我们知道了，有些东西我们不可能知道。在哥德尔的这个划时代的证明之后，数学家对数学的基本工具——证明——有了新的认识。专门研究数学证明的证明论，在他的启发下蓬勃发展。但是，哥德尔教给我们最重要的一点是： 数学，如同人生，如同爱情，有些东西是真的，你却永远无法证明。 28 augustus 所有含有34个顶点的树都是优美的！通过优美树验证项目，我们验证了含有34个顶点的树都是优美的。它们是用经过改进的算法进行验证的。 更多资料请参见： http://fwjmath.spaces.live.com/blog/cns!6A37A2A4F21FF4DE!1307.entry 15 mei 不正当竞争？微软在Live Space后台统计中做的手脚我是很习惯看这个空间的后台统计的，之前也经常有Google.com的搜索结果进来，可以说Google.com是除了rss之外的一个很大的访问量来源。但是在Live Space升级以来，我发现从Google.com来的链接就没有出现过了，倒是多了很多live search来的，而且关键字是"windows"。 我不禁怀疑微软的智力水平。你要搞也把关键字搞得一样啊，现在这样子傻子都知道你对Google.com的链接动了手脚了。当然这是你自家地盘，但是这是不是违反了用户条款呢？ 我反正一向用google，而且这种行为我最不齿了：仅仅为了推广你的live search你就开始造假了，微软？ 九流。 29 april 所有含有32或33个顶点的树都是优美的！通过优美树验证项目，我们验证了含有32或者33个顶点的数都是优美的。它们是用经过改进的算法进行验证的。 更多资料请参见： http://fwjmath.spaces.live.com/blog/cns!6A37A2A4F21FF4DE!1307.entry 20 maart 默比乌斯带：只有一面的魔环小时候手工课，经常有要把纸裁成带然后再粘成环的活要干。这个任务即使对小朋友来说也是很简单的。但有时总会有些马大哈会犯糊涂，在把纸带两端粘成环之前不小心翻了个面，纸环就变得歪歪斜斜的了。
这也不是什么大事，撕了重粘就好了。但是，既然纸环已经变成这样了，何妨把玩一番呢？要知道，这就是鼎鼎有名的默比乌斯带。 很多读者应该都知道默比乌斯带的特别之处：它只有一个面，也只有一条边。在数学上，这样的曲面有一个特别的名字：单侧曲面。怎么证明它只有一个面呢？很简单，我们用红笔在上面沿着它的走向画一条线（不跨越边沿），在笔回到起点的时候，我们会发现红笔已经涂过了纸环的所有面。如图：
这就可以很好说明默比乌斯带只有一个面了。 如果我们在普通的纸环上面做同样的操作的话，当笔回到起点时容易知道还有一面没有涂过，所以普通纸环不是单侧曲面，实际上每个人都知道它有两个侧面。 如果我们沿着这条红线把环剪开，会得到什么呢？
相信很多朋友都知道了，我也就不卖关子了：这个纸环会被剪成一个中间旋转了两个半圈的大纸环：
但是，可能没有多少人留意到，经过一番摆弄，这个纸环可以变成一个两层的“默比乌斯带”。之所以要加引号，是因为这个毕竟也是双侧曲面，而不像真正的默比乌斯带那样是单侧曲面。
要做到同样的效果，我们也可以用两层纸带用类似做默比乌斯带的方法来粘贴，只不过两层纸要分别粘贴而已。 好了，回到那个剪了一次的纸环那里去。如果我们再剪一次，会发生什么事情呢？现在这个纸环已经是不是单侧曲面了，所以剪开以后应该至少出现两个环。问题是，那会是怎么样的两个环呢？
好了，结果出来了，是两个和刚才一样的纸环，不过这两个纸环是套在一起的。 如果我们摆弄一下，能把它们弄成刚才没有开剪之前的大纸环的一个双层版本。
再摆弄一下，又能把它们弄成一个四层的“默比乌斯带”。
可以证明，如果我们这样不停的剪下去，每次剪出来的都是一样的纸环（中间有两圈旋转的），而且都套在一起，还能弄成一个多层的“默比乌斯带”。一个不大严谨的证明应该是不复杂的。（提示：将每次剪出来的都套成多层“默比乌斯带”，然后剪开就成了多层的两个半圈旋转大纸环，又能套成多层的“默比乌斯带”） 那么，这东西有什么用呢？ 首先，这东西既然是数学家做出来的，肯定是有理论上的意义的。事实上，这是数学家发现的第一个单侧曲面。 在积分理论发展的过程中，由于曲面通常有两侧，所以人们要给曲面定个方向才能进行积分。但是，当时还没有人知道是否存在这样的曲面，它只有一侧从而无法在它上面确定一个积分的方向。 而默比乌斯带正是这样的一个单侧曲面，它只有一个侧面从而无法定向。所以这类曲面又有一个名字叫“不可定向曲面”。 由于默比乌斯带只有一个面，这个面的长度自然就是普通纸环一面长度的两倍了。有人想到将这个特性用到传送皮带上，这样的话就可以把磨损分摊到更多的地方，从而提高皮带的寿命。这个想法还获得了美国的专利。 利用默比乌斯带的想法获得的专利还不止这一个。还记得那个两层“默比乌斯带”吗？不记得也没有关系，看下图：
如果我们把纸带想像成金属带，让电流由其中一个夹子流入而从另一个夹子流出的话，在纸带表面的电流有两个可能的流动方向，而这两个方向的电流产生的磁场恰好互相抵消。也就是说，电流在这个装置流动的时候不会产生磁场，所以也不会有电池感应的现象发生。这就是一个无电感电阻。这种电阻就叫默比乌斯电阻。 默比乌斯带在艺术和文化作品中也经常被引用，作为“无限循环”的一个象征。国际通用的循环再造标志就是一个绿色的、摆放成三角形的默比乌斯带。在《哆啦A梦》（小叮当）漫画中，就有一个形状是默比乌斯带的道具，只要把它放在门把手上，里边的人开门就会回到同一个房间里去。如果我们看科学馆门前的环状雕塑，多半也利用了类似默比乌斯带的性质，有空的话经过这些雕塑可以数一下这些环有多少个面多少条边沿，我估计绝大部分结果都是1。而至于埃舍尔的例子就更是众人皆知，也不用我饶舌了。 实验室中也有可能产生默比乌斯带形状的粒子。前不久，一群科学家在Journal of Chemical Physics上发表了一篇论文，其中预言了一种默比乌斯带形状的碳单质（准确来说应该是石墨烯）。它能抵抗摄氏200度左右的温度，算是相当稳定。由于它默比乌斯带的结构，它应该是一个偶极子，从而可以形成稳定的晶体。现在就等科学家们把它实际做出来了。 这一切，都是由数学家看到一个粘错的纸环开始的。
Bonus1： 又是来自xkcd的漫画：（http://xkcd.com/381/）
Bonus2： 想要一个金属做的默比乌斯带的朋友，你们有福了！野驴设计了默比乌斯带形状的松鼠会纪念品！心动的话请移步到http://songshuhui.net/archives/11435.html来订购吧！以下是效果图：
默比乌斯指环，装备后+43敏捷，+46耐力，增加命中等级25点，增加攻击强度86点，再加上松鼠会的松鼠光环，实在是行走在艾泽拉斯大陆和现实世界上的必备佳品啊！ 02 maart 遗传算法：内存中的进化本文遵守首页上的Common Creative 署名-非商业性用途-禁止演绎 2.5 中国大陆。非商业性网站转载请注明作者以及出处，谢谢。 商业性网站转载请与作者本人协商。
这是个真实的故事。 从前在海岸边有一群扇贝在悠哉游哉地生活繁衍着。它们自然是衣食不愁，连房子也有了着落。它们担忧的只有一件事：每隔一段时间，总有一个人来挖走它们之中的一部分。当然啦，挖回去干什么这大家都知道。但扇贝们不知道的是，这人的家族图腾是Firefox的图标，所以他总是选择那些贝壳花纹长得比较不像Firefox图标的扇贝。 这种状况持续了好几十万代。大家应该也猜到扇贝们身上发生什么事情了：它们的贝壳上都印着很像Firefox图标的图案。 可能有些读者会说：你这不是糊弄我们么，Firefox才有多少年历史，你就搞了个几十万代的扇贝？ 确有其事，但是这些扇贝不是真实的，它们在我电脑的内存里边生活。它们是一个遗传算法程序的一部分，这个程序的目的就是用100个半透明三角形把Firefox的图标尽可能像地画出来。 什么是遗传算法呢？ 简单地说，遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化，从而得到问题的一个近似解。 在二十世纪五十年代，生物学家已经知道基因在自然演化过程中的作用了，而他们也希望能在新出现的计算机上模拟这个过程，用以尝试定量研究基因与进化之间的关系。这就是遗传算法的滥觞。后来，有人将其用于解决优化问题，于是就产生了遗传算法。 那么，具体来说，在计算机里边是怎么模拟进化过程的呢？ 我们还是以开头提到的程序为例。 首先，我们知道，生物个体长什么样子很大程度上是由染色体上的基因决定的。同样，如果我们把100个半透明三角形组成的东西看成一个生物个体的话（为了说话方便，称为扇贝吧），我们也可以说它的样子是由这些三角形的具体位置和颜色决定的。所以，我们可以把一个一个的半透明三角形看作是这些扇贝的“基因”。而组成扇贝的这100个基因就组成了每个扇贝个体的“染色体”（chromosome）。 从下面的图可以大约看出来这些基因是怎么决定扇贝的样子的（为了观看方便，我们只画出其中五个三角形）：
然后，扇贝们除了生活，当然还要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体，而在这个程序里边我们当然也这么办：选择两个原有的扇贝，然后从这两个扇贝的染色体中随机选取一共100个基因组成新个体的染色体。如图所示：（仍然是将扇贝看成是五个三角形组成的）
为了产生新的基因，使基因的种类更多样化，在组合的时候，新的扇贝的基因有一定的概率发生变异。也就是说，其中的一个透明三角形的位置或者颜色会随机改变，如图（仍然是五个三角形……我偷工减料……）：
其次，为了使扇贝的样子向Firefox图标靠近，我们要给它们加上一点选择压力，就是文章开头故事中提到的那个人的行动：在每一代把最不像Firefox的扇贝淘汰出去，同时也给新的个体留下生存的空间。怎么评价这个扇贝像不像Firefox呢？最直接的方法就是一个一个像素比较，颜色相差得越多就越不像。这个评价的函数叫做“适应函数”，它负责评价一个个体到底有多适应我们的要求。 在淘汰的过程中，为了便于编程，我们通常会在淘汰旧个体和产生新个体的数目上进行适当的调整，使种群的大小保持不变。淘汰的作用就是使适应我们要求的个体存在的时间更长，从而达到选择的目的。 最后，在自然界中，种群的演化是一个无休止的过程，但程序总要停下来给出一个结果。那么，什么时候终止演化输出结果呢？这就要订立一个终止条件，满足这个条件的话程序就输出当前最好的结果并停止。最简单的终止条件就是，如果种群经过了很多代（这里的“很多”是一个需要设定的参数）之后仍然没有显著改变适应性的变异的话，我们就停止并输出结果。我们就用这个终止条件。 好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码之后，只需要随机产生一个适当大小的种群，然后让它这样一代代的繁衍、变异和淘汰下去，到最后终止我们就会获得一个惊喜的结果：（这回是完整的了，图片下的数字表示这个扇贝是第几代中最好的）
怎么样？虽说细节上很欠缺，但是也算是不错了。要不，你来试试用100个透明三角形画一个更像的？就是这样的看上去很简单的模拟演化过程也能解决一些我们这些有智慧的人类也感到棘手的问题。 实际上，在生活和生产中，很多时候并不需要得到一个完美的答案；而很多问题如果要得到完美的答案的话，需要很大量的计算。所以，因为遗传算法能在相对较短的时间内给出一个足够好能凑合的答案，它从问世伊始就越来越受到大家的重视，对它的研究也是方兴未艾。 其实，通过微调参数和繁衍、变异、淘汰、终止的代码，我们有可能得到更有效的算法。遗传算法只是一个框架，里边具体内容可以根据实际问题进行调整，这也是它能在许多问题上派上用场的一个原因。像这样可以适应很多问题的算法还有模拟退火算法、粒子群算法、蚁群算法、禁忌搜索等等，统称为元启发式算法（Meta-heuristics algorithms）。 另外，基于自然演化过程的算法除了在这里说到的遗传算法以外，还有更广泛的群体遗传算法和遗传编程等，它们能解决很多棘手的问题。这也从一个侧面说明，我们不一定需要一个智能才能得到一个构造精巧的系统。 无论如何，如果我们要将遗传算法的发明归功于一个人的话，我会将它归功于达尔文，进化论的奠基人。如果我们不知道自然演化的过程，我们也不可能在电脑中模拟它，更不用说将它应用于实际了。 向达尔文致敬！
Bonus：如果你看明白了这篇文章，而且你懂英语的话，你自然明白下面这个冷笑话：（来自http://xkcd.com/534/）
Just to make sure you don't have it maximize instead of minimize. 25 februari 一百个三角形进化成Firefox本文遵守首页上的Common Creative 署名-非商业性用途-禁止演绎 2.5 中国大陆。非商业性网站转载请注明作者以及出处，谢谢。 最近写了个遗传算法的程序~~~这是我第一次练习写这个~~~以前想用这个方法很久了但是一直没有碰上合适的问题~~~ 我的程序的作用就是用100个三角形来画某个给定的图片，在测试里边我用了Firefox的图标和我自己的照片。毫无疑问这是受上次那个用多边形画蒙娜丽莎的人启发的，虽然严格来说他的程序不能算是遗传算法。遗传算法需要有一个种群，然后是竞争、杂交、变异。我的程序种群有30个，杂交是交换三角形，变异率是每个参数1/2048（一个个体有100*(3*2+3)=900个参数）。其实遗传算法写起来也不难，就是不容易找到合适的问题。 绘画方法是多种颜色三角形重叠的点求这些颜色与背景颜色的平均值，背景颜色是252 252 252。 下面这个例子经过了大概三十万代的迭代，用时不到一个小时。 不说废话了，上图： 原图：
100个三角形：
组合过程（不是进化过程！！）：
数据是：（格式为x1 y1 x2 y2 x3 y3 r g b） 62 88 39 91 8 24 209 1 1 02 februari 荣幸收到某印度民科来信我前一段时间不是搞了个优美树验证项目么。项目没啥事情，正在稳定进行中，各项工作整整有条。关键是，这网站居然被某印度民科看上了。 印度其实是个好地方，那地方人聪明，跟中国差不多。科技发展水平也跟中国差不多。当然了，民科也跟我们这里差不多。我们这里的民科还算好，他们的偶像陈景润好歹也算是正规学者。印度那边民科的偶像是谁？那是拉马努金！天才！他留下来的东西够数学界整理个好几百年的了，而且很多是在没有指导下独自完成的（当然他也看了不少书，但那是起步）。当时哈代发现了他把他接到英国是为了一起研究，论独创性的话哈代当然是自愧不如。 于是乎，有的印度民科也就不掂量掂量自己有没有拉马努金的天才，就一头扎到无底的数学难题了。哪个领域的都来一手，而且不难的不做。 就算是当年欧拉高斯黎曼也没那么嚣张啊！ 看来人乱搞起来哪个国家都是一样的。 好了，言归正传。给我发邮件的那人，严格来说并不是“大师”本人，我估计是大师的弟子。他给我发来的邮件内容看起来非常狂热，什么“这是优美树疾病的一个疗法吗”等等内容。还附带有该“大师”的许多论文的链接，都是在预印本网站上的，也就是说没有在刊物上发表过。文章内容除了优美树猜想之外还有很多数学和物理上的“重大发现”，可谓是包罗万象，下面简单说说： 最新的一篇是关于量子纠缠的，这篇的摘要我看得云里雾里的，那就算了。 然后是关于哈密尔顿分解，我不懂，也跳过。 接下来是说证明了Caccetta-Haggkvist猜想，这是个图论的东西，我也不大懂，也跳过。 接下来的我也不大懂，跟物理有点关系。 再来就有好戏看了。 接下来的一篇论文关于图论，证明了Hadwigers猜想，这是有关顶点着色的。 接下来一篇也是着色，据说开辟了研究的新方向。 再接下来就是重头戏了。他在Hamiltonian Graphs and the Traveling Salesman Problem这篇东西里边宣称，通过哈密尔顿图，他找到了旅行推销商问题的一个多项式算法！这不就是等于说P=NP么？这论文如果是对的，到哪里都是个菲尔兹奖或者沃尔夫奖啊！ 可惜，看来没有杂志肯接收他的这篇论文，看来是有点问题。 我们再往下看。 接着是一篇关于有限投影平面的，在这篇文章里他又解决了一个问题。 接着是关于雅可比问题的，不懂，跳过。 接着是关于拉姆赛数的，这个我懂一点。他提出了一个“新拉姆赛数”的概念，然后说这两个东西是一样的，然后对于新的那个他找到了更快捷的方法来计算。这要是真的可以做一个新的分布式计算…… 可惜，仍然是没有在杂志上发表，等于0。 然后是关于线性规划的新算法，据说可以推广到非线性和整数规划丢番图方程的情况，可惜没有给出时间复杂度。 我二分法也可以做非线性……最近做的某个ENS卷子就是讲丢番图方程的解系…… 然后是一篇鸿篇巨制，民科的典范：On Problems Related to Primes: Some Ideas。 在这篇文章里他解决了哥德巴赫猜想、孪生素数猜想和谢尔品斯基猜想！一篇论文解决三个猜想，比国内的民科高明多了。 然后有几个图论和数论的文章我就跳过了，反正都是解决某某问题的。 有一篇关于3x+1的文章还算老实，没有证明某某问题。 然后就是证明优美树猜想的文章了。这篇东西他2005年放上网，2008年还修改过，然后comment的单词还拼错了…… 态度看来是不大端正啊，而且这个修改是不是发现了当时的错误？ 然后是解决图重构问题的，这个我也知道一点，不是那么好做的，当然这个做得对不对我还是不大清楚的。 然后是费马大定理的推广，这个倒是没什么。 接着又是孪生素数猜想的证明。 我有天上网，不小心看见了陶哲轩对某证明了ABC猜想的论文作出评价，他说（大意如此），如果一个人经常跨领域啥都干，而且一来就证明很多个猜想，这人如果又没有正规的教研职位，没有受过系统的培训的话，他的文章的正确性就很值得怀疑了。而且在预印本网站上的文章大多没有发表，正确性需要验证。当然，其中有佩雷尔曼这样的高人，但是更多的是乱来的民科。 看来各国民科，大抵如此啊。我只是个学生，随便搞了个项目就被看上了，这些人真是热衷宣传啊。 不过国内的民科同行大可不必紧张，你们的表现也是很好的，这是经过某教授评定的。 这位教授是专门搞奥赛的，有一次在上海某中学授课的时候，突然有一位陌生人闯进来。 “请问某某某教授在吗？” 我不知道下面的学生会怎么反应，如果是我的话肯定忍不住笑。那教授就在你面前，你这样问明摆着就是跟别人不熟嘛，还敢在工作时间找他？ 教授反应很快：“我们没有见过这个人，也不认识他。” 那人就哦了一声，出门走了。这时全班哄堂大笑。 等笑声止住一点之后，教授又开腔了： “以后再有这种民间科学家来找我，你们就说我已经死了。” 能把数学奥赛的一把好手迫成这样子，中国的民间科学家，我佩服你们！ 26 december 谬误与真知：马桶、台风与“地转偏向力”“为什么北半球的马桶冲水时水流是逆时针旋转的？” “因为地转偏向力使水流一边向下流一边向它的右边拐。” 这是一个在日常生活中会偶尔听到的话题，故勿论其对错。那么，到底这个“地转偏向力”是什么呢？ 地转偏向力，是一个更为普遍的“力”之中的一个特例，这个“力”的大名就叫做科里奥利力。它是由法国数学家、工程师科里奥利(Gaspard-GustaveCoriolis)从理论力学中推导出来的，所以也以他的名字命名。为什么我们要在这个“力”字上加引号呢？因为它不是一个真正的力。真正的力除了有受力物体也应该有施力物体，但如果这个科里奥利力有施力物体的话，那这个施力物体也太玄乎了，能让北半球所有水流都向右拐。这其实不是一个真正的力，物理学家们把它称作一种惯性力，也就是说是由物体的惯性产生的力。 那么，在什么情况下才会出现这种力呢？科里奥利说了，在一个转动的参考系中就会出现科里奥利力，只要是在这个参考系中运动的物体都会好像受到一股垂直于运动方向的力，从而偏离开它的轨道。科里奥利他说的“转动的参考系”，其实这个转动就是说这个参考系相对于一个惯性系在转动【注1】，那么这个参考系本身就是一个非惯性系了。科里奥利力就是这个非惯性系里边的一个惯性力。 不过科里奥利力也不是对所有物体都一视同仁的。对于相对参考系不动的物体，它不会作任何打扰，它专爱找运动物体的麻烦。它的公式是：Fic=-2ω×mv。在这里，m是物体的质量，ω是指示参考系旋转速度和方向的向量（就是方向和数量的一个组合），而v则是物体在这个参考系中运动的速度向量。这个乘号也有讲究，它不是一般2×3的那种乘法，而是一种特别为向量设计的乘法，通常叫做叉乘。而Fic就是这个物体在这个参考系中受到的科里奥利力。 现在我们可以解释为什么北半球的水流总有向右偏的倾向了。我们向来认为地球是不动的，就算是物理学家做实验，在很多情况下都选取大地作为参考系。但是我们现在知道地球其实是在一刻不停地自转的，虽然转得不快，24小时才转一周，我们也没怎么觉得会被地球转得甩出去，但它的确在转动。所以地球其实是一个转动的非惯性系，任何运动的物体在地球这个参考系中都会受到惯性力——特别是科里奥利力——的作用。地球的ω的方向是从南极指向北极的，于是在北半球的话这个向量是从地下指向天空的，于是一切平行地面运动的物体受到一个向它们运动方向右边的科里奥利力的作用，于是就向右偏转了。同样的道理，在南半球这个向量是从天空指向地下的，于是乎一切东西都反转了过来，平行地面运动的物体这回受到的科里奥利力的作用就是向左边的了。 那么，马桶冲水逆时针流的原因看来就是科里奥利力了？ 那倒未必。 我小的时候看科普书，也对文章开头的说法深信不疑。直到有一天雨后，我看到楼下的沙井盖上面两个排水孔中水流的旋转方向是一个顺时针一个逆时针之后，我就不再相信这种说法了。要是真的是科里奥利力导致的排水孔水流打转的话，应该两个方向相同才对，怎么会一个顺时针一个逆时针呢？ 但这只不过是一个例子，还不能说明所有排水孔水流旋转方向都不是由科里奥利力引起的。但是我们只要稍微估算一下就会知道水流漩涡产生的原因是不是科里奥利力了。假设水流跑得跟刘翔差不多快，也就是10米每秒的样子，而且速度完全平行于地面，这时候水流受到的科里奥利力最大。即使这样，水流受到的由于科里奥利力产生的加速度也只不过是0.001米每平方秒。如果马桶的直径有1米，而水是从马桶边径直冲向中心的话，到达中心的时候由于科里奥利力产生的偏转还不到半毫米，根本就产生不出什么看得见摸得着的效应，更何况是我们平时看见的漩涡了。如果连在这个巨型马桶中的高速水流都产生不出看得见的效应的话，就更别说那些可怜的小马桶和排水口了，没戏的。 实际上，排水口和马桶们产生漩涡的原因多半是由于它们自身的构造问题。有的马桶就是特地设计漩涡式冲水的，这样的话无论你把它挪到地球上什么地方它都只能产生同一个方向的漩涡。而对于一般的排水口，由于结构，有时候它们会偏好形成某个方向的漩涡，而更多的时候是两种旋转方向的漩涡都会出现，不信你试试就知道了。 那科里奥利力是干什么吃的？这么微弱的影响它能干点什么？ 由于地球转动产生的科里奥利力是非常微弱了，这并不是它的过错，主要是因为地球转得实在太慢了，24小时才转一圈，要是参考系转得快一点的话它的影响也还是不可小觑的。我听说在一些大型主题公园之中有这么一种游戏设施，它是一个很大的转筒，里边可以站很多人。当人们站好在里边之后，转筒就开始转动。根据我们的日常经验，人们在里边会受到“离心力”的作用，然后就都贴到筒上了。正在这个时候，当转筒达到一定的速度，人们都“情不自禁”贴到筒壁上的时候，地板就会突然挪开，只剩下一帮“贴墙的”在干瞪眼。这时如果你在里边，你拿出一个小球让它做自由落体运动的话，你不仅会发现小球受到“离心力”的作用而向你的方向偏转，还会发现它很快地从你面前飘开，这就是科里奥利力的作用了。我估计在一些别的以旋转为卖点的游艺设施（比如说咖啡杯）里边也同样能观察到这种效应，可能没那么明显罢了。我们能在这些游艺设施中观察到科里奥利力的明显效应，就是因为它们的旋转速度比地球快多了。 不过，虽然因为地球旋转得慢，引起的科里奥利力不太大，但是我们也还能看到某些它的效应。 要看到一个微弱的东西产生的效应，最好的办法在大尺度和长时间的过程里边观察它。 古语有云，“水滴石穿”，只要时间够长，没有什么效应是观察不到的。比如说河流，一刻不停流淌了千百年的河流，在科里奥利力的作用下河水总是倾向于向右偏，于是河流的右岸总是被冲刷的，而左岸由于没那么多河水冲向它，流速较慢，所以经常有沙石堆积。再比如说铁路，每天都有成百上千吨重量的火车在上面沿着同一个方向以一百来公里一小时的速度飞驰着，这样日积月累也会产生磨损。而人们发现在北半球，右轨磨损得总是比左轨要厉害那么一点点，原因就是火车在行走的时候会受到向右的科里奥利力的作用，这样的话右轨要承担的压力就比左轨要大那么一点，于是磨损当然也就更厉害了。 如果在大尺度上观察的话，科里奥利力也会现出原形。我在沿海地区长大，一年少说也会经历好几次台风。如果我们从卫星云图上面看的话，所有在北半球的台风都是逆时针旋转的，这就是科里奥利力玩的把戏。在地面附近，台风中心处的气压会特别低，所以风是向台风中心吹的。而当这么多空气跑到台风的中心之后，它们也没地方去，所以就一直沿着风眼的壁旋转着向上爬，然后就到达顶端了【注2】。在顶端它们也还是没有地方好去，之后向外吹了。这时候，科里奥利力就过来干涉了，使气流的方向逐渐向右偏移，于是我们就能在卫星云图上看到这个被自己向外吹成了顺时针的台风了（这是2007年第8号台风圣帕）：
以上我们说的都是自然现象，那么有没有人造的能显示科里奥利力效应的仪器呢？ 其实是有的，而且我觉得应该很多人都听说过这个东西。它叫傅科摆。 是听说过，但是这个东西不是用来说明地球是在转动的么？ 的确，当初法国物理学家傅科(JeanFocault)在巴黎先贤祠放这个摆，目的的确是要展示地球在转动。在巴黎先贤祠的这个傅科摆，摆长67米，重28千克。之所以傅科选择这么长这么重的摆是有原因的。摆长越长，摆的速度就越大，这样的话傅科想要的效应会更加明显。摆在开始摆动之后就不能再被干扰，所以为了使空气阻力对于摆的影响尽量小，傅科选择了一个相对大的质量。为了显示摆的轨迹，傅科还特地在摆下摆了一个沙盘。如果地球是静止的话，他的摆应该只会在沙盘上画出一条唯一的轨迹，并且沿着这条轨迹不停的往复运动，直到摩擦力使它失去所有能量为止。 正式演示的那天到了。在巴黎名流的众目睽睽之下，傅科的摆在沙盘上画出的轨迹竟然非常缓慢地向右偏转了起来。自然以一种简单得出人意料的方式证明了我们一直认为静止的大地实际上是在永无休止地自转着。傅科摆向人们展示了地球的自转。 那么，是什么力量使摆的轨迹偏转的呢？你没有猜错，正是科里奥利力。在摆的每一次摆动中，科里奥利力都使摆偏转了那么一点点。但是如果长时间观看的话，每个小时摆的轨迹都会向右转过11度，大概32.7小时摆才会转过一圈，这个周期会随着摆所在地的纬度变化。正是这样缓慢而又坚定的偏移使人们能亲眼看到地球转动引起的效应，而这一切都源于科里奥利发现的科里奥利力。 现在这个摆还在巴黎先贤祠里边摆着，当然加上了不少的装置，使摆可以一直摆下去。直到现在这个摆还在以大约32.7小时转完一周的速度缓慢地而坚定地摆动着，就像人们追寻真理的步伐一样。 1.在力学里边，为了研究运动，我们肯定要首先假定有些东西是不动的。这些我们假定为不动的东西，再加上一个钟，就是一个参考系。比如说坐火车的时候，地上的人认为大地是不动的，他们的参考系就是大地，那么火车里边的人当然就是以每小时几十公里的速度在不停飞驰着。但是对于火车上的人来说，他们看车上的座位啊桌子啊都不像是正在高速运动的样子，所以他们肯定是会认为这个火车是不动的，他们的参考系就是火车。这样的话，在他们眼中看来，他们自己是没动的，反而是地上的人毫无凭据就以每小时几十公里的速度在运动呢。 那么，在这些参考系中有没有一些是比较特殊的呢？有的。如果我们还是以火车做例子的话，当火车匀速运动的时候我们当然感觉不到什么，但如果火车一刹车的话，大家都会纷纷像被一双无形的手推着向前倒去。如果一个参考系经常有这种无缘无故的“力”的话那就真是太麻烦了，于是我们定义一堆特殊的参考系，它们之间相互静止或者相互做匀速直线运动，而且在它们之内的物体永远不会受到一些没有施力物体的力，我们把它们叫做惯性系，因为在惯性系里边的物体，要么就是不动，要么就是不停地做匀速直线运动，“不碰南墙不回头”。而一切不是惯性系的参考系我们都叫做非惯性系，这是一个很没有想像力的名字。在非惯性系中物体有时会受到一些莫名其妙不知道从哪里来的力，这些力被称为惯性力，因为它们其实就是物体本身内在的惯性的一种体现。 2.虽然在这个情况下，科里奥利力是使风向右偏的，但是由具体的计算我们可以知道，这时候产生的漩涡仍然是向内逆时针，也就是向外顺时针的。
07 december [翻译]粒子物理学：打破标准模型的竞赛
导言：在基础物理学中有一个非常成功的理论，它叫“标准模型”，但科学家却觉得它的成功令人沮丧，而且还要想方设法击败它，创造一个超越它的基础物理学理论。大型强子对撞机就是最近的尝试之一，但它并非击败标准模型的不二法门。Geoff Brumfiel 对每个尝试在对撞机全速运行之前摘取大奖的竞争者进行了一番调查，让我们跟去看看吧！
它威力强大，它令人生厌，它注定灭亡，这就是物理学家眼中的“标准模型”。它是一台由方程组成的数学机器，描述了所有已知的物质结构，从原子到星系无一漏网。它描述了自然中四种基本相互作用之中的三种：强相互作用、弱相互作用和电磁相互作用。它以前所未有的精确度预测了一个又一个实验的结果。尽管威力如此巨大，它还远未完善。它的数学结构非常随意，其中还穿插了很多不严格的常数，但最困扰科学家们的是它一次又一次地击败了向它引入最后一种基本相互作用——引力——的所有尝试。 所以，自从二十世纪七十年代标准模型建立之后，物理学家们就一直在尝试超越它。实际上，他们必须用与它那些近乎完美的方程预言的结果相反的实验数据来推翻它，然后再从废墟上重新建造一个更新更好的理论。坐落在瑞士日内瓦附近的欧洲核子研究中心（CERN）内的大型强子对撞机（Large Hadron Collider，LHC）正是推翻这个模型的最新尝试，也是许多人认为最可能成功的。它供应的巨大能量将会使粒子加速到标准模型力所不达的领域。在打破僵局的竞赛中，“到目前为止，LHC 是最受欢迎的”，Frank Wilcezk 说。他是麻省理工学院的理论物理学家，是 2004 年诺贝尔物理学奖的得主之一，他和其他两位得奖者的获奖工作就是标准模型的理论基础之一——描述强相互作用力的量子色动力学。 但 LHC 并不是这场游戏的唯一玩家。几十年来，物理学家一直在通过各种途径寻求超越标准模型的方法：有的寄希望于粒子加速器；有的寄希望于对罕见事件的精细测量；有的还寄希望于太空观察得到的结果。在 LHC 全速运转之前——它的第一份实验结果至少要到明年夏天才能出来（请参看“势不可挡的对撞机”一节）——其中一些研究团队认为他们还可以为胜利放手一搏。他们的任务相当艰巨：标准模型可是相当难以对付的，它已经成功抵挡住了所有简单明显的攻击。要想打败它，科学家们需要前所未有的精确实验，大量的实验数据，还要加上不少的运气。下面我们来看一下这些跃跃欲试的物理英雄吧！ Tevatron 在 LHC 全速运转之前，世界上另一个重量级的粒子加速器已经在全力奔跑，争取打破标准模型了。自 2001 年以来，坐落在美国伊利诺斯州费米实验室的 Tevatron 就不停将质子和反质子加速到万亿电子伏特的对撞能级了。
这只是 LHC 最高对撞能量的七分之一，但在探求新物理的过程中，对撞能量并不代表一切。能创造出标准模型以外的粒子的碰撞事件非常罕见，所以加速器运行时间越长，积累的数据越丰富，它就越有机会作出新的发现。因此，至少在将来的一段时间里，Tevatron 还能继续在数据积累方面领先于 LHC。即使是在 2009 年夏天，Tevatron 在数据上也还会超过它的新竞争者好几倍。 而现有的这些数据似乎提示我们，一些超出标准模型的东西已经出现了。这种提示虽然诱人，但仍不确切。与标准模型不符的结果之一就是对奇异 B 介子（Bs）的测量。奇异 B 介子是由一个奇异夸克和一个反底夸克组成的，在介子的世界中算是非常重量级的了。根据电荷-宇称对称性，标准模型预言奇异 B 介子和它的反粒子（由一个反奇异夸克和一个底夸克组成）的衰变路径相同。但测量结果提示我们，它们俩的衰变路径有些差异。据 Tevatron D-Zero 实验的发言人 Dmitri Denisov 所言，这种差异在将来的探索中可能会成为一条重要的线索，可能意味着存在未知的粒子或者法则。无论如何，“这是一项激动人心的测量实验”，Denisov 说。 而据 Tevatron 的另一个主要实验——对撞探测器（CDF）——的发言人 Robert Roser 补充，其实奇异 B 介子反常并不是加速器中出现的唯一奇怪现象。顶夸克-反顶夸克对衰变的过程中出现的一些特征也迷住了他，但他也承认这个结果远未被确认。然而，以后我们可能会发现这些反常信号的重要性，Roser 说，“如果你不断积累数据，（这些可能的反常情况）其中之一可能会变成事实。” 但 CERN 的一位理论物理学家 John Ellis 对此持怀疑态度。据 Ellis 所言，不错，Tevatron 也许能给出一些诱人的提示，但在 LHC 重装上阵之前它看起来不会作出什么决定性的发现。他指出，在粒子物理学的世界中，在测量精确度达到 5σ（5个标准误差，相当于 99.99994267% 的精确度）之前，任何结果都不能被称为“发现”。要达到这样的测量精度，我们需要的数据远比 Tevatron 目前累积的要多，这个目标在它的新对手超过它之前恐怕难以达到。“我认为这对于 Tevatron 来说是非常非常困难的，”Ellis 说，“我认为他们不可能在 LHC 开始扫荡之前到达目标。” 宇宙 当高能物理学家们集中在他们的机器的控制室里时，另一群物理学家正在仰望星际。他们希望在那里能找到打败标准模型的武器——如果宇宙肯配合的话。
暗物质候选者之一来自所谓的“超对称”理论，这个理论预言标准模型中的每种粒子在标准模型外都有一个较重的“超对称伙伴”。在这些超对称伙伴粒子中最轻的是中性伴随子（neutralino），而超对称理论预言它的性质正好与暗物质相同。 我们不能通过天文望远镜或者轨道卫星等方式直接看到中性伴随子本身，但偶尔会有两个中性伴随子会相互碰撞然后湮灭，这时它们会产生一簇普通粒子，而轨道探测器正好可以探测这种粒子簇。PAMELA（Payload for Antimatter Matter Exploration and Light-nuclei Astrophysics，物质反物质探索与轻核天体物理研究有效载荷）项目已经发现了一条有趣的线索。装载在卫星上的仪器已经非正式地报告了正电子的过剩，这些正电子可能是暗物质湮灭时被制造出来的（参见 Nature 454, 808; 2008）。“这是个漂亮的结果，”看过 PAMELA 数据的 Graciela Gelmini 说，她是加州大学洛杉矶分校的物理学家。但她补充强调，由于测量的复杂性，我们必须多留个心眼。 而最近发射的另一个卫星或许也能探测到中性伴随子匆匆湮灭时发出的一些信号。价值 6.9 亿美元的费米γ射线空间望远镜（Fermi Gamma-ray Space Telescope，原名 GLAST）是一个用于全天探测超高能光子的太空设备，而这些超高能的γ射线有可能是由中性伴随子湮灭产生的，在这种情况下我们会在这个轨道探测器的天图上看到一片无处不在的云雾。“这将会是一个非常、非常惊人的特征信号，”项目科学家 Steven Ritz 说，他在马里兰州 Greenbelt 隶属于 NASA 的 Goddard 空间飞行中心工作。 据伊利诺依州芝加哥大学的宇宙学家 Michael Turner 说，如果这样的特征信号能及时被识别和确认的话，它就有机会在打破标准模型的竞赛中打败 LHC。但他也指出，尽管天体物理学在学术上可能会是第一个作出如此发现的领域，但它能做的也就只能是这些了。正电子、γ射线和其它的特征信号只能粗略地给出新粒子质量的可能范围，但对于超对称理论却什么贡献都做不了。正因为这样，“很多问题将会仍然存疑”，Ritz 说，而这些问题要等 LHC 来解决。
势不可挡的对撞机 就像《自然》杂志之前强调的那样，在日内瓦附近位于欧洲核子研究中心（CERN）的大型强子对撞机（Large Hadron Collider，LHC）将要开始运转了。但在这台机器产出可以正式发表的科学发现之前，科学家们还有很多工作要做。在接下来的几个月，在操作员微调对撞机主体时，其他科学家也要让分布在粒子加速环旁边的实验仪器正常运行。 要启动一个如同高楼般大小的探测器绝非易事。每一台设备都是由成千上万个小探测器构成的，而为了追踪质子对撞时产生的粒子，所有这些探测器都要完美地同步运作。据 ATLAS（A Toroidal LHC ApparatuS，回型 LHC 实验装置）实验的发言人 Peter Jenni 介绍，现在他们正在利用宇宙射线来同步这些探测器。然而，追踪真正的粒子对撞过程需要的远不止这些。对撞的质子束每秒会产生数以亿计的“事件”，每个事件各自包含着数百甚至上千个从对撞点飞出的粒子“碎片”。由于这些小探测器是为了追踪每一个粒子而设计的，它们产生的数据量将会远远超过实验物理学家的处理能力。幸好绝大多数的碰撞都不会有什么特别的粒子产生，所以实验者们给探测器安装了一些电子触发器，用以将那些有意义的碰撞事件分离出来。例如，一个简单的触发器会将产生了μ子的碰撞事件标记起来，因为μ子通常是由比较重的粒子衰变而来的。据 Jenni 所说，每种有趣的事件都会有一个为之设计的触发器来保存数据，而每个触发器都需要进行仔细的调整。 在对数据进行过滤后，科学家们还要对剩下的数据进行分析。此时，实验设备产出的数据会通过一个巨大的计算网格传送到数以千计的物理学家那里，这个计算网格连接了遍布全球的大学实验室，数据的每日处理容量达到 PB 级（1PB=1024TB，现今的个人电脑硬盘大小普遍是 0.1TB 左右）。据 CERN 的 CMS 实验（Compact Muon Solenoid，紧凑型μ子螺旋型磁谱仪）发言人 Jim Virdee 所说，这个计算网格的试运行情况良好，而 ATLAS 和 CMS 的团队正在使用计算机生成的示例数据练习如何对数据进行处理。 Jenni 和 Virdee 都说，如果一切顺利的话，最早在 2009 年夏天就会看到 LHC 的第一批结果。在那时，对撞机应该已经在它的最高对撞能量 7Tev（万亿电子伏特）上运行了几个月，在这段时间内一切技术问题都会被解决。 LHC 会在它的第一次运行中就发现物理学上的新东西吗？有可能。这台对撞机的最高对撞能量是 Tevatron 的大约 7 倍，而后者是现今对撞能量最高的粒子加速器。这是一个飞跃，所以原则上来讲我们几乎能在正式运行时立刻看到新的粒子，Virdee 说，“你不需要多少数据就能超越费米实验室探索的前沿。” 费米实验室的物理学家们对这种看法持怀疑态度，这也是人之常情。据费米实验室对撞探测器的发言人 Robert Roser 所说，在 Tevatron 工作的物理学家用了两年时间才完整领会到他们实验的特性。而据费米实验室 D-Zero 实验的发言人 Dmitri Denisov 所言，即使拥有更高的对撞能量，LHC 仍需要进行数量相当大的碰撞才能找到一些新东西。“在一个探测器中仅仅让两个质子对撞是不够的，”他说。 黑暗 别的物理学家选择了黑暗而非光明。在那些废弃矿井和交通隧道中，他们照看着他们洞穴里的高灵敏度探测器，这些探测器也许可以找到直接指向暗物质的证据，当中包括超对称理论中的中性伴随子（参看 Nature 448, 240; 2007）。
尽管这不是打败 LHC 的方法中最刺激的，但这些探测器取得的进展令人印象深刻。其中一个实验项目是 CDMS II（Cryogenic Dark Matter Search II，低温暗物质搜索二代），它位于美国明尼苏达州的苏丹矿井下，正在不停收集着数据。它的运行者打算在年底前将它的灵敏度提升三倍。另一个位于意大利大萨索山一条隧道中，名为 XENON100 的实验项目同样也有机会比 LHC 更快得到初步的结果。“这个领域成长得很快，竞争也很激烈，所以现在要在这里立稳脚跟不是件容易的事，”XENON100 的项目科学家 Elena Aprile 说，她在纽约哥伦比亚大学工作，“这是个美妙的时代。” 而处于所有这些期待的顶端的是一个研究团队声称他们已经在他们的探测器中看到了暗物质。在今年早些时候，同样位于大萨索山国家实验室的实验项目 DAMA/LIBRA（Dark Matter Large Sodium Iodide Bulk for Rare Processes，碘化钠晶体暗物质搜索）的研究者宣告他们在项目的新一代探测器中看到了暗物质的信号（Nature 452, 918; 2008）。但据实验仪器与其处于同一穹顶下的 Aprile 说，其他团队都被他们的发现难住了，现在还没有人能够确认这个信号，实际上，他们的结果似乎与其他团队的相互矛盾。“我们的结果远非一致，”她说。 尽管这些探测器正在跳跃式发展，它们也有死穴：它们探测的前提是暗物质与普通物质有相互作用，尽管这种相互作用可能极其罕见。据 Ellis 说，这个前提不一定成立。对于他来说，这些实验就像“在黑暗中射击”。 但 Ellis 也承认，这些黑暗中的搜索也有可能比 LHC 更早发现些新东西。“我觉得这帮找暗物质的人就像扑克牌里边的大王一样难以捉摸，”他说。 中微子 对于那些想要在竞赛中打败 LHC 的科学家来说，接下来的几个月在咖啡因的催化下可能只会在他们记忆中留下努力工作的模糊印象。但研究中微子的物理学家们可能会好受些，因为他们早在十年前就在这个领域开辟了新的天地。
但很不走运的是，据 Ellis 所言，标准模型只要对它的方程稍作修改就可以容忍中微子拥有质量了。“我们比较容易就能加点什么东西进去（标准模型），”他说。这样的话，尽管中微子研究者按理说已经撼动了标准模型，但他们的发现对正在探求新物理模型的理论物理学家们并无助益。 但中微子的故事并没有就此完结。来自美国、欧洲和日本的几个实验团队都在向他们的探测器发射中微子束，试图搞清楚中微子是如何振荡的。据哈佛大学的理论物理学家 Lisa Randall 所说，中微子振荡的精确细节可以帮助他们检验新理论模型的可行性。 另外，还有两个新的探测器能在这条道路上走得更远。一个来自欧洲的合作项目在靠近法国土伦的地中海海底布置了一个名为 ANTARES （Astronomy with a Neutrino Telescope and Abyss Environmental Research，中微子望远镜天文学与深空环境研究，缩写意为“心宿二”）的中微子探测器，而来自美国的另一个团队正在南极洲的冰川下安装一个名为 IceCube 的探测器。这两个探测器的设计思想是相同的：通过一串串的小型探测器来捕捉高能中微子冲击水或者冰的痕迹。ANTARES 在今年夏天早些时候就已经安装完毕，而 IceCube 的 70 串探测器才安装了大概一半。但据 IceCube 的首席科学家，工作在威斯康星大学的 Francis Halzen 说，现在 IceCube 的灵敏度已经是超级神冈探测器的五倍了。“我们能作出新发现并不是不可思议的，”他说。 但是我们还不知道他们可能发现些什么，有可能是被困在太阳核心的暗物质粒子产生的中微子。但 Halzen 补充说，探测中微子实验发现的东西都需要 LHC 进一步跟进。“我认为这些（中微子探测项目）只是补充性的实验，”他说，“但如果有机会的话，我倒是更希望是第一个看到新东西的人。”
成功在望？ 这样的话，这些项目能否击溃标准模型呢？Wilczek 对此持怀疑态度。“我还没有激动得坐不住，”他说，如果我们看看以往的记录的话，似乎“标准模型每次都坚持住了”。他相信只有 LHC 才真正拥有打破现有格局的机会。 但是我们也不能保证这个巨型对撞机一定能做出新的发现。“我们可能在 2009 年年中就观察到超对称现象，但它也可能永远不会出现，”Ellis 说，如果真的永远看不到超对称现象的话，物理学家们面对的会是“想象中最恐怖的场景”。“（这样的话）我们接下来能干什么呢？”他问道。 但 Turner 的看法恰恰相反。这些实验和 LHC 终究是在并肩作战。他确信只要将他们的实验数据与 LHC 的结合起来，物理学家们就能击败标准模型，也会给物理学开创一个新天地。“我们站在一个重要物理学革新的边沿。”他说。 Geoff Brumfiel 是《自然》杂志在伦敦的高级记者。 关于 LHC 启动的更多资料，请参见《自然》杂志特别新闻，地址是 http://tinyurl.com/5usrfl。 译注：关于 LHC 探测器的资料，请参看 http://boinc.equn.com/lhc。这个网站内容有保证，因为有一部分也是我翻译的，呵呵。 再译注：LHC 前一阵时间发生了一点小故障，不过还是可以保持在 2009 年初开始全速运行，这样上面提到的这些计划就多了几个月的时间来打败 LHC 了。让我们来看好戏吧！ also: http://songshuhui.net/archives/5507.html 05 december 最“经济”的直尺[修改稿1]注：本文遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！ 直尺可谓是人人必备的文具，是抄笔记划重点的必备武器，平时要量度个什么距离也需要它出马。要是我说刻度是直尺的灵魂，恐怕没有多少人会反对。没有刻度的直尺好比没有字的书，形体还在，但是毫无用处。 我们平时用的直尺大概有刻度的范围有15厘米，每厘米有一个大刻度，每毫米有一个小刻度，用起来的确相当方便。但是在数学家（更确切地来说是组合学家）眼中看来，这种等间距标记刻度的方法未免太浪费，如果允许刻度不均匀分布的话，用同样数目的刻度能量度的不同距离会多得多。当然，直尺是肯定有零点的，所以我们要求最左边的刻度标记为0。 下面我们来看一个简单的例子。 考虑一把只有4个刻度的直尺。如果这4个刻度是等间距分布，相邻两个刻度之间间隔1厘米的话，我们只能量度从1厘米到3厘米一共3种距离。但如果我们将刻度刻在0, 1, 4, 6厘米处的话（如下图），数一数就能知道这样刻度的直尺能够量度从1厘米到6厘米一共6种距离，功能比刻度等间距分布的直尺要大上一倍。 所以说，要想挖掘直尺量度距离的能力，我们就需要合适的刻度方案，而不是以往的那种“平均主义”式的等间距刻度方案，因为这种方案的效率太低了。我们的目标就是在刻度数目一定的情况下使直尺能量度的距离尽量的多，最好每对刻度能量出来的距离都不同，这样就是最理想的情况了。我们把这个条件叫做直尺的“最经济”条件，因为在这种情况下直尺能够量出种类最多的距离，这样的话买这把直尺的人就会觉得物超所值了。 但是，满足这样的条件的刻度方案是否存在呢？回答是肯定的。如果我们要设计一个符合条件的包含4个刻度的直尺，除了刚才上面的做法之外，我们还可以把刻度分别刻在0, 9, 99, 999厘米处，这样的话也可以保证每对刻度能量出来的距离都不同。对于更多的刻度也可以照葫芦画瓢。这样的话，我们就可以确保“最经济”的刻度方案是存在的了。 虽说依照上面提到的刻度方案满足“最经济”的条件，看起来很不错，但是想象一下，一个人在街上带着一把长10米但是上面只有4个刻度的尺子，这个景象是多么的滑稽。于是，新的问题出现了：对于某个确定的刻度数量，有没有办法找到这样一个“最经济”的刻度方案，使得它对应的直尺长度在所有“最经济”的刻度方案中是最小的呢？ 第一个考虑这种尺子的是美国数学家Solomon W. Golomb，这是个颇为严肃的，没啥花边新闻的组合学家。而这种尺子很自然也以他的名字命名，叫做Golomb尺，毕竟是他第一个提出这个问题的。一个刻度方案只需要满足“最经济”的条件就可以被称为Golomb尺，也可以叫优化尺。如果这个刻度方案同时满足最小化条件的话，它就被称为最优Golomb尺，也可以叫最简优化尺。 再加上这个条件之后，问题的答案就远非显然了。之前我们只需要随便找出一个可行的方案就可以了，现在我们需要检查每一个优化尺。二者的难度显然不在一个层次上。那么，聪明而固执的数学家们有没有什么好方法呢？ 遗憾的是，没有。为了验证一个刻度方案是否最简优化尺，我们仍然需要对每一个可能的方案进行验证。由于可能的方案数目非常多，所以这种验证能力有限。为了验证含有25个刻度的最简优化尺，我们需要让7500个英特尔酷睿处理器连续不间断运行3000天！可见这个计算量是多么的大。 虽然要确认一个优化尺方案是否最简是很困难的，但要给出一个很接近最简方案的优化尺还是可以做到的。实际上，数学家们早就对一种与优化尺相似的数学对象相当熟悉了，这东西有一个很唬人的名字：循环差集。虽然名字听起来比较吓人，但它其实并不难理解，它其实就是优化尺的环形版。因为数学家对它比较熟悉，如果能把循环差集转化为优化尺的话，对于优化尺的研究是很有帮助的。 我们可以用念珠当作循环差集的一个模型。普通的念珠都是只有同一种颜色的，比方说是黄色吧。如果我们挑选其中的一些珠子，把它们染成另外一种颜色，比如说蓝色吧。然后我们考察蓝色念珠之间的距离，在这里我们定义两颗念珠之间的距离为它们之间相隔的其它念珠个数最小值再加1。如果每两颗蓝色念珠的距离都不同的话，我们就把这种染色方案称为一个循环差集。
你是否感到上面的描述似曾相识呢？“如果每两颗蓝色念珠的距离都不同的话”，这跟优化尺的“最经济”条件“每对刻度能量出来的距离都不同”几乎就是一模一样。如果我们把蓝色念珠看作整串念珠中的“刻度”的话，优化尺跟循环差集的定义是一模一样的。它们的差别在于，优化尺是定义在笔直的直尺上的，而循环差集是定义在环形的念珠上的。那么，如果我们能把念珠变成直的，循环差集会不会转化成优化尺呢？ 我们来试一下。由于我们关注的对象只是蓝色的念珠，所以如果剪开的两头有黄色的念珠的话，我们大可以将它们去掉。下图是对上图的念珠随便剪了一刀之后得到的情景：
观察一下蓝色珠子的位置，这是不是相当于一个优化尺？只不过它量度的单位是珠子的直径而已。所以说，通过循环差集我们真的可以获得优化尺的方案。 可以证明，无论我们怎么剪，得到的一串东西之中，蓝色珠子的位置方案都相当于一个优化尺，这样的话我们就完成了刚才的任务了。 不过话又说回来，这还是不够的。既然随便剪都可以的话，有没有办法剪得巧妙一点，使最后得到的优化尺尽量短呢？回想一下，既然在剪断念珠之后我们要扔掉两头那些没用的黄色珠子，而一串念珠的个数又是有限的，那么我们扔掉越多，剩下的珠子不就越少，优化尺不就越短了？要想扔掉尽量多的黄色念珠，我们在两颗相邻的但是距离最远的蓝色珠子之间剪一刀不就行了！ 这样的话，我们把念珠重新接好再剪一次，对比一下：
看来这是个好办法。如果我们对于正整数n能够找到含有n个蓝色珠子的循环差集，而使这个集合里边包含的念珠尽量少的话，剪一刀我们不就可以得到相当接近最简优化尺的一个优化尺方案了么？这看起来的确不错，然而有一个问题我们还没有想到。如果寻找符合条件的循环差集比寻找最简优化尺还要困难的话，我们这么麻烦绕这么大一个圈不是浪费生命么？ 幸好，由于循环差集比优化尺的性质好得多，寻找循环差集比寻找最简优化尺要容易得多。事实上，数学家们已经有一种方法可以直接生成那些可能是最符合条件的循环差集。这种方法一时半会是说不清的，大概就是将循环差集和一个所谓的“有限半线性空间”联系起来，这个“空间”里边有一些“点”和“直线”，分别代表了念珠编号和循环差集的一种读法，它们满足一些限定这个空间性质的公理，而通过这个“空间”数学家们就能找出最符合条件的那些循环差集。有趣的是，虽然名为“空间”，这东西和我们平时的观念可是大不相同，比如说“直线”上面只有有限个“点”等等。这代表了数学可以达到的一种抽象的高度，它颠覆了人们对“空间”的概念。 那么，这种方法的威力有多大呢？早在1984年，数学家Atkinson和Hassenklover就已经用这种方法给出了直到100个刻度的优化尺方案，而之后的验证证明，即使这些优化尺方案不是最简的也相当接近，比如说这次，人们验证得出的含有25个刻度的最简优化尺就是当年他们给出的那个： 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480 但很可惜的是，虽然这些优化尺方案非常接近最简的方案，但现在数学家们仍然没能证明用循环差集给出的优化尺方案就是最简的，所以数学家仍然需要用大规模计算的方式来验证一个最简优化尺方案。不过，因为已经知道一个非常接近答案的方案，所以搜索起来相对来说也容易多了。 这么难的问题，到底有什么实际意义呢？要知道，计算这个问题所需的计算量足以做好几年的天气预报了，如果一点实际用途都没有的话那看起来还真是有点浪费。 不过你还真的别说，这东西除了在天线中和编码理论有点实际用途之外，就剩下理论上的趣味性了。那么，为什么那些数学家会对这样一个没多大用处的东西投入这么多的精力，连智商过人的 Golomb也是如此呢？又是为什么全球的志愿者都肯为这个东西投入如此多的计算能力呢？问题的答案在于两个字：“有趣”。已故的陈省身老先生说过，“数学有趣”，正是这个“有趣”使他们情不自禁不能自拔，也正是这个“有趣”使他们具有了一种对付越来越难的问题的勇气和信心。 所以说，有时候做研究不一定因为有用才去做，兴趣有时候是更好的导师。 延伸阅读： 这里有一个关于最简优化尺和Distributed.net的中文介绍：http://www.equn.com/forum/thread-4312-1-1.html Distributed.net官方网站：http://www.distributed.net/ 关于循环差集的一个很有趣的英文介绍：http://www.inference.phy.cam.ac.uk/cds/index.htm 16 november 镜城注：本文遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！ 今天又是个晴天，他想。
……………………………… 一片黑暗，他只来得及意识到这点，意识又立刻丧失了。 ………………………………
他睁开眼，还在公司的办公室里边。这也算是我的家了，他想，反正用具一应俱全，虽然还缺了点什么，但也无所谓了。 25 oktober 最“经济”的直尺注：本文遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！
直尺算是一样非常常用的工具了，要想线画得直，不请直尺出场恐怕是不行的。但它的主要用途还不在这里。画直线，IC卡也可以，但是如果要在纸上量度一段距离的话，还是要等直尺出马，因为IC卡没有刻度。这样说来，如果说刻度是直尺的灵魂，相信没有人会有异议。数学家们说得好，一把有刻度的直尺顶得上一把圆规，因为我们只需要一把有刻度的直尺就能完成任何尺规几何作图。 扯得有点远了，还是回到刻度上来。我们平时用的直尺大概有刻度的范围有15厘米，每厘米有一个大刻度，每毫米有一个小刻度，用起来的确相当方便。但是在数学家（更确切地来说是组合学家）眼中看来，这种标记刻度的方法未免太浪费。如果一把直尺有8个刻度的话，刻度之间两两组合最多能量出28种距离，而如果沿用普通直尺的刻度方法的话，我们只能量出从1到7一共7种距离。为什么会这样呢？想想看，有7种组合可以量出距离为1的线段，这样的话就浪费了6种刻度组合了。这当然算不上是一个很经济的办法。 于是自然而然，这些多事的数学家们就开始考虑一个问题了：要怎么样标记刻度才能使每对刻度的组合量出的距离都不同，从而避免浪费呢？当然，在这里0的刻度是肯定要标的，毕竟是自然数的起点嘛。如果没有别的限制的话，这个问题是不难解决的。还是举刚才8个刻度的例子，如果我们分别把刻度标在0、1、3、7、15、31、63、127的话，容易验证每对刻度组合量出的距离都不相同。一般地说，对于有n个刻度的直尺，如果我们把刻度分别刻在2的k次方减1（k可以从0到n-1）的话，这把直尺就满足这些数学家提出的条件了。 但是这时候，造直尺的商人就开始有异议了。数学家们很奇怪，我们不是帮你们节省了刻度的费用么，这个建议不是挺好么，为什么不接受呢？ 商人也不多说，直接拿出了两把尺子。 “你们自己看看，同样是8个刻度，我的直尺只需要7厘米的材料，你们的方案却需要一米有余。原材料不要钱啊？” 于是数学家们被迫在他们的问题中加上一个补充条件，现在他们要寻找的刻度方案既要是“经济”的，也就是说每对刻度组合量出来的距离都不同；又要是最小化的，也就是说在满足这个条件的所有刻度数相同的刻度方案之中尺子长度最小的。这样一来，这个问题的答案就远非显然了。 当然，上面的对话是我虚构的。即使没有商人的要求，数学家们也会以一种类似自虐的方式不停给自己提难题，或者是将已经解决的问题加大难度。事实上，第一个考虑这种尺子的是美国数学家Solomon W. Golomb，这是个颇为严肃的，没啥花边新闻的组合学家。而这种尺子很自然也以他的名字命名，叫做Golomb尺，毕竟是他第一个提出这个问题的。一个刻度方案只需要满足“经济”的条件就可以被称为Golomb尺，也可以叫优化尺。如果这个刻度方案同时满足最小化条件的话，它就被称为最优Golomb尺，也可以叫最简优化尺。 进行了这样的限制之后，问题明显变难了，但是到底有多难呢？答案可能会令你很惊讶：目前为止我们仅仅确定了含有25个或以下刻度的最简优化尺方案，而含有25个刻度的最简优化尺还是昨天才通过大规模的全球志愿者电脑联网计算确定下来的。 完成这个计算的是一个叫Distributed.net的分布式计算项目，经过了全球志愿者共三千零六天的计算才最终决定了含有25个刻度的最简优化尺方案，而它的运算能力相当于7500个英特尔的酷睿处理器。也就是说，要找到含有25个刻度的最简优化尺方案，需要7500个英特尔的酷睿处理器同时工作3006天才能完成这个任务！可见这个任务是多么艰难。 现在有人猜测，确定含有n个刻度的最优简化尺是一个NP-难问题，也就是说我们不可能找到一个有效的算法来对这个问题进行计算！为什么问题会突然间难了这么多呢？罪魁祸首就是最小化的条件。如果没有最小化的条件的话，我们就已经有了答案了。加上最小化的条件之后，我们要证明一个优化尺是最简的话，就需要检查每一个长度比它小的刻度方案，并且证明它们都不是优化尺。但是，只要学过组合数学就会知道，当刻度个数一定的时候，长度一定的刻度方案的个数是以阶乘速度增长的！
这样的话，当刻度增加，长度也会增加，从而对于每一个长度要检查的刻度方案数量也会呈阶乘速度增长。由于我们要检查的长度不止一个，所以难度增加的速度就更加大了。这样的话就不难解释为什么直到现在人们只确认了刻度数目不高于25的最简优化尺方案了。 虽然要确认一个优化尺方案是否最简是很困难的，但要给出一个很接近最简方案的优化尺还是可以做到的。实际上，数学家们早就对一种与优化尺相似的数学对象相当熟悉了，这东西有一个很唬人的名字：循环差集。虽然名字听起来比较吓人，但是循环差集其实并不难理解，它其实就是优化尺的环形版。当然啦，直尺不能弯成一个圈，除非是广告商用塑料或者纸做的那种满大街派发的便宜货。既然这样，我们就要寻找另一个比较贴近实际生活的模型了。 大家对和尚用的念珠比较熟悉吧，对对，就是唐僧那种。当然我也不排除某些同学对念珠菌比较熟悉，但别搞错，我们现在说的是环形的那种念珠。通常和尚用的念珠都是单调的黄色组成的，这跟他们念的经也比较适合，但对于那些只想买念珠来炫耀一下的游客来说这就未免太无趣了。那就加点蓝色的珠子吧，为了不无聊，我们规定每对蓝色珠子的距离都不相同。这样的话，这些蓝色珠子排布的方案就可以组成一个循环差集了。循环，是因为念珠可以随便旋转，而“差”来源于对距离的要求，因为距离实际上就是位置差。
好了，在我们上面描述循环差集的模型中，你有没有发现些熟悉的东西？“每对蓝色珠子的距离都不相同”，这跟优化尺的定义不是一模一样么？这样说来，循环差集跟优化尺的差别仅仅在于循环差集是可以“循环”的，而优化尺不能。现在我们要找的是最简优化尺，自然而然，我们就会想到，怎么样才能把循环差集转化为优化尺呢？很简单，循环差集比优化尺要多一个“循环”的对称性，我们只要把这种对称性给破坏了不就得了！ 于是，某邪恶人士拿出一把剪刀，对着方丈刚串好的黄蓝相间的念珠一剪子……念珠怨念地撒了个满地都是…… 唉，所以说做人不要那么心急，先听清楚怎么剪再下手，这才是严谨的精神嘛。首先，剪好之后要平摊在桌子上，两头各打个结，这样不就不会散开了嘛。然后因为我们看的是蓝色珠子，所以打结两头如果有黄色珠子的话就扔掉吧，反正也没用。做好之后，观察一下蓝色珠子的位置，这是不是相当于一个优化尺？只不过它量度的单位是珠子的直径而已。
可以证明，无论我们怎么剪，得到的一串东西之中，蓝色珠子的位置方案都相当于一个优化尺，这样的话我们就完成了刚才的任务了。 不过话又说回来，这还是不够的。既然随便剪都可以的话，有没有办法剪得巧妙一点，使最后得到的优化尺尽量短呢？回想一下，既然在剪断念珠之后我们要扔掉两头那些没用的黄色珠子，而一串念珠的个数又是有限的，那么我们扔掉越多，剩下的珠子不就越少，优化尺不就越短了？要想扔掉尽量多的黄色念珠，我们在两颗相邻的但是距离最远的蓝色珠子之间剪一刀不就行了！ 这样的话，我们把念珠重新接好再剪一次，对比一下：
嗯，看来这是个好办法。如果我们对于正整数n能够找到含有n个蓝色珠子的循环差集，而使这个集合里边包含的念珠尽量少的话，剪一刀我们不就可以得到相当接近最简优化尺的一个优化尺方案了么？这看起来的确不错，然则有一个问题我们还没有想到。如果寻找符合条件的循环差集比寻找最简优化尺还要困难的话，我们这么麻烦绕这么大一个圈不是浪费生命么？ 幸好，由于循环差集比优化尺的性质好得多（循环总是很讨数学家的欢心，嗯），寻找循环差集比寻找最简优化尺要容易得多。事实上，数学家们已经有一种方法可以直接生成那些可能是最符合条件的循环差集。这种方法一时半会是说不清的，大概就是将循环差集和一个所谓的“有限半线性空间”联系起来，这个“空间”里边有一些“点”和“直线”，分别代表了念珠编号和循环差集的一种读法，它们满足一些限定这个空间性质的公理，而通过这个“空间”数学家们就能找出最符合条件的那些循环差集。有趣的是，虽然名为“空间”，这东西和我们平时的观念可是大不相同，比如说“直线”上面只有有限个“点”等等。只有脑子学得迷迷糊糊连常识都忘掉了的那些数学家才能完全掌握它们的性质，当然为了这个他们也牺牲了不少东西…… 那么，这种方法的威力有多大呢？早在1984年，数学家Atkinson和Hassenklover就已经用这种方法给出了直到100个刻度的优化尺方案，而之后的验证证明，即使这些优化尺方案不是最简的也相当接近，比如说这次，Distributed.net验证得到含有25个刻度的最简优化尺就是当年他们给出的那个： 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480 但很可惜的是，虽然这些优化尺方案非常接近最简的方案，但现在数学家们仍然没能证明用循环差集给出的优化尺方案就是最简的，所以数学家仍然需要用大规模计算的方式来验证一个最简优化尺方案。不过，因为已经知道一个非常接近答案的方案，所以搜索起来相对来说也容易多了，尽管与电脑游戏相比还是相当相当的难。 这么难的问题，到底有什么实际意义呢？要知道，计算这个问题所需的计算量足以做好几年的天气预报了，如果一点实际用途都没有的话那看起来还真是有点浪费。 不过你还真的别说，这东西除了在天线中和编码理论有点实际用途之外，就剩下理论上的趣味性了。在射电望远镜的天线阵列中，天线的排布就常常是排成0-1-4-6的样子，可能也是为了尽可能好地利用天线位置测量吧。至于在编码理论中的用途嘛……我也不清楚……反正在信息交流越来越多的今天，编码理论的地位已经变得相当重要了，能有点用也算不错了。 那么，为什么那些数学家会对这样一个没多大用处的东西投入这么多的精力，连智商过人的Golomb也是如此呢？又是为什么全球的志愿者都肯为这个东西投入如此多的计算能力呢？问题的答案在于两个字：“有趣”。已故的陈省身老先生说过，“数学有趣”，正是这个“有趣”使他们情不自禁不能自拔，也正是这个“有趣”使他们具有了一种对付越来越难的问题的勇气和信心。 所以说，有时候做研究不一定因为有用才去做，兴趣有时候是更好的导师。 延伸阅读： 这里有一个关于最简优化尺和Distributed.net的中文介绍：http://www.equn.com/forum/thread-4312-1-1.html Distributed.net官方网站：http://www.distributed.net/ 关于循环差集的一个很有趣的英文介绍：http://www.inference.phy.cam.ac.uk/cds/index.htm 12 oktober 所有含有31个顶点的树都是优美的! All trees with 31 nodes are graceful!经过一个月的计算，我，fwjmath，和我的笔记本宣布，经过计算，所有含有31个顶点的树可以分为两部分，一部分可以用一个确定性算法给出一个优美标号，而对于另一部分，我们可以显式地对每棵树给出一个优美标号。这也就是说，我们已经证明，所有含有31个顶点的树都是优美的。 After 1 months' calculation, I, fwjmath, with my laptop, declare that all trees with 31 nodes can be divided into 2 classes, one in which every tree can be given a graceful labeling by a determinist algorithm, and for the others a graceful labeling can be given explicitly to every tree. In other words, we have proved that every tree with 31 nodes is graceful! Après un calcul durant 1 mois, Je, fwjmath, avec mon ordinateur, proclame que les arbres avec 31 noeuds peuvent être classés dans 2 catégories, l'une dont un algorithme déterministe donne à chaque arbre un marquage gracieux, l'autre dont un marquage gracieux est explicitement donné à chaque arbre. En conclusion, tout arbre possèdant 31 noeuds est gracieux. 这次计算所用的算法是改进过的，而且将计算任务分配到了双核的两个核心，所以速度有了比较大的提升。关于优美图的介绍，请参见：http://fwjmath.spaces.live.com/blog/cns!6A37A2A4F21FF4DE!1205.entry The algorithm is optimized for speed and modified for work distribution to 2 cores, so an important gain of speed is observered. For information on graceful labeling, please read http://fwjmath.spaces.live.com/blog/cns!6A37A2A4F21FF4DE!1205.entry L'algorithme est optimizé et modifié pour partager le travail entre 2 CPU, d'où vient un gain important de vitesse. Pour savoir plus sur le marquage gracieux, cf http://fwjmath.spaces.live.com/blog/cns!6A37A2A4F21FF4DE!1205.entry 下一步我将会整理数据和资料，为TIPE做准备。 Ensuite, je vais ranger les données pour mon TIPE. 25 augustus 所有含有30个顶点的树都是优美的! All trees with 30 nodes are graceful!经过两个多月的计算，我，fwjmath，和我的笔记本宣布，经过计算，所有含有30个顶点的树可以分为两部分，一部分可以用一个确定性算法给出一个优美标号，而对于另一部分，我们可以显式地对每棵树给出一个优美标号。这也就是说，我们已经证明，所有含有30个顶点的树都是优美的。 After more than 2 months' calculation, I, fwjmath, with my laptop, declare that all trees with 30 nodes can be divided into 2 classes, one in which every tree can be given a graceful labeling by a determinist algorithm, and for the others a graceful labeling can be given explicitly to every tree. In other words, we have proved that every tree with 30 nodes is graceful! Après un calcul durant plus que 2 mois, Je, fwjmath, avec mon ordinateur, proclame que les arbres avec 30 noeuds peuvent être classés dans 2 catégories, l'une dont un algorithme déterministe donne à chaque arbre un marquage gracieux, l'autre dont un marquage gracieux est explicitement donné à chaque arbre. En conclusion, tout arbre possèdant 30 noeuds est gracieux.
关于优美图、优美树和优美标号的介绍，请参看这两个链接： http://topic.csdn.net/u/20080322/16/c5441587-d534-4bfb-8033-87367c452985.html http://en.wikipedia.org/wiki/Graceful_labeling 简单地说，假设有一颗树T拥有n个顶点，如果存在对顶点的一个由0至n-1的不重不漏的标号方法，使每条边由此诱导出来的标号（即为边的两个顶点标号的差的绝对值）为从1到n-1的不重不漏的n-1个数的话，那么我们称这个标号方案是一个优美标号，而这棵树也被称为优美的。注意，在这里关于优美性的论述只对于树有效。 图论中著名的Ringel-Kotzig猜想断言：所有的树都是优美的。这是一个尚未证明而意义重大的猜想。曾经有很多人尝试证明这个猜想，但都没有成功。而也有人对这个猜想进行数值上的验证。在此之前的记录是任意含有29个顶点的树都是优美的，这个结论是由Michael Horton在10台计算机上用了总计58天的CPU时间作出的。
About graceful labeling, please have a look at this: http://en.wikipedia.org/wiki/Graceful_labeling If you are interested and want to know about details, please contact me via:
在接下来的一段时间中，我会对我的算法进行进一步的优化和调整，然后继续冲击n=31！ After this, I'll optimize and modify my program for the next aim of n=31！ Ensuite, je vais optimizer et modifier mon algorithme pour le but suivant, n=31! 11 mei 从福尔摩斯到衍射：现代科技拾贝注：本文遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！ 序这个文章是我跟pchu说好了一起写的。规则很简单：他跟我分别给出两样东西，分别作为开头和结尾。他给的开头是福尔摩斯，我给的结尾是衍射，这就是这个奇怪题目的由来。当然，在这种限制下想写出很系统化介绍某种东西的文章是很困难的，所以大家可能就只能看到一些东西的片断，所以就将就一下吧。好了，我们开始旅行了，出发！ 起点：福尔摩斯的眼睛福尔摩斯这个英国著名侦探小说家柯南·道尔笔下的人物，想必大家对他都很熟悉。而大家对他最为称道的恐怕就是他那双锐利的眼睛了。他能通过裤脚上的泥点推断出一个人在来之前到过伦敦什么地方，也能通过一个人的外貌判断出这个人的身份和职业，甚至还有曾经到过的地方。福尔摩斯的断案能力恐怕是跟他敏锐的观察力息息相关的，但是在观察力的背后还有一个重要的因素就是他丰富的刑侦知识。 当然，福尔摩斯只是一个小说人物，但是他的这种超乎寻常的观察力和推理已经成为了大家对于一个优秀侦探的基本印象，以至于现在“现代福尔摩斯”已经成为了人们对那些优秀侦探的尊称。当然，由于科技的发展，现代的侦探的工具比福尔摩斯用的尺子和烟斗要优秀得多。这些现代工具让侦探们拥有了比福尔摩斯更敏锐的观察能力。可以说，这些工具让侦探们具有了“福尔摩斯的眼睛”。下面我们就来简单看一些例子。 关于刑侦技术，大家可以第一个想到的就是美剧CSI中描述的各种先进的技术。但是事实上现实生活中没有多少案件是可以用到这样高级的技术的。刑侦中用得最多的技术，恐怕就是最基础的血液分析。由于重大案件通常会伴随着流血或者凶杀事件，所以对于血液的研究对于侦查是十分有用的。 对于血液的分析，第一步就是对血液痕迹的确定。在电视剧里边大家可能会看到侦探们用一种喷雾喷洒地面，然后再用紫外线灯照射，有过血迹的地方就会呈现蓝白色的荧光。其实这种喷雾就是一种特殊的化学物质和过氧化氢的混合物，这种化学物质名为鲁米诺试剂（luminol），也叫发光氨。这种试剂检验血液痕迹的原理很简单。血液中含有血红蛋白，其中含有铁离子，是过氧化氢分解的一种催化剂。过氧化氢分解时会释放出具有强氧化性的单个氧原子，然后氧原子就会与鲁米诺试剂发生氧化还原反应，使鲁米诺试剂发出蓝白色的荧光。知道原理之后，我们可以想到既然是氧化还原反应使鲁米诺试剂发出荧光的话，岂不是很多化学药品都可以做到这一点？事实上，这种血液的检测方法的缺点也就在于这里。如果罪犯事先用家庭常用的漂白粉清洗过现场的话，现场也会残留具有氧化性的氯化合物，会对荧光的判断造成干扰。不过，有经验的侦探通常都可以分清两者的区别，另外一种规避的办法就是先让犯罪现场干燥几天再进行血迹检测，这时候不稳定的氯化合物会分解殆尽，干扰也就会降低。当然，这种方法由于准确度有限，所以通常鉴定出血迹之后侦探们还会用别的方法来进行对比鉴定。尽管有这些缺点，这种血迹鉴定的方法还是被广泛采用，因为它也有几个很明显的优点。首先，它不会对血迹的化学成分造成干扰，因为血迹在这里是作为催化剂出现的，这样就给后期的证据提取提供了方便。其次，这种方法可以检测出浓度为百万分之一的血液痕迹，普通的清洗方法对它的干扰不大，而且根据荧光的强度等等信息可以推断出血迹出现的大概时间。最后，这种方法简单易行，而且成本不高，便于广泛铺开使用。所以这种检验方法实在是很流行。 血迹提取出来了，接下来的工作有两个方向，一个是轨迹分析，另一个是成分分析。轨迹分析说白了就是根据血迹的形状推断凶手作案的工具和方式，比如说在凶手挥动凶器的时候，可能会有微量的死者血液随着凶器的挥动溅到墙壁和天花板上，通过对这些血液痕迹形状的分析我们可以知道凶手使用的凶器的大致大小、形状和类型，甚至还可以知道凶手当时挥动凶器的力度和轨迹。成分分析就更为复杂。一般来说，现在的技术已经可以分清血迹是人血还是动物血，可以辨别血型，最后最强大的一招就是提取DNA样本，然后用PCR等方法倍增后与犯罪嫌疑人的DNA进行比对。由于DNA相当于一个人独一无二的标记，所以这种方法的准确率极高。不过由于成本实在很高，所以也不经常采用。 除了血液的处理之外，还有一样很基础的刑侦技术就是指纹提取。人们很早就观察到，每个人的指纹都有独特之处，两个人的指纹相同是几乎没有可能的。人的皮肤又会不停分泌油脂和汗液，这些物质在手指接触其它物体的时候会在物体上面留下痕迹，这就是指纹。正是因为这样，指纹的提取才成为了刑侦中的一个重要元素，因为这种方法成本较低，方便快捷，而且准确率也颇高。 通常被提取的指纹都是位于凶器表面或者是墙壁桌子镜子等光滑表面上的，因为这些表面上的指纹比较容易提取。提取的方法也很多，大多数都是先使指纹显形，然后再照相记录。提取的方法有很多，最简单的就是用光照的办法，因为油脂等等物质虽说透明，但毕竟是杂质，会对表面的光学特性有影响。所以通过光学的方法可以辨析出一部分指纹。常用的方法有很多，有时候就算用普通的光源都能发现指纹，有时候就需要一些特殊的光源比如说紫外线灯。另一种常用的方法就是利用油脂容易粘住小东西的特性，用粉末来进行提取。这种方法也是很方便的，大家在家里就可以用奶粉试试，也可以使用碘的蒸汽。不过这两个方法在指纹很“老”的时候就会失去效用，那时候就要用更高级的物理和化学方法来处理指纹了，其中最简单的就是硝酸银法。因为汗液中含有氯化钠，而银离子对氯离子是很敏感的，于是我们就可以利用这个反应使指纹显形。当然，这些提取指纹的方法，犯罪分子用一个手套就可以使它完全失效。不过也有通过犯罪分子丢弃的手套来提取指纹的案例，这就只能怪贼太笨了。 在信息化的今天，侦探们除了面对暴力犯罪以外，还要对付高科技犯罪。这些犯罪也迫使侦探们发展出针对这些信息技术的侦查技巧和工具，其中除了大家熟知的网络入侵痕迹检查和数据复原技术等等之外，还有一些很偏门的东西，比如说利用操作系统本身的一些不算是漏洞的缺点，还有就是直接利用无线电方法。 大家知道，我们的电脑在删除文件的时候，大半是只会将文件的索引删除，文件的真实内容仍然好好躺在硬盘里边。这就是一些入门级的数据恢复软件可以处理的范围。现在市面上也有所谓的“文件粉碎机”之类的软件出售，这些软件大多是通过覆盖文件所在扇区的内容来彻底消灭痕迹的。而美国军方销毁文件的标准做法是对文件所在扇区用全0和全1间隔覆盖8次，力图消去可能的剩磁。但是有时候其它文件也会透露出一些重要信息。磁盘系统的写入单位是簇，一簇的大小大概是几KB。但是一个文件不一定能够完全占据整数个簇，这是操作系统就会用内存的数据去继续填充。这样的话通过分析这些内存数据，侦探们有时候也能发现一些线索。 无线电监听就更直接了。早在20世纪中期，贝尔实验室的研究人员就已经发现电子仪器的操作会发射一些电磁波，通过检测这些电磁波可以大概知道电子仪器进行了什么操作。于是乎，美国警方就又发明了一种新的侦查方法。他们可以直接把车停在犯罪嫌疑人的屋外，利用无线电来监听屋内键盘的操作，这样的话无论是多高深的技术都如玻璃一样透明了。 虽然侦探们拥有了这么多的对付高科技犯罪的方法，有一样东西还是他们无能为力的。这不是因为科技发展还不够的问题，而是科技已经发展到可以证明侦探们对这样东西是无能为力的了。那就是密码。 第二站：密码，人类智慧的较量密码术由来已久。最早的密码恐怕要追溯到埃及金字塔上的象形文字。在一些金字塔上就有用形态相似读音不同的象形文字互相代替的现象，不过这看起来更加像某种吸引游人停留的手段。密码术的最早有实际意义的应用恐怕还是在我们中国。比如说古代的用兵凭证“虎符”本身就有密码的功能，既能代表一些简单的信息，也能证明来人的身分，因为虎符本来是一体的，剖开后就可以依据花纹是否相合判断是否原件。还有竹简书写术和密码诗等等就不细说了。西方的密码应用也很早，最有名的就是圆筒书写法。首先寄件人将布条缠在某一直径的圆筒上，然后再在布条上写字。解开后布条上就有一列被打乱了的字迹了。收件人收到布条以后，只需要将布条往相同直径的圆筒上一缠，马上就能读出寄件人写的内容。而在这个过程中，传信的邮差由于不知道圆筒的直径，所以根本不能了解布条上写的内容。如果说金字塔上的密题是字母替换密码的先声的话，这种圆筒书写法恐怕就是移位加密法的前身了。 在密码学研究当中，我们通常有如下的术语。要传递的信息叫做明文，就像寄件人写的内容。在传递中别人无法阅读的信息叫密文，就像邮差手上的布条。将明文转化为密文的过程叫加密，将密文转化为明文的过程叫解密。在加密过程中用的决定加密结果的信息叫加密密钥，在解密过程中的就叫解密密钥。在很多时候加密密钥和解密密钥是一样的，在圆筒加密法中的对应物就是圆筒的直径。通常在一个例子里边，我们将发信人称为爱丽丝（Alice），收信人称为鲍勃（Bob），而尝试监听这两者通讯的人叫做伊芙（Eve）。 由于单纯的移位加密容易通过分析语言和词语结构破译（当然也有例外，比如说旋转天窗法），所以人们对于替换加密法的研究比较多也比较丰富。 最早的替换加密法叫单字母替换密码。顾名思义，这种加密方法就是根据一个替换表将所有字母替换成别的字母，从而就使不知道这个替换表的人无法阅读。在这里，加密密钥和解密密钥都是这个替换表。可惜的是，这种加密方法很快就被破解了，因为每种语言都有它固有的结构，最常见的就是字母出现的频率。在爱丽丝和鲍勃的通讯中，伊芙只要截取到密文，就可以通过字母频率再加上语言上的知识将替换表反推出来。如果只用语言知识的话有时候也可以解决，不过难度可能有点大。我手头上就有这么一份密文，当时可费了我不少的工夫，当然我只是分析语言结构而已。 单字母替换密码被破解后，它的各种变种层出不穷。有的利用多个代号代替一个字母，希望用这样的办法将字母频率方面的信息抹平。最极端的例子可能是所谓的“比尔密码”，用一篇文章的单词作为载体，每个代号n表示的就是这篇文章的第n个单词的首字母。这样的话很容易想到如果这篇文章遗失的话，密码就有可能永远无法破译，所以这并不算是一种很安全的加密方法。 另外一种比较流行的变种就是使用多个替换表，最终就发展出了维热纳尔密码。维热纳尔密码是法国外交家Blaise de Vigenere在16世纪后期提出的，旨在用多个替换密码表来克服字母频率的问题。具体的加密方法很简单。首先爱丽丝和鲍勃先选定一个单词作为共同的密钥，然后爱丽丝将这个单词每个字母代表的替换表从维热纳尔方阵之中抽取出来，将明文每个字母轮流循环用这些替换表加密。解密的时候鲍勃也如法炮制。这样就顺利抹平了字母出现的频率了。 这样优良的密码学特性使维热纳尔密码坚持了不短的时间，直到大约两个世纪后才被当时普鲁士少校卡西斯基（Kasiski）和英国科学家、计算机创造者之一查尔斯·巴比奇（Charles Babbage）分别独立破译。他们用的方法殊途同归，后来被称为卡西斯基方法。这个破译法的关键就在于语言结构。在很多语言中，有一些单词出现的频率特别高，比如说英语中的the。这样的话，很有可能有两个单词the的加密方式完全一样，这样的话两个the生成的密文也就会相同，而且之间的间隔是密钥长度的倍数。只要收集到足够的这样完全相同的密文片断，伊芙就可以推断出密钥的长度，从而就可以将不同替换表加密的密文分离出来。现在问题就变成了多个单字母替换密码的破解了，而这个我们很清楚是可以攻破的。于是这样，沿用了两个世纪的维热纳尔密码就这样被破解了。 当然，这个加密方法并不是完全没有弱点的。它的一个重要假设就是密钥长度远小于明文长度，只有这样才能造成重复，才能进行下一步的破解。如果密钥长度就等于明文长度的话，卡西斯基方法就毫无用武之地了。这种加密的方法被称为“一次性便笺”，因为每次使用的时候密钥都要重新随机生成。这种加密方法显然是不能被破解的，因为本来密钥就是完全随机的，所以不同的明文完全有可能生成相同的密文。这种一次性便笺密码似乎就是所有密码编制者的梦想：一个不能被破解的密码。 但是不要高兴得太早。虽然在理论上这个加密方法是不能被破解的，但是在实际应用上它会遇到一个不可避免的问题：密钥分发。要爱丽丝和鲍勃都能顺利进行加解密，他们两个就要首先达成密钥的一致。这样的话，为了不泄漏密钥，他们可能要亲自见一次面，交换一大堆密钥，而这在实际应用中是很难做到的，因为分发这样的完全随机的密钥记录本而又要求保密的话费用会很高。所以，这种最安全的密码现在应用范围很窄，只适用于那些不计成本要求安全的地方，例如国家元首之间的热线。 经过卡西斯基方法之后，数学分析法在密码学中就开始了它的长盛不衰的统治。不仅是破译密码，连构造密码都用到了数学。随着机器的自动化，自动加密机器也出现了。最有名的自动加密机器应该就是在二战中德军使用的“恩格玛”（Enigma）了。这种加密机器由插线板、转盘和反射器构成。插线板将输入输出转盘的字母交换，转盘本身就是一个替换表，一共有三个转盘，每加密一个字母转盘都会转动发生变化，相当于使用了不同的替换表，而反射器则是将转盘的字母信号反射到另一个字母对应的路径上。这样的设计既方便使用，又有很大的加密强度。密钥就是使用的转盘编号、对应转盘位置的三个字母和几对插线板的交换字母对，实际上有一亿亿种不同的可能性，加密强度很大，也很便于分发。所以恩格玛在德军战场上使用了相当长的一段时间。 在初期，恩格玛的确给德军带来了不少的便利。原本对德国密码攻无不克的盟军突然发现他们遇到了一个难懂的谜语。但是这种机器提供的安全性也麻痹了德军的安全思想，最终导致了一系列的破译进展。首先是法国人通过间谍行动在德国人手中得到了恩格玛机的电子线路，然后是波兰数学家雷杰夫斯基（Rejewski）通过开头重复密钥的漏洞，利用置换群的特性攻破了比较容易入手的一些恩格玛系统。在德国人弥补上这个漏洞之后，又有英国人利用战场上士兵没有时间生成随机密钥的弱点，成功识别出了一些有规律的密钥“色利斯”（Cillies）。最后，英国数学家、计算机创始人之一阿兰·图灵（Alan Turing）通过猜测明文的攻击，用类似雷杰夫斯基的方法给了恩格玛致命一击。由于这种攻击方法需要很多枯燥的计算，图灵甚至设计了名为“炸弹”的机器（跟雷杰夫斯基的机器同名但是原理不同）来专门做这项工作。恩格玛的破译再加上盟军的间谍行动最终使盟军能够洞识大部分德军的行动，为二战的胜利做出了不少的贡献。 从上面恩格玛被破译的过程，我们可以知道有时候密码被破译未必是因为密码系统安全性不够，而有可能是因为使用者不够小心，泄漏出了密码的规律。比如说雷杰夫斯基的破解方法基于德国人的重复输入密钥，色利斯就是利用德军有时候没时间或者懒得想随机密钥的弱点对恩格玛进行破解的，最后图灵的方法也是利用德军的规范化的电文来进行已知明文攻击的。与此情况相反的是，德军海军的恩格玛系统就没有被盟军用纯粹的密码学方法破译过，这是由于这个系统的机器拥有更多的转盘，密文开头没有重复的密钥，而且明文格式不规范，这样就避开了所有的攻击。所以说，有时候一个密码系统的安全性不仅取决于这个系统的算法安全性，而且还取决于使用它的人。如果使用者不注意密码安全的话，再强大的密码也会有被攻破的可能。 在计算机出现以后，密码系统的发展达到了极致，而密码分析的工具也同样大大得到了扩展。传统密码方面出现了DES和它的后代AES，它们是美国加密的国家标准，还有别的算法比如说Blowfish, RC5等等。尽管密码分析家绞尽脑汁也不能破解这些密码。但是这些算法都有一个问题，与一次性便笺一样的问题：密钥分发。可以说，整个系统的最大风险就在这个地方。那么，到底有没有办法避免这个问题呢？ 二十世纪七十年代，分别有两个小组（Ellis, Cocks, Williamson; Diffie, Hellman）给出了答案：有。 它们的系统都是基于同一个原理：存在这样的数学问题，解决它很容易，但是解决它的反问题就极其困难。举个例子：将两个大质数乘起来，很容易；但是将一个大合数分解为两个质数的话就不容易了。这样的数学问题在密码学上有一个特别的称呼：单项陷门函数。根据这个原理，我们就可以设计出这样的密码系统，在这个系统中，加密密钥和解密密钥是分开的。加密密钥可以公开，让所有人都可以给你发送加密信息，但是解密密钥只是在你手中，只有你能对这些发送给你的密文解密。从解密密钥推出加密密钥的过程相当于计算一个单向陷门函数，这是轻而易举的；但是反过来就不一样了。所以，在这种系统里边，只要密钥的复杂度足够高，我们就不需要担心密钥的分发问题了。这种密码系统被称为公钥密码系统。这种系统的另外一个优点就是，如果将加密密钥和解密密钥的作用反过来的话，它就会变成一个身份认证系统，这在很多场合都是很有用的。 在各种各样的公钥密码系统当中，最为人熟知的就是RSA。RSA所用的单项陷门函数就是刚才在上面提到的大质数乘法。质数越大，密码就越难破解。现在最大的被公开破解的RSA密钥就是RSA实验室提出的RSA挑战之一RSA-640。这个密钥长度为640个二进制位，破解人投入了相当于一台Opteron 2.2GHz的电脑连续运算30年的运算力才最终破解了这个密钥，而普通用户使用的密钥长度通常为1024个二进制位。这样的话我们可以相信这个密码体系对于现在来说是足够安全了。 密码学家甚至还想到了直接依靠作为宇宙运行规则的物理原理作为加密系统的基石。量子密码就是一个很好的例子。在这里由于篇幅关系就不仔细介绍了，大家可以自己查阅相关的资料。利用量子密码系统，人们可以方便而又保密地分发密钥，从而给一次性便笺密码带来了新的机会。现在量子密码的研究已经有了很大的发展，已经有公司提供商用的量子密码，比如说美国的MagiQ公司，而且他们的量子密码可以在光纤中传播几十公里仍能正常读取。不过由于密钥生成的速度实在太慢，量子密码通常只是被应用作保密分发传统密码密钥的一种方式。 当然，密码破译者也不会闲着。我们从上面的故事看到，计算机的发明者通常都是密码的克星。那么，新时代的计算机发明者又会给我们带来什么呢？ 第三站：下一代实用计算机我们现在的生活真是须臾离不开计算机。工作娱乐用个人电脑，出去买东西的话刷卡机连着银行的计算机网络，就连去饭堂吃个饭也要打卡。而且现在的电脑也越来越快了。 但是，这种繁荣背后也隐藏着令人担忧的事实。随着人类科技不断发展，人们要求的计算能力也越来越多。以往人们是依靠增加CPU晶体管数目来增加计算能力的。但是，随着晶体管数目的增加，同一块硅片上刻制的晶体管必然会越来越小，而这个小的程度是有限制的，如果从物理学来讲的话就是原子的尺度，如果从现在的工艺来说就是刻制光的波长。总之，一直按照这条路发展下去的话计算机工业必定会走进死胡同。除此之外，计算机还有种种不大令人满意的问题，比如说计算能力等等。这样的话，研究下一代的计算机的各种可能模型就显得十分重要了。 量子密码提醒我们，这是世界除了我们熟知的牛顿式的确定性以外，还存在着量子领域的不确定性，而这种不确定性有时能够带给我们意想不到的惊喜。同样根据量子原理构想出来的量子计算机正是这样的奇迹之一。 我们现在用的计算机有一个很大的特点，就是确定性。我们给什么数据和程序，它就只会按照程序傻乎乎地一步一步来，没有远见。在计算科学的范畴里边，现在的计算机被称为“确定性图灵机”。这个图灵机就是由那位破译恩格玛的图灵提出的一个计算机的数学模型，直到现在还广泛应用于计算理论的各种定理中。然而，确定性图灵机并不是最强大的计算机器模型。如果我们设想有一台拥有超能力的机器，如果我们问它一个不超出它“感应”的范围的问题，它能够立刻“猜”出答案，这样的机器从直觉上来说也会比我们现在拥有的确定性图灵机要强大得多。事实上，这种机器在计算科学中被称为“非确定性图灵机”，而且已经被证明是比图灵机更高效的计算机器。 那么，我们如何去造出这样的一台机器出来呢？粗看起来这似乎十分玄乎，怎么会有机器可以“猜”答案呢？然而世事无绝对，量子力学就给我们提供了这么个工具。举个例子，电子可以有两个方向相反的自旋。如果在经典世界的眼光中，一个电子的自旋非此则彼，没有中间路线可走，但在量子世界中，事实上电子可以处在“既此又彼”的状态中，这就是量子态的叠加。如果我们把电子逆时针自旋的量子态记为|0>，顺时针的量子态记为|1>的话，在经典世界中电子的状态不是在|0>就是|1>，但是在量子世界中电子的状态可以是a|0>+b|1>，a,b分别是电子处在这两个状态的几率的平方根。这种特殊的叠加态就是量子计算机的基石，qubit（也叫量子比特）。 那么，量子计算机是如何处理这种qubit呢？很简单，如果机器能处理5个qubit的话，先将5个qubit赋值(|0>+|1>)/sqrt(2)，然后对它们进行一种叫幺正变换的运算，最后测量着几个qubit的状态就可以知道结果了。因为每个qubit的初始状态都处于等可能的状态，对这5个qubit进行一次运算就相当于同时进行了2^5种可能的经典状态的运算。这就是量子计算机“猜”的能力的由来。 在解决实际问题上，量子计算机能够在很短的时间内解决普通计算机需要几十年甚至上亿年才能解决的问题，比如说上文提到的RSA密码系统的基础：大数分解。现在最好的大数分解的经典算法分解一个数所需要的时间是跟这个数的长度成指数关系的，这就意味着算法所需的时间会随着待分解数的增长而迅速变大。但是量子计算机可以在很短的时间内完成这个问题。如果一个数长度为n的话，它分解这个数所需要的时间与(n^2)*(lgn)*(lglgn)成正比，而这个函数增长的速度远远小于指数函数。这个算法就是1995年贝尔实验室的Shor提出的Shor算法。这个算法带来的影响就是，实用的量子计算机一旦出现，世界上现有的最安全的密码系统RSA就会在顷刻间土崩瓦解。另外一个让密码学家心寒的量子算法就是Grover算法。这个算法可以在O(sqrt(n))的时间内完成对规模为n的任意数据库的搜索。密码分析家应用这个量子算法可以设计出在短时间内破解一系列的广泛应用功的经典密码的算法，其中包括DES。所以一旦实用的量子计算机出现之后，人们想要保护自己的隐私就必须依靠量子密码和一次性便笺这些工具了。 不过也不用担心，实用的量子计算机实际上是很难建造的，这里边有技术上的因素。在量子计算机的运算过程中，qubit是同时处于|0>和|1>的叠加态中的。但是这种叠加态在现实中很不稳定，一点小小的热涨落就会使这些叠加态退相干变回经典的非|0>即|1>的状态，这样的话如果在运算过程中qubit退相干的话，整个计算就会失败，给出一些错误的结果。就是由于量子叠加态的不稳定性，尽管量子计算机的理论基础已经比较成熟，真正实用意义上的量子计算机还没有建造出来。 当然，研究人员现在正在不停地探索建造量子计算机的技术。技术的关键就在于长期保持量子的叠加态还有操控这些叠加态。现在在发展的技术包括量子点、超导量子、量子拓扑、绝热量子计算等等。而现在经过不断的研究，全世界第一台商用量子计算机已经闪亮登场。它就是美国D-Wave公司的Orion。它拥有16个qubit，运行在由超导材料铌制成的芯片上。这台计算机可以进行大数分解，也可以解数独，因为像数独这样的组合优化问题正是量子计算机的强项。 当然啦，量子计算机由于技术上的限制，在一段时间内恐怕没有办法“飞入寻常百姓家”。但是它的兄弟光子计算机就没那么遥远了。 光子计算机，顾名思义就是利用光子来进行计算的计算机。传统的计算机是通过电子的流动来进行计算的，这样有几个不好的地方。第一是发热，现在已经有人实验用CPU煮面了；第二是由于工艺的限制，电路只能是二维的，复杂度上不去；第三是电磁的各种干扰的问题。光子计算机就能解决这些问题。光子计算机由于利用光子进行计算，发热量和能量消耗都很少；而由于光子传播是互相独立互不影响的，光路可以是三维的，这样的话就可以大大提高空间利用率和线路复杂度，为更复杂更强大的计算机铺平了道路。 光子计算机也有不同的种类。有直接处理光学图像的模拟式光子计算机，现在已经被用于卫星图片处理还有模式识别等方面；也有根据现代计算机基本结构设计的光子计算机，贝尔实验室就设计制造过世界上第一台光子计算机，运算速度达到每秒十亿次；还有光学神经网络，为模拟人脑提供了一条新的道路；最后还有将量子因素引入光子计算机，实现强大的量子计算。 但是光子计算机也有一些技术上的问题。首先就是光子计算机的其中一个优点其实也是缺点。光子在传播当中互不干扰，但是如果要用光子进行计算的话就需要光子和光子之间发生相互作用，这就需要特殊的光学元件。但是这样的光学元件构造并不简单，很不利于小型化。现在研究人员主要工作的重点就在于光学元件的微型化。贝尔实验室的光子计算机就是用砷化镓光学开关制成的。不过随着研究人员不断开发出各种各样的微型光学元件，这些技术问题正在不断被克服。 光子计算机之所以有这么强的计算能力，都归功于光的神奇特性。光既是粒子，又是波，能像粒子一样传播，又像波一样互不干扰。对我们来说，光的波动性更加神秘。下面我们就来看一看光的波动性导致的光的一个奇特现象：衍射。 终点：波的分身术光的衍射是由17世纪的物理学家格里马蒂（Grimaldi）发现的。他在做实验的时候发现当光通过小圆孔之后在墙上投影的光斑并没有明确的边沿，这与当时盛行的光的微粒说相矛盾。后来这个现象被惠更斯用光的波动说推导出来的惠更斯原理顺利解释。后人又发展了衍射的完整理论。其实衍射这种光学现象在日常生活中并不少见。日华月华还有峨嵋佛光都是衍射造成的。 衍射的实质就是光由于它的波动性，可以绕过一些小障碍物继续传播，遇上小缝隙的时候也可以透过小缝隙继续传播。这里的“小”的定义是与光的波长至少处于同一个数量级。我们在平时很少看到光的衍射现象是因为光的波长很小，大约在几百纳米左右，而我们日常生活中接触的东西很少有这么小的。头发丝和面纱可能勉强可以做到这一点。 事实上，我们观察到的衍射现象大多是光经过衍射之后重新汇集起来所出现的干涉图案，比如说著名的双缝干涉实际上就是光衍射通过两个小缝之后重新汇聚起来得到的干涉图案。衍射和干涉这两者结合起来可以带给我们一些意想不到的惊喜。 大家应该都听说本生和基尔霍夫发明的本生灯和分光镜这两件给化学分析立下汗马功劳的仪器的故事吧。分光镜中的核心元件是一个棱镜，正是这个棱镜将入射光分成一整个光谱的。但是，由于棱镜的制作工艺限制，它的精确度很难提高。这时候，颜色光栅就派上了用场。衍射光栅是一种由密集的等间距的平行刻线构成的光学元件，这就相当于很多个小缝。通过衍射和干涉的效应，它可以将某种特定波长的光的大部分按照同一角度反射，精确度很高，所以尽管它的制作工艺很复杂，衍射光栅仍然被广泛应用在各种光谱仪器当中。 由于光在传播中遇到障碍物和遇到小缝的衍射行为是不一样的，所以光在通过某个光栅之后形成的干涉图样其实携带了这个光栅的所有信息。这个原理有两个方面的应用。第一个是制造特定的干涉图样。通过傅立叶分析，我们可以从干涉图样反推出衍射光栅的具体构型。这项技术已经被广泛应用于激光防伪技术之中。大家上街去买张CD的话，通常盒子上都会有一个小小的激光防伪标签，其实这些标签上有很多微小的衍射结构，正是这些衍射结构把反射光变成精巧的防伪图案的。 另一个方面的应用就是通过干涉图样推测衍射光栅的结构，这也就是X射线衍射分析的原理。在1912年，德国的物理学家劳厄（Laue）就已经预见到了这种分析技术。X射线是一种波长很短的电磁波，它的波长跟原子的尺度在数量级上差不多。这样的话，由于晶体表面原子和分子排布十分整齐，对于X射线来说正好是一个非常合适的光栅。这样的话，通过分析特定波长的X射线在晶体表面衍射之后得到的干涉图象，我们就能推测出晶体表面原子和分子的排布，从而得知晶体的结构。这就使X射线衍射分析。 首先探索这项技术的是英国物理学家布拉格父子（Bragg）。他们在劳厄提出这个想法的第二年就利用了这个方法测定了氯化钠等晶体的结构，而且还得出了在X射线衍射分析中十分有用的布拉格公式。这项成果使他们登上了1915年诺贝尔奖的领奖台。后来这项技术就被广泛应用在晶体结构的测定上，比如说各种蛋白质的结构测定。值得一提的是，也正是X射线衍射最终证实了克拉克（Crick）和沃森（Watson）的DNA双螺旋结构模型，推动了各种对DNA的应用，比如说生物学家和侦探使用的DNA比对技术。而他们也因为这个发现获得了1962年的诺贝尔生理学和医学奖。 科技的发展是永无止境的，各种不同的方法可能在各种不同的领域中有出乎意料的作用。比如说光的衍射在光子计算机和DNA的结构测定中都有用，而引入量子计算的光子计算机还有DNA比对又在侦探这个属于福尔摩斯的行当中大有用武之地，量子计算可以破解罪犯的加密文件，而DNA比对又可以成为指证罪犯的强而有力的证据。现代可以正在不断飞速向前发展，它必将给我们带来更多的方便和安全。 后记：写了两天，终于写完了，一共23KB左右。途中还被fold.it这个有趣的游戏耗了不少时间。其实我还是不大满意，感觉这篇文章知识性还是不太强，很多东西都是大家耳熟能详的东西。不过这次是命题作文，所以也没啥办法。希望下一次能够好些~~~ 附pchu同一题目文章：从福尔摩斯到衍射现象 05 mei 非线性、自组织及其它（补）：一点补充和说明补注：本系列文章遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！ 稍微查了查，这个应该是我第四个科普类型的文章。第一个是《星空中的传说》（中医杂谈不算数，那是吵架，hoho~~~)，是基本上按照小学时候看的一本书写的，后来pchu拿去增添了一些内容改了一些结构形成了pchu版的《星空中的传说》，比我的版本要好不少。第二个就是《浅谈AI》。这个实际上写作过程有点变态，就是上一年的差不多这个时候，我们一班预科班的人在上海，而又遇上了五一假期，很多人都去了旅游，包括pchu，于是我就把他的电脑借过来，用了两天一夜左右的时候敲出来《浅谈AI》的。当时没有草稿，没有提纲，就是凭着自己的记忆和感觉在那里狂敲，最后敲出来20KB大约一万字的文章，那时候连自己都觉得惊讶，虽然说后来检查的时候发现了一个错误，但是既然没人提起那就算了。第三个就是来法国后写的《来自天书的证明》这个系列，这个没啥难度，抄书就行了，就是有个地方补了个证明而已，这个证明也有叙述上的不妥，不过没人提起也就继续算了。第四个就是现在这个系列《非线性、自组织及其它》了。本来这个系列是希望向《浅谈AI》看齐的，所以也采用了相似的“裸写”模式，也是两天的时间。但是很显然，由于我对这个领域的了解实在不够，所以写得很生硬晦涩，不像是科普。上篇中篇尤其是这样，下篇由于了解比较深入（算法嘛~~~），所以写得相对也比较好一些。 而且我发现好像看我的文章的人很少做什么评价（众：本来就没多少人愿意看你的东西……），所以希望大家看了这个系列之后说一点评价，让我以后想办法改进，谢谢！ 在这里再补充一点。在今天下午Sec俊审阅了这个系列的上篇之后，要去了那个程序的源代码。经过Sec俊对元胞邻域的修改，再加上我对配色方案的修改，我们得到了一个更有化学反应韵味的程序。以下是两次不同试验的截图：
在这里再次大力感谢Sec俊的贡献！ over. 睡觉去了~~~ 文章链接： 非线性、自组织及其它（上）：从化学振荡说开去 |
| A | BrO3- |
| B | CH2(COOH)2 |
| P | HOBr |
| X | HBrO2 |
| Y | Br- |
| Z | Ce(4+) |
我们注意到，这里只有一个元反应是自催化的，也就是第二个反应。在这里，f是一个可以调节的参数，因为最后一个反应是多个反应的混合总效果。
自催化除了可以产生振荡以外，通过与扩散现象结合还可以产生在空间中的周期性分布。这种周期性分布首先由英国数学家图灵提出。图灵是通过对带有扩散项的自催化反应微分方程的研究发现这种周期性解的。这种周期性结构不仅在化学反应中能够看到，而且也能在生物界里边被发现。为了纪念这位科学家，这种结构后来被称为图灵结构，正如同为他提出的图灵机一样。图灵结构可以是动态的也可以是静态的。比如说在一层极薄的液面中发生的BZ反应就会有不断运动扩散的水波状的结构（这里有一个Youtube视频），这种在化学中特别的结构也被称为化学波。当然，我们也有很多办法可以模拟这种化学波，比如说用数值模拟的方法。有趣的是，我们也可以通过元胞自动机来模拟这种波动结构。只需要不多的几段代码就可以实现类似的结构。下面请看图：
这个小程序是我以前用vb写的。想要的读者可以自行向我索取，因为这里放不了。
从上面的图我们可以看出组织是怎么一步一步在混乱中发展的。
2007年的诺贝尔化学奖也是授予一项在二维表面上能产生化学波的反应的研究的，这里有比较详细的相关资料。
回到图灵结构。图灵结构也可以是完全不动的。这也是图灵当初发现的那个稳定解的情况。
化学波可以用来解释一个有趣的生物学现象：如果研究动物身上的条纹的话，只有斑点身体条纹尾巴的动物，而从来不会有条纹身体斑点尾巴的动物（大家可以回忆一下小熊维尼历险记里边的跳跳虎）。这是为什么呢？原来，动物身上的条纹是由黑色素构成的，而黑色素的产生是服从某种现在未知的分子控制的，这种分子可以在动物细胞之间扩散，从而形成类似化学波的稳定图灵结构。动物的整个身体服从的图灵结构的规律都是一样的（尽管不同的物种和个体大小会影响这一规律），而半径越小，斑点越容易变成条纹。动物尾巴显然比身体要细，所以条纹身体斑点尾巴的动物是不存在的。同理可以推出，蛇很少有斑点的图案，更可能有的是覆盖身体的横条纹。
简单的化学方程竟然可以在热力学第二定律阴影覆盖下的混乱区域创造出有序的结构，而且这种现象是这么的普遍，到底它背后隐藏着什么呢？
文章链接：
非线性、自组织及其它（上）：从化学振荡说开去
非线性、自组织及其它（中）：远离平衡的结构
非线性、自组织及其它（下）：群体的力量
非线性、自组织及其它（补）：一点补充和说明
|
|
