为什么会出现图灵机?这得从罗素悖论讲起。
罗素悖论
有位理发师放出豪言:他给且只给不为自己刮胡子的人刮胡子。问:这位理发师该为自己刮胡子吗?
如果理发师为自己刮胡子,那么按照他的豪言“只给不为自己刮胡子的人刮胡子”他不应该为自己刮胡子;但如果他不为自己刮胡子,同样按照他的豪言“他给不为自己刮胡子的人刮胡子”他又应该为自己刮胡子。
这个问题就是著名的理发师悖论,是哲学家兼数学家的罗素用来比喻罗素悖论的一个通俗说法,也被叫作集合论悖论,用集合论来描述就是:
集合 S 由一切不属于自身的元素组成,那么 S 是否属于 S 呢?
在这一悖论提出之前集合论是数学理论的重要基础,结合集合论,历史上的一切数学问题都可以完美地等到求证,当时人们已经相信整个数学大厦已经建立起来了,数学已经迎来了绝对的严格性。
但罗素悖论出现后,人们心中的大厦坍塌了,直接导致了历史上的第三次数学危机。当时提出集合论的数学家康托尔也被这个悖论逼疯了,可怜的康托尔。由此可见罗素这个人在数学界的影响。
哥德尔不完备性定理
当时人们好不容易在集合论的基础上构建起了数学大厦,结果集合论也是不完美的,连这个基础都崩溃了。那还能不能找到一个系统,在它的基础上真正构建整个数学大厦呢?
后来有一个数学家哥德尔成功证明了一个定理,大意是这样的:
世界上存在我们既没办法证真也没办法证伪的命题。
比如前文说的的集合论,还有典型的 1+1=2 的问题,我们既不能证明它们是真命题,也不能证明它是伪命题。这个定理被称为哥德尔不完备性定理。我们可能会想,这种定理也能被证明?他是怎么证明的?这个我们就不去研究了,反正哥德尔他就是证明了这样的一个定理,过程是很复杂的。
哥德尔不完备性定理的证明结束了关于数学基础的争论,宣告了数学不是绝对严格性的,把数学彻底形式化这种愿望是不可能实现的,不存在这样一个完美的数学系统。
哥德尔不完备性定理告诉我们,不要试图去寻找一个完美的系统,这不存在的,这辈子都不可能存在的。
那么,有了这个结论,我们是不是就可以不往下探索了呢?如果还可以往下探索,我们该探索什么问题?
计算模型和图灵机
通过哥德尔不完备性定理,我们知道,有些问题是既不能证真也不能证伪的,有些问题是可以证真或证伪的。对于这两类问题,它们的边界在哪里?怎么去判定一个未解的问题是否真的有解?
为了解答这个问题,我们需要引入一个度量:可计算问题。在数学中对应可计算函数,它的定义是这样的:
设函数 f 的定义域为 D,值域为 R,如果存在一种算法,对于 D 中任意给定的 x,都能计算出 f(x) 的值,则称函数 f 是可计算的。
这是当时诸多数学家、逻辑学家等对判断一个问题是否可计算提出的一个思路。通俗的讲就是,先给定一个模型,如果拿有限的值去套这个模型,能够得到期望的结果,那就说明这个问题是可计算的,否则是不可计算的。这里用来判断问题是否可计算的模型就被称为:计算模型。
那么如何设计或找到这样一个计算模型呢?这是当时人们所面临的一个重要问题,一直没有得到解决。后来终于有一位数学家提出了一个这样的模型,他就是图灵。他提出的这个计算模型被称为图灵模型,而这个图灵模型就是图灵机。
好了,到这里我们已经知道了历史背景下为什么会诞生图灵机。那么图灵模型它是一个怎样的模型?图灵机它又是如何工作的呢?这就是下一篇要讲的内容。
最后顺带讲一下图灵这个人,相信很多人都听过他的故事,他真的是很牛逼。他 24 岁就提出了图灵机,二战期间参与了密码破译工作,任密码破译总顾问,后来还提出了著名的“图灵测试”,逝世前两年还写出了第一个国际象棋程序。图灵的贡献对计算机领域的发展有着非常深远的影响,可惜他享年只有 42 岁(1912 年 - 1954 年),如果不是英年早逝的话,计算机的整个发展史可能就要重写了。
参考: