本文作者：方弦
计算无处不在。
走进一个机房，在服务器排成的一道道墙之间，听着风扇的鼓噪，似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘，到今天的计算机，我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多，甚至超越了它们的制造者。上个世纪末，深蓝凭借前所未有的搜索和判断棋局的能力，成为第一台战胜人类国际象棋世界冠军的计算机，但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识；而仅仅十余年后，Watson却已经能凭借自己的算法，先"理解"问题，然后有的放矢地在海量的数据库中寻找关联的答案。长此以往，工具将必在更多的方面超越它的制造者。而这一切，都来源于越来越精巧的计算。
计算似乎无所不能，宛如新的上帝。但即使是这位"上帝"，也逃不脱逻辑设定的界限。
第一位发现这一点的，便是图灵。
《计算的极限》系列
在现实中，证明某种东西不存在是非常困难的。要证明某种东西存在，只要举出一个例子就可以了；但要证明某种东西不存在，就要想办法排除所有的可能性，而在现实生活中，这几乎是不可能的。所以，只要能排除那些比较主要的可能性，任务就算完成。但在数学中，情况大不相同：通过形式逻辑的方法，我们可以确实地证明某种数学对象不存在。这都要归功于数学那彻底的抽象化和形式化。
数学家在证明某个数学对象不存在的时候，经常会来一招"欲擒故纵"：首先假设它存在，那么它必然具有某些特定的性质，再利用这些性质，用严密的逻辑推理引出一个不可能的结论。既然结论是不可能的，而逻辑推理又没有问题，那么一定是推理的出发点出了差错：作为推理基础的那个东西，其实并不存在。这种证明方法，就是反证法。
现在，我们尝试用反证法证明停机问题是不可计算的。
按照反证法的格式，我们先反其道而行之，假设停机问题是可以计算的。根据定义，这说明存在一台图灵机P，使得向它输入某个图灵机M的状态转移表编码，以及初始输入I，图灵机P就能在有限步运算内，判断出机器M在输入I上是否会停止。
接下来，我们将要用图灵机P构造一个逻辑上不可能存在的结构，这将是证明的关键。
我们来考虑一个新的图灵机R，它的输入是某个图灵机M的状态转移表编码<M>。图灵机R先"调用"图灵机P，判断图灵机M在初始输入<M>上是否会停止。用现代的计算机语言来说，就相当于调用函数P(<M>,<M>)。如果图灵机P得出的结论是机器M在输入<M>上会停止的话，图灵机R接下来就会进入死循环；否则，如果机器M在输入<M>上不会停机的话，图灵机R就停止。
图灵机R的构造有两个奇怪之处。
首先，在图灵机R的运作中，它尝试判断一台图灵机M在它自身的编码<M>上的运作情况。此时，图灵机M不仅是程序，同时也是数据。这提醒我们，其实程序和数据没有实质的区别。程序只是一种特殊的数据，能够被分析、整理、改写。
事实上，我们每天都在使用处理程序的程序。比如说杀毒软件，其实就是一种扫描程序的程序。它检查每个程序的内容，判断程序中有没有威胁计算机安全的恶意代码。用杀毒软件扫描它自身，实际上就是让这个程序运作在它自身的代码之上。我们也可以用记事本打开记事本的程序本身，或者用压缩软件打一个包含它程序本身的压缩包。这些例子都说明了一个道理：程序就是一种数据。正因为程序就是数据，我们才得以完成图灵机的自我指涉。
其次，在图灵机R的构造中，如果M在输入<M>上停机，那么R就不停机；如果M在输入<M>上不停机，那么R就停机。这就是说谎者悖论的翻版：它的行为要与自己的判断相悖。
这样，我们就凑齐了说谎者悖论的两个要素：自我指涉和自我否定。剩下的，就是如何将这两个要素组合在一起，引出不可调和的矛盾了。
为了引出矛盾，我们来考虑图灵机R在自己的编码<R>上的运行情况。
如果R在<R>上停机的话，R必定没有进入死循环。所以，在调用图灵机P时，得到的必然是"图灵机R在输入<R>上不会停机"，才能避免死循环。但图灵机P的这个结论不符合我们的假设，出现了逻辑矛盾，所以R不可能在<R>上停机。
如果R在<R>上不停机的话，因为图灵机P必定在有限时间内完成计算，所以R必定进入了死循环。而R进入死循环的先决条件是，在调用图灵机P时，得到的是"图灵机R在输入<R>上停机"。而图灵机P的这个结论，同样不符合我们的假设。由于同样的逻辑矛盾，R同样不可能在<R>上不停机。
所以，根据严密的逻辑，我们构造的图灵机R在自己的编码<R>上，既不可能停机又不可能不停机，这是不可能的。另一方面，我们的逻辑推理也是没有问题的。尽管多么不情愿，剩下的可能性只有一种：我们假设的那个能完美解决停机问题的图灵机P，根本不存在！也就是说，停机问题是不可计算的。。
【感谢neko（@iNEKO_mini）提供图片】
这个结论，我们称之为停机定理。以上的论述，作为停机定理的证明远远不算严谨，还有很多细枝末节需要填充。但这些细节都是技术性的，并不妨碍主要的思想：矛盾的自我指涉。
停机定理的证明，一如哥德尔不完备性定理的证明，核心是化了妆的说谎者悖论。图灵机的能力如此强大，一台通用图灵机就可以完成一切图灵机的工作，将所有图灵机作为数据处理。也正因如此，图灵机不能解决某些牵涉它自身的问题，否则总会存在一些自我否定的"说谎者"，利用能解决牵涉自身问题的那些图灵机，完成被逻辑所禁止的，致命的自我指涉。图灵机的能力，在必然的逻辑推演下，同时也成了它的枷锁。
实际上，图灵一开始并没有证明停机定理。他证明的是：不存在这样的程序，能判断任意图灵机是否会至少打印出一个1。这里的"1"可以换成任意的符号。这个证明的方法要稍复杂些，不过本质上仍然是通过自我否定与自我指涉来制造悖论。而事实上，许多（但不是所有）有关图灵机的问题，都能用同样的方法被证明是不可计算的。这样，图灵手上就握有一套不可计算的问题，可以开始进攻希尔伯特的问题。
我们回顾一下希尔伯特的问题。哥德尔证明了，所谓的"一阶谓词演算"是完备的。也就是说，在这个数学系统中，每个真理都能被证明，"真"和"能被证明"这两个概念是一致的。希尔伯特的可判定性问题是：是否存在一种计算过程，可以在有限步运算内，判断在这个完备的数学系统中每个命题的真假？
一阶谓词演算作为数学系统，在能力上实在是比不上数学家们常用的逻辑系统：它连自然数都不能很好地定义。但图灵发现，这个稍弱的数学系统已经足以表达图灵机的运行过程。对于每个图灵机M，通过巧妙然而机械化的操作，图灵都能构造出一阶谓词演算中的一个命题U(M)，使得U(M)成立当且仅当图灵机M会至少打印出一个1！也就是说，命题U(M)是否为真与图灵机M的运行过程息息相关。
剩下的证明就如同探囊取物了。如果希尔伯特的可判定性问题是可以计算的话，必定存在一台图灵机H，可以在有限时间内，判断每个命题的真假。对于一台图灵机M，我们要知道它是否会至少打印出一个1，可以先机械化地计算出与M有关的命题U(M)，然后用图灵机H去判断U(M)的真假，从而判断图灵机M是否会至少打印出一个1。也就是说，利用图灵机H，我们可以用计算回答一个不可计算的问题，而这是不可能的。所以，图灵机H并不存在，希尔伯特的可判定性问题的答案只有三个字：不可能。
希尔伯特的期望，又一次化为泡影。逻辑弄人。
图灵确信自己解决了希尔伯特的判定问题后，很快将他的想法写成了论文，它的题目是：
《论可计算数，及其在可判定性问题上的应用》（On Computable Numbers, With an Application to the Entscheidungsproblem）
他将论文交给了数理逻辑课的纽曼教授。这篇论文在纽曼教授的桌上放了几个星期。当教授终于有时间细读图灵的论文时，一开始根本不敢相信希尔伯特的问题竟然能通过对如此简单的机器的论证而解决，但无懈可击的逻辑论证最终战胜了怀疑。这无疑是划时代的工作，最终埋葬了希尔伯特的宏伟计划。
但正当纽曼教授联系各方，想办法发表图灵的论文时，从大西洋彼岸的普林斯顿，寄来了一篇论文：
《初等数论中的一个不可解问题》（An unsolvable problem of elementary number theory）
它的作者是丘奇（Alonzo Church），普林斯顿大学的一位年轻数学教授，当时在数理逻辑这一领域已经小有名气。而这篇文章的最后一句话是：
In particular, if the system of Principia Mathematica be ω-consistent, its Entscheidungsproblem is unsolvable.
（特别地，如果《数学原理》中的系统是ω-一致的话，它的可判定性问题是不可解的。）
对于图灵来说，这绝对不是一个好消息，因为这正是他的结果。
那么，丘奇又是如何得到这个结论的呢？
在物理学中，有一类特殊的实验：它们不需要购置昂贵的仪器，不需要大量的人力物力，需要的只是有逻辑的大脑；而这种实验却可以挑战前人的结论，建立新的理论，甚至引发人们对世界认识的重新思考。这种实验就是传说中的思想实验。历史上的许多伟大物理学家，都曾设计过发人深思的思想实验，伽利略、牛顿、爱因斯坦便是其中的代表，这些思想实验不仅对物理学的发展有着不可磨灭的作用，更是颠覆了人们对世界对宇宙的认识。这篇文章将从易到难地介绍一下物理学历史上的几个著名思想实验。
自从亚里士多德时代以来，人们一直以为力是运动的原因，没有力的作用物体的运动都会静止。直到伽利略提出了下面这一个家喻户晓的思想实验，人们才知道了惯性原理——一个不受任何外力(或者合外力为0)的物体将保持静止或匀速直线运动：
设想一个一个竖直放置的V字形光滑导轨，一个小球可以在上面无摩擦的滚动。让小球从左端往下滚动，小球将滚到右边的同样高度。如果降低右侧导轨的斜率，小球仍然将滚动到同样高度，此时小球在水平方向上将滚得更远。斜率越小，则小球为了滚到相同高度就必须滚得越远。此时再设想右侧导轨斜率不断降低以至于降为水平，则根据前面的经验，如果无摩擦力阻碍，小球将会一直滚动下去，保持匀速直线运动。
在任何实际的实验当中，因为摩擦力总是无法忽略，所以任何真实的实验都无法严格地证明惯性原理，这也正是古人没有得出惯性原理的原因。然而思想实验就可以做到，仅仅通过日常经验的延伸就可以让任何一个理性的人相信惯性原理的正确性，这一最简单的思想实验足以体现出思想实验的锋芒！
仍是受亚里士多德的影响，伽利略之前的人们以为越重的物体下落越快，而越轻的物体下落越慢。伽利略在比萨斜塔上的著名实验人尽皆知，可是很多人不知道的是，其实在这之前伽利略已经通过一个思想实验证明了两个小球必须同时落地：
如果亚里士多德的论断是对的话，那么不妨设想把一个重球和一个轻球绑在一起下落。由于重的落得快而轻的落得慢，轻球会拖拽住重球给它一个阻力让它减速，因此俩球的下落速度应该会介于重球和轻球下落速度之间。然而，如果把两个球看成一个整体，则总重量大于重球，它应当下落得比重球单独下落时更快的。于是这两个推论之间自相矛盾，亚里士多德的论断错误，两个小球必须同时落地。
有了上述思想实验，实际上两个小球同时落地就已经不仅是一个物理上成立的定律了，而是在逻辑上就必须如此。在这个例子中，思想实验起到了真实实验无法达到的作用：即便在我们高中所学的牛顿引力理论不适用的情形，两个小球同时落地依然是成立的！后面我会讲到广义相对论中的等效原理，这个思想实验在逻辑上的必然成立是爱因斯坦总结出等效原理的关键因素。
如图，一门架在高山上的大炮以很高的速度向外水平地发射炮弹，炮弹速度越快，就会落到越远的地方。一旦速度足够快，则炮弹就永远也不会落地，而是会绕着地球作周期性的运动。
牛顿的这一简单的思想实验，第一次让人们认识到，原来月球不会掉到地上来（也不会飞走）的原因，正是导致苹果落地的引力！牛顿的引力理论促成了人们认识上的一个飞跃：天上的东西并不"神圣"，他们遵循的规律和地上的普通物体完全一致。
用长绳吊一水桶，让它旋转至绳扭紧，然后将水注入，水与桶暂时都处于静止中，这时显然液面水平。再突然使桶反方向旋转，刚开始的时候水面并未跟随着运动，此时水面仍然水平。但是后来，桶逐渐把运动传递给水，使水也开始旋转，就可以看到水渐渐离开其中心而沿桶壁上升形成凹面。运动越快，水升的越高。倘若此时突然让桶静止，水由于惯性仍将旋转，此时的液面仍为凹面。牛顿认为，水面的下凹，不是由水对周围的相对运动造成的，而是由水的绝对的、真正的圆周运动造成的，因此由水面的下凹就可以判断绝对运动的存在。
这一思想实验，是牛顿为了论证绝对空间的存在而设计出来的。然而，众所周知，牛顿的绝对时空观其实是错误的，也就是说这一思想实验其实是个失败的例子。这一谬误，在100多年之后才被哲学家兼物理学家马赫所指出。马赫认为，水面的凹陷，并不是由于水相对于"绝对空间"的运动，而是由于相对宇宙间的所有其他物体的运动，这些其他所有物体通过引力对水施加了作用。其中起决定性作用的物体则是遥远的天体，正是遥远的天体的"参考系拖拽"作用使得相对于它们旋转的液面发生了凹陷。马赫认为并不存在绝对空间，所有参考系等价。倘若能够使水面保持静止，而让所有遥远天体一同旋转，按照马赫的观点，静止水面将产生凹液面。我们显然无法做这样的实验，但是如果用几公里厚的水桶做上面的水桶实验，则人们便不能肯定牛顿对液面的平凹的判断了。。后来，马赫的观点对爱因斯坦发明广义相对论产生了决定性的影响，马赫原理本身也随着广义相对论的逐渐证实而得到了广泛认可。
在20世纪的宇宙大爆炸理论提出之前，人们对于宇宙的认识是朴素的：宇宙无限大、存在的时间无限长、宇宙处于稳恒态、宇宙中的星体分布在大尺度上均匀。然而那时的人们不知道的是，从这四条基本假设却可以逻辑地推出与事实明显相悖的结论——奥伯斯佯谬：
如果宇宙是稳恒，无限大，时空平直的，其中均匀分布着同样的发光体，由于发光体的照度与距离的平方成反比，而一定距离上球壳内的发光体数目和距离的平方成正比，这样就使得对全部发光体的照度的积分不收敛，黑夜的天空应当是无限亮的。
然而每天的黑夜总是如期降临，天空并不是一直无限亮着。这就说明以前我们对宇宙的认识存在问题。奥伯斯本人给出了一个解释，他认为宇宙中存在的尘埃、不发光的星体吸收了一部分光线。然而这个解释是错误的，因为根据热力学第一定律，能量必定守恒，故此中间的阻隔物会变热而开始放出辐射，结果导致天上有均匀的辐射，温度应当等于发光体表面的温度，也即天空和星体一样亮，然而事实上没有观察到这种现象。直到宇宙大爆炸理论的提出，奥伯斯佯谬才迎刃而解。根据大爆炸理论，宇宙诞生于150亿年前的一个大爆炸，到现在宇宙仍处在膨胀的过程当中，因此，宇宙的存在时间便是有限的，并且并非处在稳恒态。四条基本假设的两条已经不再成立，因此奥伯斯佯谬也自然被瓦解。
牛顿之后的时代，经典力学在描述世界上产生了巨大的成功，人们逐渐的相信世界是可以用物理定律机械地描述的。比较极端地，拉普拉斯就相信机械决定论，认为世间万物（包括人类、社会）都逃不过确定的物理定律的掌控。
"我们可以把宇宙现在的状态视为其过去果以及未来的因。如果一个智能知道某一刻所有自然运动的力和所有自然构成的物件的位置，假如他也能够对这些数据进行分析，那宇宙里最大的物体到最小的粒子的运动都会包含在一条简单公式中。对于这智者来说没有事物会是含糊的，而未来只会像过去般出现在他面前。"——拉普拉斯
拉普拉斯提到的"智能"，便是后人所称的"拉普拉斯妖"。倘若拉普拉斯妖是存在的，那这个世界也太可怕了：你我的行为全部都可以通过计算得出，我们的命运也全都被物理定律+初始条件严格的定出了，没有什么会是计算之外的，那生活还有什么乐趣可言！幸运的是，混沌理论和量子力学的发展，让拉普拉斯妖永远也不可能存在了。量子力学告诉我们，物理量都是有不确定性的，不可能无误差地精确测量。而混沌理论则表明，只要涉及3个及更多的物体，初始条件的极其微小的差别将导致最后结果的千差万别。从另一个角度来说，拉普拉斯妖是基于经典力学可逆过程的，然而真实的系统确实满足热力学第二定律（熵增原理）的不可逆过程。因此世界仍是充满不确定性充满了惊喜的，人也可以凭借自己的主观努力去改变自己的命运。
中学时我们都曾学过热力学第二定律（熵增原理）：孤立系统的不可逆过程熵总是在增加。"落叶永离，覆水难收；欲死灰之复燃，艰乎其力；愿破镜之重圆，冀也无端；人生易老，返老还童只是幻想；生米煮成熟饭，无可挽回..."这些都是熵增原理在实际生活中的反应，它现在也已经成为了物理学中最牢不可破的原理之一。然而当年麦克斯韦却曾提出过一个对熵增原理的诘难，非常令人困惑：
一个绝热容器被分成相等的两格，中间是由"麦克斯韦妖"控制的一扇小"门"，容器中的空气分子作无规则热运动时会向门上撞击，"门"可以选择性的将速度较快的分子放入一格，而较慢的分子放入另一格，这样，其中的一格就会比另外一格温度高，系统的熵降低了。可以利用此温差，驱动热机做功，而这是与热力学第二定律相矛盾的。
对于这个诘难的反驳，可并不是一件轻松的事情。有人可能以为麦克斯韦妖在打开、关闭门的时候需要消耗能量，这里产生的熵增会抵消掉系统熵的降低。然而开关门消耗的能量却不是本质的，它可以任意降低到足够小。对于麦克斯韦妖的真正解释，直到20世纪才被揭开。关于熵的问题向来比较难懂，因此我直接引用赵凯华先生在《新概念力学·热学》中的话："麦克斯韦妖有获得和存储分子运动信息的能力，它靠信息来干预系统，使它逆着自然界的方向进行。按现代的观点，信息就是负熵，麦克斯韦妖将负熵输入给系统，降低了它的熵。那么，麦克斯韦妖怎样才能获得所需的信息呢？它必须有一个温度与环境不同的微型光源去照亮分子，这就需要耗费一定的能量，产生额外的熵。麦克斯韦妖正是以此为代价才获得了所需的信息（即负熵）的，这额外熵的产生补偿了系统里熵的减少。总起来说，即使真有麦克斯韦妖存在，它的工作方式也不违反热力学第二定律。"
爱因斯坦的狭义相对论建立了全新的时空观，对于当时的人们来说难以接受。因此自从提出以来，狭义相对论就受到了各种诘难，其中最著名的当属双生子佯谬。但是无论如何诘难，狭义相对论都可以很完美的给出解释，所有的佯谬都被一一化解，研究这些佯谬可以更加深刻的理解狭义相对论的时空观。
在狭义相对论中，运动的参考系时间会变缓，即所谓的动钟变慢效应。现在设想这样一个情景：有一对双胞胎A和B，A留在地球上，B乘坐接近光速的飞船向宇宙深处飞去。飞船在飞出一段距离之后掉头往回飞，最终降落回地球，两兄弟见面。现在问题来了：A认为B在运动的时候时间变慢，B应当比A年轻；而同样地，在B看来，是A一直在运动，是A的时间变慢了，A应当比B年轻才是。那么兄弟俩究竟谁更年轻呢？狭义相对论是否自相矛盾了？
事实上，理解双生子佯谬的关键，是要清楚A和B的地位并不对等：两人中只有B经历了加速过程，B在飞船掉头的时候不可避免的要经历一次加速。因此，只有A才是处在狭义相对论成立的惯性系当中，只有A的看法是正确的：当兄弟俩见面时，B比A更年轻。类似的效应已经被精密实验所证实了。其实只要用狭义相对论做详尽的计算，也能够从B的角度理解为什么B比A更年轻，但是这不得不做繁琐的计算，这里就不给出了。至此我们可以放心地说，狭义相对论在这个问题上是没有包含矛盾的。但是出去旅游一圈的双胞胎兄弟居然回来就比较年轻了，这一点可是颠覆了大多数人的世界观的...可是这是事实，不信也得信呀！
在中学里大家都学了质量的概念，然而事实上是有两种不同的质量的：惯性质量和引力质量。惯性质量是F=ma中的m，它是惯性大小的量度；引力质量是F=GMm/r^2中的m，它是引力大小的量度。之所以中学里并不对这二者进行区分，是因为这二者精确地相等。这一事实并不是理所当然的，而爱因斯坦正是通过这一神奇的事实，归纳出了广义相对论的一个基本假设：等效原理。
设想一个处于自由空间（没有引力作用）中的宇宙飞船，它以a=9.8m/s^2的加速度做加速直线运动。倘若里面的人扔出一个小球，小球由于惯性，将以9.8m/s^2的加速度落地；而这正如一个处于引力场中的惯性系所表现的那样。非惯性系中的惯性力正比于惯性质量，而引力则正比于引力质量。惯性质量与引力质量相等这一事实，导致了惯性力与引力这两种效应无法区分，这就是弱等效原理。爱因斯坦进一步推广，对于一切物理过程（不仅仅是力学过程），自由空间中的加速运动参考系，与引力作用下的惯性系，这二者在原则上完全不可区分，这就是强等效原理。
"引力场中一切物体都具有同一的加速度，这条定律也可表述为惯性质量同引力质量相等，它当时就使我认识到它的全部重要性。我为它的存在感到极为惊奇，并且猜想其中必有一把可以更深入了解惯性和引力的钥匙。"——爱因斯坦。
薛定谔的猫恐怕是物理界最著名的一只虚构小动物了，它是量子力学的创始人之一——薛定谔为了说明量子力学并不完备而提出的：
把一只猫放进一个封闭的盒子里，然后把这个盒子连接到一个包含一个放射性原子核和一个装有有毒气体的容器的实验装置。设想这个放射性原子核在一个小时内有50％的可能性发生衰变。如果发生衰变，它将会发射出一个粒子，而发射出的这个粒子将会触发这个实验装置，打开装有毒气的容器，从而杀死这只猫。根据量子力学，未进行观察时，这个原子核处于已衰变和未衰变的叠加态，猫则处在死和活的叠加态，即"既死又活"（而不是很多人误解的"半死不活"、"要么死要么活"）。但是，如果在一个小时后把盒子打开，实验者只能看到"衰变的原子核和死猫"或者"未衰变的原子核和活猫"两种情况。现在的问题是：这个系统从什么时候开始不再处于两种不同状态的叠加态而成为其中的一种？在打开盒子观察以前，这只猫是死了还是活着抑或既死又活？这个实验的原意是想说明，如果不能对波函数塌缩以及对这只猫所处的状态给出一个合理解释的话，量子力学本身是不完备的。
薛定谔的猫是物理学家的一个噩梦，它把微观的量子力学效应放大到了宏观的日常生活，使得一切都变得十分诡异。对于薛定谔的猫的解释，涉及到了多种对量子力学的深刻哲学理解，本文就不详述了，如果你想搞清楚这只神奇的猫的命运，那么请到物理学院来学习吧！
后记：
思想实验是物理学史上伟大的智慧结晶，回顾一番足以看出其中闪耀的智慧光芒。望这些思想实验能够给读者带来对世界认识的启迪吧。
| 您可能也喜欢： |
 盘点数学里十大不需要语言的证明 |
| 不完整的实验 |
| 如何辨别自己在现实还是虚拟世界 |
| 纸的承受能力竟然是如此之大 |
| 硬币也可以浮在水面上！ |
| 无觅 |
