是谁发明了计算机（三）
1937年在计算机的发展史上是个神奇的年份。
这一年，图灵（Alan Turing）在指导教授数学家纽曼（Max Newman）的启发下发表了一篇论文，其中提到了逻辑运算机（Logical Computing Machine），这就是后来大名鼎鼎的“图灵机”。
在1928年的时候，数学大拿希尔伯特（Hilbert）在一次年会上提出了三个问题：第一，在一个数学体系中，是否存在一套规则，可以判断任何一个命题的真伪；第二，这样的系统是否具有一致性，也就是一个命题不能一会儿被证明是真的，一会儿被证明是假的；第三，是否有一个机制来判断一个命题是否可以被验证。
三年之后，25岁的数学天才哥德尔（Kurt Gödel）对第一和第二个问题给出了否定的答案。哥德尔给出这样的一个例子，“这句话是无法被验证的。”（This statement is unprovable) 如果这句话是真的，那我们就无法验证它的真假，这个是矛盾的，因为既然无法验证，我们怎么能说这是真的呢？但如果这句话是假的，那就是说这句话是可以被证实的（This statement is provable），结果变成 This statement is proved to be unprovable, 也是矛盾的。这和“我说的是假话”有异曲同工之妙。
最后问题的焦点就到了第三题，是否存在这样的机制可以决定一些命题可被验证，但另一些命题是无法验证的，如果有这样的机制，那么我们就可以找出那些无法验证的命题（就像我们上面提到的This statement is unprovable 的例子），把它们排除之后，就可以找到满足希尔伯特第一第二问题的系统了。而图灵的论文就是试图回答这个问题。
他设计了一台假想的逻辑运算机（Logical Computing Machine），有四部分组成：
明眼人都看出来了，这不就是一台计算机的雏形吗？就是用这台逻辑运算机，图灵解开了希尔伯特的第三个问题。首先，图灵提出在逻辑运算机进行运算的过程中，机器最终会到达两种可能的状态：一个是计算完成，机器停止，这就是停机状态；另一个是无限循环，计算永远完成不了。然后图灵设计了一个巧妙的悖论：假设存在一个判断程序H，它可以判断某个程序P是否会到达停机状态：
如果P会停机, 那么 H(P)=Halt；
这样矛盾就出来了，H判断K会停机，可是K因此决定无限循环，所以H判断错了；但如果H判断K会无限循环，K却会因此停机，这样我们就永远也无法通过H来判断K会不会停机，所以结论是：不存在一个可以判定停机问题的程序H。图灵就这样轻轻巧巧地就回答了希尔伯特的第三个问题：停机就代表一个命题是可证的，不能停机就是说那个命题无法验证，而判断程序H就是那个判断命题是否可证的机制，既然H不存在，那么也就不存在一个可以判定命题可证性的机制了。
图灵的论文也许对数学理论的建立有一些帮助，但他更大贡献却是那台假想的逻辑运算机，可以说现代计算机的所有基本要素都已经出现在这台机器里了。
写完论文，图灵的指导教授就把他推荐给了普林斯顿大学的另一位数学大牛Alonzo Church。于是图灵远渡重洋，来到了普林斯顿，搬进了爱因斯坦，哥德尔等人所在的数学系大楼（那真是一个群星璀璨的年代）。正是图灵的新老板Alonzo Church，当看完图灵的论文，非常慷慨地把“逻辑运算机”改成了以作者本人命名的“图灵机”，从此“图灵机”扬名天下，而24岁的图灵也在计算机发展史上，打下了一个永恒的印记。
剩下的问题就是如何才能真正地把图灵机制造出来了。
这一年，图灵（Alan Turing）在指导教授数学家纽曼（Max Newman）的启发下发表了一篇论文，其中提到了逻辑运算机（Logical Computing Machine），这就是后来大名鼎鼎的“图灵机”。
在1928年的时候，数学大拿希尔伯特（Hilbert）在一次年会上提出了三个问题：第一，在一个数学体系中，是否存在一套规则，可以判断任何一个命题的真伪；第二，这样的系统是否具有一致性，也就是一个命题不能一会儿被证明是真的，一会儿被证明是假的；第三，是否有一个机制来判断一个命题是否可以被验证。
三年之后，25岁的数学天才哥德尔（Kurt Gödel）对第一和第二个问题给出了否定的答案。哥德尔给出这样的一个例子，“这句话是无法被验证的。”（This statement is unprovable) 如果这句话是真的，那我们就无法验证它的真假，这个是矛盾的，因为既然无法验证，我们怎么能说这是真的呢？但如果这句话是假的，那就是说这句话是可以被证实的（This statement is provable），结果变成 This statement is proved to be unprovable, 也是矛盾的。这和“我说的是假话”有异曲同工之妙。
最后问题的焦点就到了第三题，是否存在这样的机制可以决定一些命题可被验证，但另一些命题是无法验证的，如果有这样的机制，那么我们就可以找出那些无法验证的命题（就像我们上面提到的This statement is unprovable 的例子），把它们排除之后，就可以找到满足希尔伯特第一第二问题的系统了。而图灵的论文就是试图回答这个问题。
他设计了一台假想的逻辑运算机（Logical Computing Machine），有四部分组成：
- 一个内存（Memory），这是一条无限长的纸带，上面有一个个的小方格，格子里是字符（最简单的就是 0／1），或者是空白；
- 一个读写头，它停在小方格上，可以有三个动作：读取字符，改写字符，向左或向右移动一小格；
- 一个状态寄存器（Register）
- 一个控制程序（Table of Instructions），根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
明眼人都看出来了，这不就是一台计算机的雏形吗？就是用这台逻辑运算机，图灵解开了希尔伯特的第三个问题。首先，图灵提出在逻辑运算机进行运算的过程中，机器最终会到达两种可能的状态：一个是计算完成，机器停止，这就是停机状态；另一个是无限循环，计算永远完成不了。然后图灵设计了一个巧妙的悖论：假设存在一个判断程序H，它可以判断某个程序P是否会到达停机状态：
如果P会停机, 那么 H(P)=Halt；
如果P不停机, 那么 H(P)=NOT Halt
我们再构建一个程序K，它会把判断程序H当作子程序（subroutine）来调用，然后根据H对K判定的结果，反其道而行：
如果H说我会停机，也就是 H(K)=Halt，那么我就无限循环 K will Not Halt；
如果H说我不停机，也就是 H(K)=NOT Halt，那么我就停机 K will Halt
这样矛盾就出来了，H判断K会停机，可是K因此决定无限循环，所以H判断错了；但如果H判断K会无限循环，K却会因此停机，这样我们就永远也无法通过H来判断K会不会停机，所以结论是：不存在一个可以判定停机问题的程序H。图灵就这样轻轻巧巧地就回答了希尔伯特的第三个问题：停机就代表一个命题是可证的，不能停机就是说那个命题无法验证，而判断程序H就是那个判断命题是否可证的机制，既然H不存在，那么也就不存在一个可以判定命题可证性的机制了。
图灵的论文也许对数学理论的建立有一些帮助，但他更大贡献却是那台假想的逻辑运算机，可以说现代计算机的所有基本要素都已经出现在这台机器里了。
写完论文，图灵的指导教授就把他推荐给了普林斯顿大学的另一位数学大牛Alonzo Church。于是图灵远渡重洋，来到了普林斯顿，搬进了爱因斯坦，哥德尔等人所在的数学系大楼（那真是一个群星璀璨的年代）。正是图灵的新老板Alonzo Church，当看完图灵的论文，非常慷慨地把“逻辑运算机”改成了以作者本人命名的“图灵机”，从此“图灵机”扬名天下，而24岁的图灵也在计算机发展史上，打下了一个永恒的印记。
剩下的问题就是如何才能真正地把图灵机制造出来了。
Comments