1、奇怪的理发师
罗素悖论（Russell's paradox）也称为“理发师悖论”。这里的罗素，就是大名鼎鼎的伯特兰·罗素，曾获诺贝尔文学奖的英国哲学家、数学家和政治活动家。1920年，罗素来中国讲学，毛泽东曾任记录员。罗素反战、反宗教的思想也为中国人熟知。
“罗素悖论”是罗素在数学上的重要成果，它直接造成了第三次数学危机。
“罗素悖论”说有一个理发师，他只帮“所有不自己刮脸的人刮脸”。那理发师该给自己刮脸吗？如果刮，那就违反了承诺。如果不刮，按照承诺他又该刮。矛盾出现了。
还有许多与“罗素悖论”相似的悖论。比如“图书馆悖论”说的是图书馆要编一本书，记录馆内所有不自己列出书名的书。那么，这本新编的书要不要记录自己的书名？
“罗素悖论”的数学表述形式，就是假设有一类元素X，其有一个性质是X中的元素x不属于X。现在给另一个类A，使得A包含所有的x。问A是不是属于A自己？如果是的话，A肯定具有X的性质，即x不属于X，所以A不属于X，矛盾。如果不是的话，又因为A的性质与X相同，A应该属于X，又矛盾。
上述表述中的“类”，其实就是数学上有严格定义的“集合”。真正的类和集合的定义有一些细微的差别，比如很多集合可以组成类。
对“集合”的最朴素的理解就是“一堆东西”。这些“东西”，就是元素。集合有“无序性”，即元素排列不分先后。“互异性”，即元素各不相同。“确定性”，一个元素与一个集合只存在属于或不属于的关系，不可能既属于又不属于。集合又分有限集和无限集。比如，所有的自然数可以组成一个集合，是无限集。
在数学上，集合还有一个几乎等义的名词——“外延”。比如，函数的集合是定义域和值域的有序对，这些有序对也同样是函数的“外延”。
有“外延”就有“内涵”。前面说到，很多集合可以组成一个类。“内涵”是一个类中所共同拥有的性质的可能的集合。一个类中，内涵越大，外延就越小；外延越小，内涵就越大。举例来说，“轿车类”的内涵是所有可能的“轿车集合”，这个“轿车类”里面包含很多“轿车集合”，包括模型轿车，玩具轿车，巧克力做的轿车，甚至想象中的轿车。而“轿车类”的外延在不同的情况下可以意味着不同的事物，可能它仅仅表示真实存在的轿车。
说了这么多，类的“内涵”跟“罗素悖论”到底有什么关系？原来，“罗素悖论”正是抓住了“内涵公理”的一个漏洞。
“内涵公理”用来形容怎样的集合可以组成一个类。它是这样表述的：如果P是集合的一个性质（符合P的元素组成的集合），那么存在类A，使得A中的任何元素都有P的性质。试想，“内涵公理”中的集合如果是X，P如果换成x不属于X，不就是我们之前讨论过的矛盾问题吗？“罗素悖论”其实就是“内涵公理”的悖论。
数学家为了解决这个难题，修改了“内涵公理”的定义。修改后的表述方法如下：如果P是集合的一个性质，那么存在类A，其中，[x属于A]等价于[有P的性质的所有元素或x自己]。
回到“罗素悖论”，P(x)表示x不属于X的性质。A中的x不属于X，但是属于x自己的集合呀。所以就不会有矛盾了。
用理发师来举例，由他只帮“所有不自己刮脸的人刮脸”，变成他只帮“所有不自己刮脸的人刮脸，或者帮理发师自己刮脸”。那理发师当然可以给自己刮脸了，数学的可靠性得到了维持。
1900年前后，福尔蒂、康托和罗素分别发现了集合论中的致命悖论。这些悖论使数学大厦的基石发生了动摇。德国数学家弗雷格在他的书中写道：“一位科学家不会碰到比这更难堪的事情了，即在工作完成之时，它的基础垮掉了。”
尽管数学家通过更完善的定义化解了这次危机，但是数学的基础，会不会仍然存在别的隐患？我们能够在多大程度上信任我们曾经深信不疑的数学？
2、图灵的构想
无独有偶，英国科学家图灵在解决“停机问题”(Halting problem)的时候使用了相似的悖论。
首先介绍图灵机。图灵机可以看成是有一端无限延伸的纸带，纸带上被分为无穷多个区间。有一个读写头，可以在某一个区间内写入、擦除数据。它还可以从一个区间移动到另一个区间。另外，有一套“控制规则”，它决定了机器目前的状态（读写还是移动）和根据区间内的内容，读写头要如何移动。此外，还有一个状态寄存器，它保存了机器所有的状态。图灵认为，这样一台机器可以完全模拟人类的思维活动。
所谓停机问题，就是判断一个程序是否会在有限时间内结束运行的问题。就图灵机而言，当读写头处于写入状态时，视作由外界向图灵机输入。所以停机问题具体为，是否存在某个输入x，当输入x时机器进入“停机”状态。
现在假设存在一个测试程序T，由它把x输入图灵机进行测试。假若找不到x可以让图灵机停止，则测试程序输出0。假若存在某个x使图灵机停机，则测试程序输出1。
现在来考察T的可信度。由于这个测试程序可以判别一切的图灵机，那么它应当对任何程序都有效。假如我们能构造出一个程序，使T无法判断这个程序是否能停机，那么停机问题便成了一个悖论。
构造该程序如下：这个程序也有一个输入，它以此内容作为输入调用T，假如T运行的结果为1（停机），那么该程序永久运行下去（永不停机）；若T运行的结果为0（永不停机），则该程序立即停机。由于T本身有确定的结果，这个程序很容易实现。假设这个新程序叫“构造程序”。
现在使用T来判别这个“构造函数”。T的结果是确定的，假如结果是1（停机），则意味着“构造程序”调用T的结果是0（永不停机）；反之亦然。如此可见，T必须给出一个矛盾的结果。或者说T无法判断“构造函数”的停机情况。
以上证明了要判断一个程序是否能在有限时间内结束运行，是不可能的。
联想到图灵机对于人脑的对应，它以逻辑的方式很巧妙地告诉了我们，生命是件完全不可预测的事。翻开一本书，你能马上知道结局是什么。但是生活，永远都是未知数。你要的答案，也许在下一秒钟出现。也许，要等待一万年。