第一部分 背景和历史 第1章~第7章

术语卡

• 术语：奥卡姆剃刀（Occam's Razor）
• 印象：entia non sunt multiplicanda praeter necessitatem（如无必要勿增实体）。意思是简约之法则，是由14世纪逻辑学家、圣方济各会修士奥卡姆的威廉（William of Occam，约1287年至1347年，奥卡姆（Ockham）位于英格兰的萨里郡）提出的一个解决问题的法则，他在《箴言书注》2卷15题说“切勿浪费较多东西，去做‘用较少的东西，同样可以做好的事情’。”换一种说法，如果关于同一个问题有许多种理论，每一种都能作出同样准确的预言，那么应该挑选其中使用假定最少的。尽管越复杂的方法通常能作出越好的预言，但是在不考虑预言能力（即结果大致相同）的情况下，假设越少越好。
• 出处：维基百科

人名卡

• 人名：梅拉妮·米歇尔（Melanie Mitchell）
• 印象：Melanie Mitchell is a professor of computer science at Portland State University. She has worked at the Santa Fe Institute and Los Alamos National Laboratory. Her major work has been in the areas of analogical reasoning, Complex Systems, genetic algorithms and cellular automata, and her publications in those fields are frequently cited.[1]
  She received her PhD in 1990 from the University of Michigan under Douglas Hofstadter and John Holland, for which she developed the Copycat cognitive architecture. She is the author of "Analogy-Making as Perception", essentially a book about Copycat. She has also critiqued Stephen Wolfram's A New Kind of Science[2]
  and showed that genetic algorithms could find better solutions to the majority problem for one-dimensional cellular automata. She is the author of An Introduction to Genetic Algorithms, a widely known introductory book published by MIT Press in 1996. She is also author of Complexity: A Guided Tour (Oxford University Press, 2009), which won the 2010 Phi Beta Kappa Science Book Award.
  梅拉妮·米歇尔（Melanie Mitchell）是波特兰州立大学计算机科学教授。她曾在圣菲研究所和洛斯阿拉莫斯国家实验室工作。她的主要工作是在类比推理，复杂系统，遗传算法和细胞自动机等领域，她在这些领域的出版物经常被引用[1]她于1990年从密西根大学道格拉斯·侯世达（Douglas Hofstadter）和约翰·H·霍兰（John Holland）获得博士学位，她发展了Copycat cognitive architecture。她是“Analogy-Making as Perception”的作者，本质上是一本关于“COPYCAT”的书。她还批评了斯蒂芬·沃尔夫拉姆的“A New kind of Science”一种新科学，并表明遗传算法可以为一维细胞自动机的多数问题找到更好的解决方案。她是遗传算法简介的作者，1996年由麻省理工学院出版社出版的一本广为人知的入门书。她还是Complexity: A Guided Tour复杂性导论（牛津大学出版社，2009年）的作者，获得了2010年菲贝卡“Phi Beta Kappa”奖。
• 出处：维基百科Melanie Mitchell

• 人名：冯·诺依曼 德语：John von Neumann （1903年12月28日－1957年2月8日）
• 印象：是出生于匈牙利的美国籍犹太人数学家，现代计算机与博弈论的重要创始人，在泛函、遍历论、几何、拓扑和数值分析等众多数学领域及计算机学、量子力学和经济学中都有重大贡献。
  冯·诺伊曼从小就以过人的智力与记忆力而闻名。冯·诺伊曼一生中发表了大约150篇论文，其中有60篇纯数学论文，20篇物理学以及60篇应用数学论文。他最后的作品是一个在医院未完成的手稿，后来以书名《计算机与人脑》发布，表现了他生命最后时光的兴趣方向。
  1926年，冯·诺伊曼以22岁的年龄获得了布达佩斯大学数学博士学位，相继在柏林大学和汉堡大学担任数学讲师。
  1930年，冯·诺伊曼接受了普林斯顿大学客座教授的职位。初到美国时，他在纽约对当地居民表演过默记电话簿的惊人记忆力。1931年，冯·诺伊曼成为普林斯顿大学终身教授。1933年转入普林斯顿高等研究院，与爱因斯坦等人成为该院最初的四位教授之一，不须上课。这一年，他部分解决了希尔伯特第五问题，证明了局部欧几里得紧群是李群。1937年成为美国公民，1938年获博修奖。
  1954年，冯·诺伊曼任美国原子能委员会委员。1954年夏天，右肩受伤，手术时发现患有骨癌，治疗期间，依然参加每周三次的原子能委员会会议，甚至美国国防部长，陆、海、空三军参谋长聚集在病房开会。晚年，有学生请教他做事的方法，他说：“简单（simple）。”
