matrix 发表于 2008年6月13日 14时35分 星期五
来自五次方程式部门

密歇根大学计算机科学家开发的一款开源软件(中文)，能将寻找复杂方程式中对称的时间，从数日缩减为数秒。找寻对称是一种能突显通往答案捷径的方法。例如，验证火车时刻表的安全性、确认软件与硬件设计中的臭虫，或着加速一般搜寻任务。

名为saucy（卤莽）的软件由研究人员在2004年开发出来，它能加速基础计算机科学问题的解法，能迅速解答所谓的图自同构问题（graph automorphism problem）。当前软件升级增加了新算法，能更快的发现最短路径和对称。它将复杂方程式转换成图，并在顶点的排列中寻找相似性。在实验测试中，在不到0.5秒内，新软件在全世界路由器的网际网络连接图中捕捉到1083,687个不同的对称。图中的对称性意味着路由器可以被移来移去而不会改变（网络的）运作。在搜寻 Illinois州城市与乡镇之间公路网对称性的过程中，新的算法在0.5 秒内捕捉了104843个对称，而先前最强的演算法花了16分钟。

论文(PDF)

source: http://software.solidot.org/article.pl?sid=08/06/13/0641226

下载了论文来看~~~还是勉强看得明白的~~~算法的思路上还算自然~~~这个算法快的原因一个是面对稀疏图~~~这样的话同一个时间要考虑的结点数目就少了很多~~~另一个原因（据他们说是主要原因）就是观察到大多数图的自同构对称都只涉及到很少几个顶点~~~图的自同构对称置换可以构成一个置换群~~~称为Aut(G)~~~而他们观察到这个群可以由少数几个各自只涉及为数不多的顶点的置换生成出来~~~于是就有了他们的算法~~~

最近课上得差不多了~~~开始钻研图论~~~

source: http://science.solidot.org/article.pl?sid=08/06/06/062235

matrix 发表于 2008年6月06日 14时00分 星期五
来自上帝算法部门

3月份我们曾报道，Tomas Rokick正在开发一个非常高效的方法研究魔方最少的还原步骤，他证明任何魔方都可以在25步内还原。现在根据Tomas Rokick个人主页的更新，他宣布任意结构的魔方都可以在23步内解决。他之前进行运算的工作站为8G内存和1.6GHz Q6600 CPU，现在已经升级为一台超级计算机，索尼图形图像运作公司（Sony Pictures Imageworks）提供给他使用（当然是在电影制作空闲时间内）。在这个曾经制作了《蜘蛛侠3》和《冲浪企鹅》的工作室的帮助下，新的计算结果暗示任意结构的魔方可能的解决步数是21，22或23步。

果然是很好很强大~~~不知道极限是多少？~~~

Foldit是由Bakerlab所在的华盛顿大学的生物化学系和计算机工程系联合开发的一款在线游戏，旨在利用人的解题能力来帮助科学家寻找蛋白质在现实中的折叠结构。

这里有我做的两个介绍视频：

http://youtube.com/watch?v=UB3R5-NU5pc

http://youtube.com/watch?v=FOwrz1tmGXA

然后有中文讨论帖：

http://www.equn.com/forum/thread-18296-1-1.html

这个是我写的一个小小的经验之谈：

http://www.equn.com/forum/viewthread.php?tid=18296&page=2#pid244623

matrix 发表于 2008年5月24日 21时28分 星期六   来自冷静观察部门

冷核聚变（Cold Fusion）是指在接近常温常压和相对简单的设备条件下发生核聚变反应。多个轻原子核被强行聚合形成一个重原子核，并伴随能量释放。1989年3月23 日南安普敦大学的Martin Fleischmann和犹太大学的Stanley Pons宣称成功进行了冷核聚变实验，引起轰动，但其他科学家却无法重复该实验，美国能源部的调查报告认为实验不可信。之后从事冷核聚变的科学家都非常谨慎，前天(22日)日本大阪大学的荒田吉明（Yoshiaki Arata）教授和上海交大的张月昌（Yue Chang Zhang）教授向公众演示了冷核聚变实验，包括6家报纸和2家电视台在内的60余人在场观看了这次引入注目的实验。实验原理是基于他们曾经出版的论文（1，2），方法是用高压将氘气压入包含锆氧化物（ZrO2）和钯纳米粉末的真空单元内。实验产生了大量能源，并观察到氦-4（融合的信号）。这一演示证明这种方法是高度可重复的。

source: http://hardware.solidot.org/hardware/08/05/24/1314226.shtml

如果这是真的就好了~~~冷核聚变向来是人类的梦想~~~不用复杂的托卡马克装置也不用激光更不用维持一个等离子火球就可以享受聚变的能量~~~

不过由于以前的一些虚假实验，我们还是要比较小心~~~不要这么快庆祝~~~

最近四川地震，本来应该早一点写的，这两天只顾着关心新闻了。越看新闻，心情越沉重。天灾不可避免，地震不可预测。四川又是山地，震后气候条件又不好，这种情况下伤员的抢救就只能靠运气了。好在现在大部人马已经在深入灾区，情况开始稳定。现在我们也不能做什么了，只能希望抢救人员努力，大家有钱捐钱，没钱捐血，再不济像我这样的也要上网帮忙到处转贴情况，好让更多的人放心。

温总理已经到前线了，我真的很感动。照片照不出什么来，但是如果看那段流传的前线记者QQ记录的话，真的真的很感动，因为在抢救工作期间稳定灾民情绪是很重要的。

顺便BS一下那些粪青，没有科学常识就在骂地震局骂解放军，我以后见一个打一个毫不留手。

关于地震的科学常识的话可以看这里：http://songshuhui.net/archives/141

这里资料很齐全，而且不断有更新。

抢救地震伤员，祈愿天佑吾国。

注：本文遵守首页上的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同一题目文章：从福尔摩斯到衍射现象

补注：本系列文章遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！

稍微查了查，这个应该是我第四个科普类型的文章。第一个是《星空中的传说》（中医杂谈不算数，那是吵架，hoho~~~)，是基本上按照小学时候看的一本书写的，后来pchu拿去增添了一些内容改了一些结构形成了pchu版的《星空中的传说》，比我的版本要好不少。第二个就是《浅谈AI》。这个实际上写作过程有点变态，就是上一年的差不多这个时候，我们一班预科班的人在上海，而又遇上了五一假期，很多人都去了旅游，包括pchu，于是我就把他的电脑借过来，用了两天一夜左右的时候敲出来《浅谈AI》的。当时没有草稿，没有提纲，就是凭着自己的记忆和感觉在那里狂敲，最后敲出来20KB大约一万字的文章，那时候连自己都觉得惊讶，虽然说后来检查的时候发现了一个错误，但是既然没人提起那就算了。第三个就是来法国后写的《来自天书的证明》这个系列，这个没啥难度，抄书就行了，就是有个地方补了个证明而已，这个证明也有叙述上的不妥，不过没人提起也就继续算了。第四个就是现在这个系列《非线性、自组织及其它》了。本来这个系列是希望向《浅谈AI》看齐的，所以也采用了相似的“裸写”模式，也是两天的时间。但是很显然，由于我对这个领域的了解实在不够，所以写得很生硬晦涩，不像是科普。上篇中篇尤其是这样，下篇由于了解比较深入（算法嘛~~~），所以写得相对也比较好一些。

而且我发现好像看我的文章的人很少做什么评价（众：本来就没多少人愿意看你的东西……），所以希望大家看了这个系列之后说一点评价，让我以后想办法改进，谢谢！

在这里再补充一点。在今天下午Sec俊审阅了这个系列的上篇之后，要去了那个程序的源代码。经过Sec俊对元胞邻域的修改，再加上我对配色方案的修改，我们得到了一个更有化学反应韵味的程序。以下是两次不同试验的截图：

在这里再次大力感谢Sec俊的贡献！

over. 睡觉去了~~~

文章链接：

非线性、自组织及其它（上）：从化学振荡说开去
非线性、自组织及其它（中）：远离平衡的结构
非线性、自组织及其它（下）：群体的力量
非线性、自组织及其它（补）：一点补充和说明

注：本系列文章遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！

问大家一个很简单的问题：大家通常选择什么时候去饭堂吃饭？

通常来说，饭堂刚开门的时候人比较多，所以很多人都会稍微等一等，等到饭堂快关门人比较少的时候再去。可是，如果每个人都这样想的话，饭堂开门的时候就会一个人都没有，而快关门的时候就会有一大堆人涌过去。而如果大家又转念这么一想的话，情况又会倒过来，如此无穷无尽地循环。可是事实上，以上的两种极端情况都没有发生过，饭堂的人流量虽然有轻微波动但是还是相对平均的。这是为什么？

