1701065651
复杂 [:1701064738]
1701065652
图灵机和不可计算性
1701065653
1701065654
哥德尔干净利落地解决了希尔伯特第一和第二问题，接着第三问题又被英国数学家图灵（Alan Turing，图4.3）干掉了。 [57]
1701065655
1701065656
1935年，图灵23岁，在剑桥跟随逻辑学家纽曼（Max Newman）攻读研究生。纽曼向图灵介绍了哥德尔刚刚得出的不完备性定理。在理解哥德尔的结果之后，图灵发现了该如何解决希尔伯特的第三问题， ；判定问题，同样，他的答案也是“否” [58] 。
1701065657
1701065658
图灵是怎么证明的呢？前面说过，判定问题问的是，是否有“明确程序”可以判定任意命题是否可证？“明确程序”指的是什么呢？图灵的第一步就是定义这个概念。沿着莱布尼茨在两个世纪以前的思路，图灵通过构想一种强有力的运算机器来阐述他的定义，这个机器不仅能进行算术运算，也能操作符号，这样就能证明数学命题。通过思考人类如何计算，他构造了一种假想的机器，这种机器现在被称为图灵机。图灵机后来成了电子计算机的蓝图。
1701065659
1701065660
1701065661
1701065662
1701065663
▲图4.3 图灵（1912—1954）（Photo Researchers公司版权所有©2003，经许可重印）
1701065664
1701065665
复杂 [:1701064739]
1701065666
图灵机概述
1701065667
1701065668
如图4.4所示，图灵机由三部分组成：
1701065669
1701065670
1.带子，被分成许多方格（或“地址”），符号可以被写入其中或从中读出。带子两头都有无限长。
1701065671
1701065672
2.可以移动的读写头，能从带子上读取符号或将符号写到带子上。在任何时候，读写头都处于一组状态中的一个。
1701065673
1701065674
3.指示读写头下一步如何做的一组规则。
1701065675
1701065676
1701065677
1701065678
1701065679
▲图4.4 图灵机
1701065680
1701065681
读写头开始处于特定的开始状态，并停在特定的格子上。每一步，读写头读取当前格子中的符号。然后读写头根据读取的符号和读写头的当前状态按照规则动作。规则决定读写头在当前格子中写入什么符号（替换当前符号）；读写头是向右还是向左移动或是停止不动；以及读写头的新状态是什么。如果读写头进入停机状态，机器就会停下来。
1701065682
1701065683
图灵机的输入是机器启动之前写在带子上的符号集合。输出则是停机之后留在带子上的符号集。
1701065684
1701065685
复杂 [:1701064740]
1701065686
一个简单的例子
1701065687
1701065688
用一个简单的例子解释一下。为简便起见，假设带子上的符号只有0和1（同真正的计算机一样），而空符号则指格子中为空。我们设计一个图灵机，它读取的带子上有两个0，中间夹着一串1（例如，011110），然后判断1的个数是奇数还是偶数。如果是偶数，机器最后就在带子上输出一个0（其他格子为空）。如果是奇数，最后就在带子上输出一个1（其他格子为空）。假设带子的输入总是刚好有两个0，中间夹着零个或多个1，其他的格子都为空。
1701065689
1701065690
我们的图灵机的读写头得有4种可能状态：启动、偶数、奇数和停机。读写头最初停在最左边的0，处于启动状态。我们编写规则让读写头往右移动，每次一格，用空格替换遇到的0和1。如果读写头在当前格子中读到1，读写头就变成奇数状态，并往右移动一格。如果再次读到1，就变成偶数状态，再往右移动一格。就这样读到1就在偶数和奇数状态之间切换，一直往下。
1701065691
1701065692
如果读写头读到0，输入就走完了，这时所处的状态（奇数或偶数）就是想要的结果。然后机器根据状态在当前格子里写1或0，并变成停机状态。
1701065693
1701065694
下面是读写头实现这个算法的规则：
1701065695
1701065696
1.如果处于启动状态，当前格子为0，就变成偶数状态，把0擦掉，并往右移动一格。
1701065697
1701065698
2.如果处于偶数状态，当前格子为1，就变为奇数状态，把1擦掉，并往右移动一格。
1701065699
1701065700
3.如果处于奇数状态，当前格子为1，就变成偶数状态，把1擦掉，并往右移动一格。