• 著作:
  -1923. 《关于超限数的引入》(On the introduction of transfinite numbers), 346–54.
  -1925. 《集合论的一种公理化》(An axiomatization of set theory), 393–413.
  -1932. 《量子力学的数学基础》(Mathematical Foundations of Quantum Mechanics), Beyer, R. T., trans., Princeton Univ. Press. 1996 edition: ISBN 978-0-691-02893-4.
  -1944. 《博弈论与经济行为》(Theory of Games and Economic Behavior), with Morgenstern, O., Princeton Univ. Press, online at archive.org. 2007 edition: ISBN 978-0-691-13061-3.
  -1945. 《就EDVAC的报告的首份手稿》(First Draft of a Report on the EDVAC) TheFirstDraft.pdf.
  -1963. 《冯诺依曼作品选集》(Collected Works of John von Neumann), Taub, A. H., ed., Pergamon Press. ISBN 978-0-08-009566-0.
  -1966. 《自复制自动机理论》(Theory of Self-Reproducing Automata), Burks, A. W., ed., University of Illinois Press. ISBN 978-0-598-37798-2.
  von Neumann, John. Continuous geometry. Princeton Landmarks in Mathematics. 普林斯顿大学出版社. 1998 [1960]. ISBN 978-0-691-05893-1. MR 0120174.
  von Neumann, John. Halperin, Israel, 编. Continuous geometries with a transition probability. Memoirs of the American Mathematical Society 34. 1981 [1937]. ISBN 9780821822524. MR 634656.
  -1958. 《计算机与人脑》(The Computer and the Brain, 去世后出版)
• 参考：维基百科

复杂系统的共性

• 个人一般都遵循相对简单的规则，不存在中央控制或者领导者。大量个体的集体行为产生出了复杂、不断变化而且难以预测的行为模式。
• 利用来自内部和外部环境中的信息和信号，同时也产生信息和信号。
• 可以通过学习和进化过程进行适应，即改变自身的行为以增加生存或成功的机会。
  总结：复杂系统由大量组分组成的网络，不存在中央控制，通过简单运作规则产生出复杂的集体行为和复杂的信息处理，并通过学习和进化产生适应性。
  《复杂》第1章 P14

牛顿三大定律

• 任何情况下，一切物体在不受外力作用时，总保持静止或匀速直线运动状态。
• 物体的加速度与物体的质量成反比。
• 两个物体之间的作用力和反作用力，在同一条直线上，大小相等，方向相反。

逻辑斯蒂映射（Logistic map）

x_t+1=Rx_t(1-x_t)
R=出生率和死亡率的效应
x=种群规模的“承载率”， x的初始值x₀介于0和1之间。
R固定不变，x_t迭代后会趋于一定数值。
R=2, x_t=0.5。“不动点”
R=2.5, x_t=0.6。“不动点”
R=3.1, x_t在2个值0.5580141和0.7645665之间振荡。“吸引子”
R=3.49, x_t在4个值0.872,0.389,0.829和0.494之间振荡。R介于3.4~3.5,振荡周期从2增加到4
R介于3.54~3.55,振荡周期增加到8
R介于3.564~3.565,振荡周期增加到16
R介于3.5687~3.5688,振荡周期增加到32
R约等于3.569946时，周期已趋于无穷大。
R等于大于3.569946时，x的值不再进入振荡，它们会变成混沌。
将x₀，x₁，x₂···的值组成的序列称为x的轨迹逐渐发散开，轨道极为敏感地依赖于x₀
逻辑斯蒂映射极为简单，并且完全是确定性：每个x_t值都有且仅有一个映射值x_t+1。然而得到的混沌轨道非常随机。因此，表面上的随机可以来自非常简单的确定性系统。
对于任何能产生混沌的R值，只要x₀有不确定性，不管精确到小数点后多少位，最终都会在t大于某个值时变得无法预测。
总结：数学生物学家梅对这些惊人的特性进行了总结

• 明显的不稳定波动不一定表明环境的变化莫测或是采样有错误；
• 在混沌钟，不管初始条件有多接近，在足够长的时间之后，它们的轨道还是会相互分开，意味着即使我们的模型很简单，所有的参数也都完全确定，长期预测也仍然是不可能的。
• 参考：《复杂》2011， P33-41

费根鲍姆常数