在这个饭堂的例子里边，可能有影响的因素比较多，比如说有人下课比较晚，有人不喜欢排队，有人爱吃热腾腾的饭菜，等等等等。那么，我们来看一个简化一点的例子。在一个小镇里边有一个小酒吧，镇里的人都喜欢晚上去喝一杯，顺便八卦一下小镇时事。但是这个小酒吧的确很小，能容纳的人数有限，如果所有想来喝两杯的人都来了的话酒吧就会异常拥挤。当然，没有人喜欢在太拥挤的酒吧里边喝酒。小酒吧老板也没有办法，买的地皮太小不能再扩建了。为了帮助大家决定来不来酒吧喝酒，老板每天都把昨天晚上来喝酒的人数写在镇里的公告栏，让每个人都能看得到。那么，一个自然的问题就是：如果你也是小镇居民中的一员，你会怎么决定今晚去不去喝一杯呢？

显然你不能知道今晚去的具体人数，你唯一能做的就是根据老板每天写出来的人数来估算今天晚上去的人数。估算方法是多种多样的。你可以多天取平均，或者取加权平均，甚至自己随便随机一个数出来。然后估算完毕之后，将得到的数据和酒吧容纳的人数作一个比较，如果你预计今晚去的人酒吧能容纳得下的话你就去，否则就不去。

同样，每个居民都会像你那样想，而每个人采取的估算方式可能会有很大的不同，比较极端的人甚至就会凭自己今天心情好不好来决定去不去。而大家的决定又影响了今晚酒吧的生意，进而影响明天的决定，然后就是明天晚上的生意，后天的决定，……如此重复，无穷无尽。晚上去酒吧的人数就通过这样的方式出现了自反馈。

初看起来，这样无序的管理似乎只能得到无序的结果，酒吧老板很可能今天门庭若市第二天一个人也没有。但是，经过计算机的模拟实验，我们发现尽管每天去酒吧的人数的确会有波动，但是它的长期平均值竟然越来越趋向于酒吧能容纳的人数，每天的波动也不会太极端，而且小镇人数越多效果越好。这就是自反馈的力量，它不需要明确地指示规则就可以达到想要的结果。

当然，这个例子其实也还不是很本质。你大可以说这本来就是一个方程，人数越多这个方程就越接近连续，那当然解就是一定的了。那么好，我们来看另一个例子：蚂蚁。

很多人小时候都喜欢看蚂蚁玩蚂蚁，那么大家应该会注意到，蚂蚁大队搬运食物的时候通常都是沿着一条最短的路径行走的。蚂蚁的视力根本没有可能看这么远，那么它们是怎么找到最短的路径的呢？美国物理学家费曼就曾经仔细地观察过这个过程。他发现，一开始第一只蚂蚁发现食物以后，回巢的路线并不是笔直的，而是歪歪斜斜的。后面接着的蚂蚁又不会完全按照前面的蚂蚁的路径走，有时候会误入歧途，但很多情况下反而会把原来的路修直。就这样，经过很多蚂蚁的不断调整之后，原来歪歪斜斜的路线就逐渐变得笔直起来了，就像我们不用尺子画直线一样，多画几次就变直了。那么，那些蚂蚁是怎么通过它们小小的神经系统做到这一点的呢？

蚂蚁在行走的时候会在路径上释放出信息素，而当找到食物的时候放出的信息素更有吸引力。蚂蚁行走的时候倾向于往信息素多的地方走（这里有一个自反馈的过程），但是偶尔也会犯错误。信息素在环境中会消散，所以越经常有蚂蚁往返的路径就会有越多蚂蚁去走，而越短的路径由于往返的时间短所以信息素浓度也会更高（这里是另一个自反馈的过程）。这样的话，蚂蚁就不断通过错误修正和自反馈的过程接近最优路径了。

