现代生活离不开计算，无论是工作、出行，还是购物、娱乐，背后都是大量的计算。但是在他的构想出现之前，人类5000年里的总计算量，都比不上现在的1秒钟。
他就计算机科学与人工智能之父——艾伦·图灵。
图灵一直在探索人类究竟是如何思考的，他发现可以将人类的思考过程简化，并构想出第一台通用计算机——图灵机。
图片来自吴翰清的《计算》
图灵机的伟大在于它十分简洁，只有三部分组成：纸带、表头和操作规则。
纸带：代表着信息的输入和输出，而上面只有数字“0”或“1”。
表头：相当于人的眼睛和手（或者耳朵和嘴巴），代表在哪个位置读取信息，在哪个位置输出信息。
操作规则：相当于人的大脑，里面存着思维模式，即规则，接收信息后，根据规则决定表头怎样移动，以及输出什么信息。
表头读取纸带信息，操作规则判断表头如何行动，表头移动并改写纸带上的数字。这就是图灵机的一个流程，它可以完成一个接一个的流程。
图灵正是基于哥德尔的思想，将所有的数字、符号和等式都进行数字编码，只不过这次用的不是哥德尔数，而是二进制数字。
提出不完备定理的哥德尔
然后所有基于代数数的运算，都能写成操作规则中的细分步骤，那样就能实现用机器代替人力计算。
图灵正是基于自己的这个构想，在二战期间，打造了一台可以运算的机器，破解了德国引以为傲的密码系统英格玛（Enigma），帮助盟军至少提前了两年结束第二次世界大战，预计挽救了一千四百万生命。
而我们现在所有的操作系统、人工智能和3A游戏大作，本质上都是图灵机。
图灵机的提出是一次计算革命，所有的数学问题都可以转化为图灵机的运算。
然而图灵机按照指令运行时，有可能会进入停机或者循环状态。
停机，就是当满足某些条件时，操作规则会下令机器停止运行，比如找到了我们要的答案。
而循环，就是在一定的操作规则之下，输入的信息会正好形成一个永远反复的过程。
那么能否判定某条输入信息在一个操作规则之下，最终将会停机还是会无限运行？
这就是著名的停机问题。
能否判断，最终会进入左边的停机状态，还是会进入右边的循环状态
起初人们以为这很容易判断，毕竟图灵机的运算能力很强大。
可事实上，有很多问题，完全看不到结果。
规则简单的兰顿蚁（Langton's Ant）在走了近10000步之后才显出规律
图灵用反证法证明了，没有任何算法能判定图灵机是否会停机。
假设有一台图灵机h可以判定会停机或者循环，那么我们构造一台新的图灵机h+，只需要设定当H会停机时，h+就进入循环；当h会循环时，h+就进入停机。
那么我们就用h+来运行自己生成的代码，如果停机，那么它就应该循环；如果循环，那么它就应该停机。
无论怎样都将产生矛盾，因此这样的图灵机不存在。
其实这就是一个反身自指带来的矛盾，是埋藏于数理逻辑底层的悖论。
事实上，如果图灵机能判定停机问题，那么很多数学猜想都将被攻破。
比如哥德巴赫猜想：只要写一段代码，如果一个大于2的偶数能拆成两个素数之和，则进入下一个偶数的判定，如果不能，则停机。
那样判断这个程序是否会停机，就等同于证明或证伪了哥德巴赫猜想。
如果我们能判断它是否停机，哥德巴赫猜想就解决了。因为，如果循环，就说明找不到反例，哥德巴赫猜想成立。如果停机，说明找到了反例，哥德巴赫猜想不成立。
孪生素数猜想和黎曼猜想也一样。
图灵机不仅仅是一种计算机理论模型，更是理解计算能力极限的关键。
图灵正是受到哥德尔思想的启发才提出的图灵机构想。
停机问题的不可判定性，也可以导出哥德尔不完备定理的证明。
这在本质上是因为图灵机和希尔伯特的数学大厦都是构建在自然数公理体系之上的，也就是康托尔的可数无穷基础上的。
康托尔认为自然数和有理数都是可数的无穷
图灵机虽然无比强大，但从它诞生的第一天起，图灵就清楚它能力的极限，就像一位大力士永远无法举起自己一样。
数学、逻辑、哲学和计算机都在这里交汇，交点就是自指引起的罗素悖论，这是一个无法绕开的巨大漩涡。
希尔伯特的名言是“我们必须知道，我们必将知道”。
然而图灵告诉我们：也许总有一些东西，我们无法知道。
原点阅读入驻小红书啦！
每天更新科普小知识
↓ 识别二维码直达主页 ↓
点个关注哟！
欢迎加入清华原点阅读和小伙伴们微信读者群
请联系微信mashuo577044（添加时请注明来意）