• 物理学家费根鲍姆的发现让倍周期之路得以在数学界闻名。
• R值，表示指倍周期分叉点的数值
  R₁≈3.0 ======> 周期2¹=2
  R₂≈3.44949 ======> 周期2²=4
  R₃≈3.54409 ======> 周期2³=8
  R₄≈3.564407 ======> 周期2⁴=16
  R₅≈3.568759 ======> 周期2⁵=32
  R₆≈3.569692 ======> 周期2⁶=64
  R₇≈3.569891 ======> 周期2⁷=128
  R₈≈3.569934 ======> 周期2⁸=256
  ······
  R_∞≈3.469946
• 随着周期增大，R值之间的距离越来越近。即R值增大，分叉之间的间隔越来越短。费根鲍姆计算了R值的收敛速度，约等于常数4.6692016。新的周期倍增比前面的周期倍增出现的速度快大约4.6692016倍。

• 他的理论在多个物理动力系统的实验中得到了证实，包括流体、电路、激光和化学反应。在这些系统中都发现了倍周器分叉，在这些实验中很难准确测量分叉点R值，实验得到的费根鲍姆常数也仍然界在接近4.6692016的误差范围之内。

  
  
  image.png

混沌系统

• 对于其初始位置和动量的测量如果有极其微小的不精确，也会导致对其的长期预测产生巨大的误差。即“对初始条件的敏感依赖性”
• 例子：即使很简单的计算机气象模型，也会有对初始条件的敏感依赖性，虽然有高度复杂的气象计算模型，天气预报也最多只能做到大致准确预测一个星期。
• 提出：物理学家李天岩（T.Y.Li）和约克（James Yorke）。
• 普适性，“混沌中的秩序”
  • 突然的周期倍增被称为分叉（bifurcation）。不断分叉直至混沌的过程就是 “通往混沌的倍周期之路”。
  • 费根保姆常数：新的周期倍增比前面的周期倍增出现的速度快大约4.6692016倍。

热力学定律

• 印象：是研究热现象中物态转变和能量转换规律的学科；它着重研究物质的平衡状态以及与准平衡态的物理、化学过程。热力学定义许多宏观的变数（像温度、内能、熵、压强等），描述各变数之间的关系。热力学描述数量非常多的微观粒子的平均行为，其定律可以用统计力学推导而得。
• 热力学第零定律：在不受外界影响的情况下，只要A和B同时与C处于热平衡，即使A和B没有热接触，他们仍然处于热平衡状态。这个定律说明，互相处于热平衡的物体之间必然具有相等的温度。

• 热力学第一定律：能量守恒定律对非孤立系统的扩展。此时能量可以以功W或热量Q的形式传入或传出系统。热力学第一定律表达式为：
  

• 热力学第二定律：孤立系统熵（失序）不会减少──简言之，热不能自发的从冷处转到热处，而不引起其他变化。任何高温的物体在不受热的情况下，都会逐渐冷却。这条定律说明第二类永动机不可能制造成功。热力学第二定律也可表示为熵增原理：
  
• 热力学第三定律：完整晶体于绝对温度零度时（即摄氏-273.15度），熵增为零。
• 总结：热力学第零定律定义了温度这一物理量，指出了相互接触的两个系统，热流的方向。热力学第一定律指出内能这一物理量的存在，并且与系统整体运动的动能和系统与环境相互作用的势能是不同的，区分出热与功的转换。热力学第二定律涉及的物理量是温度和熵。熵是研究不可逆过程引入的物理量，表征系统通过热力学过程向外界最多可以做多少热力学功。热力学第三定律认为，不可能透过有限过程使系统冷却到绝对零度。
• 了解基本定律时，要注意前提条件，针对什么“系统”，要明白“封闭系统”“孤立系统”“开放系统”的区别。在“封闭系统”，第一定律就是能力守恒，第二定律就是熵总是不断增加直至最大。
• 参考：维基百科

熵