这就是自反馈的威力。它可以把微小的优势放大，从而使蚂蚁这个整体自动在试错的过程中找到最好的路径，而不需要每个蚂蚁个体有复杂的行动规则。事实上，蚂蚁的这种觅食方式已经启发出了著名的蚁群算法。蚁群算法就是模拟蚂蚁的觅食方式和最优路径的搜寻方式来进行组合优化问题的解的搜索。蚁群算法模拟了遵循简单规律的个体（蚂蚁）在外环境（解空间）中寻找最优路径（最优解）的过程，而信息素则用在解空间中转移的概率类比。蚁群算法在很多组合优化问题中得到了很广泛的应用，最著名的一个例子就是旅行推销商问题（Travelling Salesman Problem，简称TSP）。尽管TSP问题是NP-完全的，在现在还没有找到得出最优解的多项式时间算法（科学界的主流意见是这种算法可能根本不存在），但蚁群算法可以在可以接受的时间内找出质量相当好的与最优解相差不大的解，所以蚁群算法是属于现在很受欢迎的近似算法之一，对其的研究也很热门。对于一个1992年提出的算法来说这实属不易。

类似的带有自反馈内容的近似算法还有和声搜索算法（Harmony Search）。和声搜索算法则是模拟人类合唱的时候找调子的过程。在合唱的时候，大家会先自己试着唱，然后根据集体的音调来调整自己的音调，最后达到所有人都一起唱同一个和音的结果。这里我们也看到了每个人音调的自反馈。和声搜索算法也是这样，先在解空间随机选择几个解向量作为初始值，然后根据这几个解向量用随机选取分量和生成分量的方法得到一个新的向量，最后，最差的向量会被舍去。如此循环往复更新向量库，最后和声搜索算法就能得到一个能接受的解。和声搜索算法是一个更新颖的算法，它的首次提出是在7年前的2001年，国内还没有这方面的报道，但是它已经在许多领域获得了不俗的成功，包括TPS、谱曲、解数独，还有一系列的实际问题。它的变种也是层出不穷。从这个算法我们也可以看出自反馈的力量。

跟自反馈密切相关的另一个现象就是自组织，也就是说一些个体按照一定的个体与个体之间的简单规律组合起来，最终在宏观上呈现出整体复杂规律的现象。在蚂蚁的例子中，蚂蚁正是通过个体与个体之间通过外界信息素的交流而在宏观上达到选取从巢到食物的最佳路径这一对于蚂蚁个体来说无法达到的目的的。而自组织的相关例子中，互联网恐怕是被人研究最多的。

互联网自从从CERN的工作网络演化为世界性的网络以来，就不断有科学家来研究它的结构，希望得到在互联网上行动的最好方法。长期以来科学家都是利用Erdos等提出的随机网络模型来研究互联网的结构的。这种随机网络有一个特征就是顶点的度符合泊松分布，只有几条边的点很少，而且几乎没有点可以链接很多边。但是，对互联网的实测表明，如果以网站为顶点的话，很多个人网站只有几个链接，而有些服务器可以有上百万的链接，这显然和随机网络的特点不一致。其实想一想就很容易明白这个道理。随机网络的边的建立是一瞬间完全随机地建立起来的，而互联网则是从CERN那个小小的工作网络逐渐扩张到现在的世界规模的。而在逐个结点添加的过程中，原本就比较多链接的网站就会更加受青睐，也会有更多的结点会添加向其的链接，而个人的小网站得不到什么关注的话可能永远就只能有几个链接了。就是这种链接的自反馈形成了互联网的这种“贫富分化”的现象。不单是互联网是这样，连普通人的交际网络也有这样的特点。这就给了公共卫生专家一个控制疫情的方法：当疫情发生时，重点对那些生活中会与很多人接触的人进行免疫。通过这样对图的“重量级结点”进行监控和免疫，疫情也会变得难于在人群中广泛传播。同样的道理也可以用到互联网上的病毒防治中。

我们甚至可以在生活中找到自组织的例子。厦门市民走上街头散步抗议某污染项目的上马就是一种市民通过社交网络自组织的现象。各种社交网站（比如说国外的facebook和国内的校内网）也都是通过社交网络自组织产生的结构。就更别说自然界食物链这种例子了。

其实生活中，非线性、自反馈、自组织都是无处不在的，它们对于我们对复杂世界的理解将会起到重要的作用。

文章链接：

非线性、自组织及其它（上）：从化学振荡说开去
非线性、自组织及其它（中）：远离平衡的结构
非线性、自组织及其它（下）：群体的力量
非线性、自组织及其它（补）：一点补充和说明

注：本系列文章遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！

注记：这一部分写得比较短，因为我没有很多的资料~~~