• 化学及热力学中所指的熵（英语：Entropy），是一种测量在动力学方面不能做功的能量总数。（对不能转化成功的能量的度量）。也就是当总体的熵增加，其做功能力也下降，熵的量度正是能量退化的指标。熵亦被用于计算一个系统中的失序现象，也就是计算该系统混乱的程度。熵是一个描述系统状态的函数，但是经常用熵的参考值和变化量进行分析比较，它在控制论、概率论、数论、天体物理、生命科学等领域都有重要应用，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。
• 这个熵的概念最初是由克劳修斯（Rudolph Clausius）于1865年定义。
• 1877年，玻尔兹曼发现单一系统中的熵跟构成热力学性质的微观状态数量相关。在宏观尺度上的属性（例如热）是由微观属性产生（例如无数分子的运动。）可以考虑情况如：一个容器内的理想气体。微观状态可以以每个组成的原子的位置及动量予以表达。为了一致性起见，我们只需考虑包含以下条件的微观状态：（i）所有粒子的位置皆在容器的体积范围内；（ii）所有原子的动能总和等于该气体的总能量值。玻尔兹曼并假设：S=klogW, S是熵，W是对应给定宏观态的可能的微观态的数量（这个被称为玻尔兹曼原理的假定是统计力学的基础。统计力学则以构成部分的统计行为来描述热力学系统。），k是“玻尔兹曼常数”，这个数用来将熵变成标准单位。玻尔兹曼原理指出系统中的微观特性（W）与其热力学特性（S）的关系。
  根据玻尔兹曼的定义，熵是一则关于状态的函数。并且因为 W是一个自然数（1,2,3,...），熵必定是个非负数（这是对数的性质）。
• 参考：《复杂》2011 P52-64 中举例。维基百科熵

香农信息

• 香农的信息定义中有一个发送者向接收者发送信息，忽略信息的意义，只考虑发送者向接收者发送信息的速度。将宏观状态（发送者）的信息定义为可以由发送者发送的可能微观状态（可能信息的集合）的数量的函数。
• 香农用信息源的熵定义信息量（这个熵的概念通常被称为香农熵，以区别于玻尔兹曼给出的熵的定义）
• 信息量的定义为接收者在接收信息时体验到的“平均惊奇度”，其中“惊奇”意指接收者对于发送源将要传送的信息的“不确定度”。
• 信息可以是通信的任何单位，一个字母，一个词，一句话，甚至是一个比特（0或1），发送源的熵（信息量）用信息的可能性定义，而与信息的“意义”无关。

希尔伯特问题

• 德国数学大师希尔伯特(David Hilbert)于1900年在巴黎的国际数学家大会上提出来的，一共23个数学问题。1-6是数学基础问题，7-12是数论问题，13-18属于代数和几何问题，19-23属于数学分析。
• 其中第2个（算术公理之相容性）和第10个问题（不定方程可解性）后来影响最大。
• 这些问题可以分为三个部分
  • 数学是不是完备的？也就是说，是不是所有数学命题都可以用一组有限的公理证明或者证否。（被哥德尔解决）
  • 数学是不是一致的？是不是可以证明的都是真命题？（被哥德尔解决）
  • 是不是所有命题都是数学可判定的？是不是对所有命题都有明确程序（definite procedure）可以在有限时间内告诉我们命题是真是假？（被图灵解决）

哥德尔不完备性定理

• 从算术着手，他证明，如果算术是一致的的，那么在算术中就必然存在无法被证明的真命题，也就是说，算术是不完备的。而如果算术是不一致的，那么就会存在能被证明的假命题。
• 举例：命题A: 这个命题A是不可证的。假设命题A可证，即它说它不可证，即命题命题A为假。意味着证明了假命题，从而算术上不一致（类似1+1=3）。假设命题A不可证，就意味着命题A为真（因为它说它不可证），那就存在不可证的真命题，从而算术上不完备。
• 延伸：说谎者悖论：“我正在说谎”或者“我所说的皆为假”。如果他确实在说谎，那么他所说的就是真的，但如果他所说的就是真的，那么他就是在说谎。

图灵机和不可计算性

• 图灵机是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机
• 图灵机由三部分组成
  • 两头无限长的带子，被分成许多方格（或地址），符号可以被写入其中或从中读出。
  • 可移动的读写头，能从带子上读取符号或将符号写到带子上（改写）。在任何时候，读写头都处于一组状态中的一个。可以左右移动，
  • 指示读写头下一步如何做的一组规则，进入新状态。

进化论起源与发展

• 在西方，直到18世纪，都是神创造万物的思想。在古希腊和印度曾有些哲学家认为人类可能是从其他物种变化而来。
• 在18世纪中叶，法国动物学家布冯（George Louis Leclerc de buffon）出版了《自然历史学》(Historie Naturelle),书中描述了各种物种之间的相似之处。
• 查尔斯·达尔文的祖父厄拉斯莫斯·达尔文（Erasmus Darwin）认为所有物种都是由同一祖先进化而来。
• 法国贵族，也是植物学家拉马克在1809年出版的《动物哲学》（Philosophie Zoologique）提出：新的物种从非生命物质中自发产生，然后物种会通过“获得性状的遗传”不断进化。生物在生命过程中适应环境，而这种获得的适应性会直接遗传给后代。（20世纪初，拉马克的理论已没有影响）
• 1858年，达尔文收到英国另一位自然学家华莱士（Alfred Russell Wallace）的手稿，《论变种无限地偏离原始类型的倾向》（On the Tendency of Varieties to Depart Indefinitely from the Original Type）。
• 1858年夏在，达尔文和华莱士的合作成果在林奈学会宣读。
• 1859年底，达尔文出版了400多页的《物种起源》。
• 1865年孟德尔关于遗传率的豌豆实验论文《植物杂交实验》，直到1900年才被承认，推翻了当时盛行的“混合遗传”的观念-认为子代的性状会是父母性状的平均。
• 直到20世纪20年代，人们认识到达尔文与孟德尔的理论并不矛盾，而是互补的。
• 费希尔（Ronald Fisher）、霍尔丹(J.B.S.Haldane)和赖特(Sewall Wright)证明了达尔文与孟德尔的理论实际上是一致的，还提供了数学框架--群体遗传学（population genetics）。他们三位被认为是现代综合的奠基者。群体遗传学与达尔文理论和孟德尔遗传学共同形成了“现代综合The Modern Synthesis
• 20世纪60年和70年代，古生物学家古尔德（Stephen Jay Gould）和埃尔德雷奇（Niles Eldredge）对现代综合提出质疑和批评。认为现代综合的生物形态渐进论不符合实际的化石记录；认为历史偶然和生物约束的作用很重要；大尺度的进化现象无法用微观的基因变异过程和自然选择解释。
• 参考：《复杂》2011 P88-110

达尔文理论主要思想：

• 存在进化，所有物种都来自共同的祖先。生命的历史就是物种呈树状分化。
• 一旦生物的数量超过了资源的承载能力，生物个体就会为资源竞争，从而导致自然选择。
• 生物性状会遗传变异，变异在某种意义上是随机的-变异并不必然会增加适应性。能够适应当前环境的变异更有可能被选择，即更有可能存货，并将这新的性状遗传给后代，从而让后代中具有这种性状的个体增加。
• 进化是通过细微的有利变异不断累积逐渐形成的。

关于图灵机与判定问题的理解

• 前提，信息有双重属性，既能作为指令，又能作为数据（字符串）。
• 判定问题：是否有明确程序可以判定任意命题是否为真 （图灵证明这个假设有矛盾）
• 基于判定问题，给出图灵命题：图灵机M对于给定输入I会在有限步后停机。
• 设定存在一个有判定作用的图灵机H，对于任何给定的图灵机M（M是指令，它的表现形式也是字符串）和输入I（字符串），都能在有限时间内判断M对于输入I是会停机还是进入死循环，停不了机。字符串是0/1字集。判定器本身必须总是能停机的，无论无论M对于I会停机，还是不会停机，即输出字符串0就停机，或输出1就停机，记为H（M，I）。（只有第三种情况，停不了机，即无法判定，可以用来检查图灵机的死循环。）
• 以判定器为基础，把图灵机M也作为输入I，记为H' （M，M），就是说M又作为描述指令，又作为字符串（这个描述指令就是字符串）。类似于，一个统计字符数字的程序来统计该程序本身的字符数字。H'的含义就是判定M处理它自身的编码M时会不会停机。H'则只有当“M对于编码M不会停机”时才会停机，当“M对于编码M会停机”--H’就进入死循环，永不停机，即无法判定。
• 假设H'对于输入H‘不会停机。上一条说H'(M, M)时，当“M对于编码M会停机”--H’就进入死循环，永不停机；则H'对于输入M不能停机，意味着M对于输入M不会停机。则H'对于输入H'不会停机意味着H'对于输入H'会停机。（只是把M替换成H'的程序字符）只有在M对于M不会停机时H‘才会停机。又意味着H'对于H'不会停机，H'对于H’就会停机。前后产生悖论。
• 总结：如果存在一个算法可以判断任意一个图灵机在任意一个输入上是否停机，那么就可以设计这样一台图灵机：让它首先执行该算法判断自己在输入上是否停机。如果得出结论是停机，则让它进入一个死循环永不停机；如果结论是不停机，则让它立即停机。这样这台图灵机就在它停机的输入上不停机；在它不停机的输入上停机，产生悖论。结论只能是：不存在这样的算法。

金句卡
一切伟大的真理开始时都是大逆不道---萧伯纳（George Bernard Shaw）《安纳扬斯卡，布尔什维克女皇》