上篇我们留了一个很有趣的问题：既然热力学第二定律断言了一切事物都会归于混乱，那么为什么我们能从这么多的领域看到如此多的规律从混乱中创生出来？

其实仔细一想，这二者并没有矛盾。我们还是举化学振荡作为例子。首先，热力学第二定律针对的是一个封闭系统，而如果一个化学振荡反应是封闭的话，到最后它也会因为反应物的消耗而停止。只有开放的化学振荡反应可以通过不断添加反应物移出产物来维持振荡的持续，这样的系统就不是封闭系统，从而也不受热力学第二定律对于封闭系统的限制了。或者，我们也可以把反应物的添加看成负熵的流入，产物的移出看成熵的流出。正是这样的熵的流动维持了系统内的结构。其次，热力学第二定律只是断言事物会归于混乱，并没有说这个过程的速度。当然，在接近平衡的地方，系统很容易就会到达平衡，因为在接近平衡的地方本来就没多少发展的空间，无论是线性的过程还是非线性的过程。只有在远离平衡的地方，一个非线性系统才能有足够的时间去发展出结构。非线性的重要性在于不会使系统直接走向平衡。

下面我们举一个简单的例子来说明问题。

早在1900年，法国科学家贝纳德（Benard）就发现了一种对流的自组织现象。如果我们在一个水平金属圆盘里边放一薄层的液体，然后对金属圆盘均匀加热的话，一开始我们只能看到简单的热传导，但是在上表面和下表面的温差越过某一个临界点之后，液体就会开始对流，而且在表面会形成六边形的蜂窝结构。液体在六边形的中心下降（上升），在六边形的边沿上升（下降），就好像所有液体分子都在协同形成这样的比较规则的图案。

下面我们来分析一下这个系统。

这个系统很显然是开放的，外部有热量流入（加热的金属圆盘），当然也有向空气流出热量，这就首先保证了这个系统不会一下子归于混乱。如果我们将这个系统完全封闭起来的话，我们恐怕很快就会到达无序的平衡态。而如果我们不允许热量流出的话，对流也不会出现，系统仍然会归于无序。所以说，有流入有流出是这个系统产生规律图案的一个条件。也正是这样的热量流动使这个系统不会处于平衡态中。热量的流动导致了系统上下表面的温差，这也是对流产生的一个因素。

那么，为什么对流会在一个临界点处发生呢？如果我们看下表面的一个小液滴的话，在热传导的情况下它可以不动，但是由于它受热的话密度变小，如果向上移动了一点的话它就会继续向上移动，这就是一种形式的自反馈，也就是一种非线性的现象。当然，液滴的移动还取决于液体的粘滞度还有热传导的速度，而这两者恰恰抑制了对流的形成。所以只有当上表面和下表面的温度差达到了一定的程度，对流才会发生。而对流的图案也是容易理解的，这是各种不同对流方式的竞争造成的。最后得到的对流图案是所有可能性中能量最低的。

人们对于这种处于非平衡态的热力学的研究正在火热进行之中，因为对于这种不在平衡态中的系统演化过程的研究可以帮助我们理解许多事情，比如说生命这种结构是如何从无序之中演化出来，大自然中的各种规律又是如何演变的。而现在有一个研究的热点就是自反馈，因为自反馈必然带来非线性的因素，也会使整个系统的变化产生很多变数。

然而，自反馈并不是只在连续的系统当中存在。离散的复合系统也常常会有自反馈的登场，而伴随着自反馈的也有某种程度的规律，这就是一种自组织现象。而且这些现象已经在很多技术中得到了应用，特别是计算机技术。我们在下篇当中就会看到各种不同的例子。

文章链接：

非线性、自组织及其它（上）：从化学振荡说开去
非线性、自组织及其它（中）：远离平衡的结构
非线性、自组织及其它（下）：群体的力量
非线性、自组织及其它（补）：一点补充和说明

注：本系列文章遵守首页上的CC版权声明，转载请注明作者与出处，谢谢！

大家平时熟知的化学反应似乎都是“一步到位”的，也就是说好像立刻就可以反应完全。而在大学学化学的同学可能也会更经常接触到一些只能部分反应的化学反应。很多化学反应都是这样单向的，它们的反应程度依赖于平衡常数。这样的反应未免有些单调。但实际上，存在这样的化学反应，它的反应历程并不是“一帆风顺”的，要经历好几次振荡才能最后到达反应平衡。如果不断补充反应物除去产物的话，这个反应还可以不断振荡下去。这里有一个这类型反应的Youtube视频。

这样的反应在科学史上还是很新的。在不同相之间发生的化学振荡很早就有报道，但是在均一介质里边的化学振荡的例子就直到1950年才被Belousov发现，后来Zhabotinsky对这个反应进行了详细的研究。这就是著名的Belousov-Zhabotinsky反应，简称BZ反应。当初Belousov发现这个反应的时候，他写的关于这个反应的论文真是到处碰壁，因为当时科学界都认为由于热力学第二定律这样的反应是不可能的。后来反正不管怎么样，终于有一本杂志愿意发他的这篇论文，BZ反应从此才被世人知道。

关于BZ反应的历程的动力学模型，为科学界普遍接受的是所谓的FKN模型，这是由俄勒冈大学的Field, Koros, Noyes发现的。他们的模型包含18个元反应方程式，涉及21种不同的化学物质。下面是一个分阶段的简化版本：

• 起始
  Br- + BrO3- + 2H+  -->  HBrO2 + HOBr
  Br- + HOBr + H+  -->  Br2 + H2O
• HBrO2的自催化反应
  BrO3- + HBrO2 + H+  -->  2BrO2` + H2O
  BrO2` + Ce(3+) + H+  -->  Ce(4+) + HBrO2
  合起来就是：BrO3- + HBrO2 + 3H+ +2Ce(3+)  -->  2Ce(4+) + 2HBrO2 + H2O
  这里HBrO2在反应物和产物里边都出现了，而且在反应过程中增加了，这就是自催化的反应。
• HBrO2的消耗
  Br- + HBrO2 + H+  -->  2HOBr
  2HBrO2  -->  HOBr + BrO3- + H+
• 丙二酸的氧化
  Br2 + HOOC-CH2-COOH --> HOOC-CHBr-COOH + Br- + H+
  2Ce(4+) + 2HOOC-CHBr-COOH + HOOC-CH2-COOH + 3H2O  -->  2Br- +2Ce(3+) + 3HOOC-CHOH-COOH + 4H+

合起来的总反应方程式是：3HOOC-CH2-COOH + 4BrO3-  -->  4Br- + 9CO2 + 6H2O

这个反应的振荡可以很容易通过添加颜色指示剂观察出来。

这个反应有一个很特别的地方就是有HBrO2的自催化反应。当然，并不是每一个有自催化反应的化学反应都是振荡的，但是没有自催化反应的化学反应一定不是振荡的。自催化反应引入了自反馈的因素，所以才会产生振荡。下面我们通过两个数学模型来说明自催化的重要性。

Volterra模型本来是为了研究物种的相互作用而提出的。在自然界中，我们常常能看到两个有着捕食与被捕食关系的物种，而这些物种的种群大小经常呈此消彼长的周期性振荡变化。Volterra模型就是为了研究这样的现象而提出的。下面是一个化学反应的表达：

R+X -> 2X
X+Y -> 2Y
Y -> P

总的反应方程式就是 R -> P。注意这里的第一和第二个源反应是自催化反应。

如果我们假定R的浓度不变的话，我们可以得到这样的两个微分方程：

d[x]/dt = k1[R][X] - k2[X][Y]
d[Y]/dt = k2[X][Y] - k3[Y]

注意第二个微分方程。这个方程有两个平衡解，一个是k2[X] = k3，可以通过另一个微分方程得出[Y]的值；另一个是[Y] = 0，可以通过另一个微分方程得出 [X] = 0。

这就是自催化的重要之处：它提供了两个吸引子。如果只有一个稳定解的话，由热力学第二定律，封闭的化学反应不可避免的就会冲同一个方向掉进稳定的结果。现在有两个稳定解的话，化学反应的历程就可以在这两个解直接徘徊，就造成了振荡的效果。事实上，这两个方程有一个稳定的周期性解，也是一个吸引子。

第二个模型就是描述BZ反应的FKN模型，也叫俄勒冈模型(Oregonator)。这个模型将本来的18条方程式简化成了5条：

A + Y -> X + P
A + X -> 2X + 2Z
X + Y -> 2P
2X -> A + P
B + Z -> (f/2)Y

以下是其中字母对应的物质列表：