1701065737
图灵对判定问题的解决
1701065738
1701065739
再来看看判定问题：是否有明确程序可以判定任意命题是否为真？
1701065740
1701065741
通过证明通用图灵机的存在，图灵证明了这个问题的答案是“否”。他意识到图灵机的编码也可以作为另一台图灵机的输入。这就好像用一个计算机程序作为另一个程序的输入。比方说，你可以用WORD写一个程序，存成一个文件，然后用另一个程序（字数统计）处理这个文件，输出你的程序的字数。字数统计程序并不运行你的程序，它只是统计文本文件中的字数。
1701065742
1701065743
类似的，你也可以设计出统计输入中1的个数的图灵机M（这个不是很难），然后运行M处理另一个图灵机M′。M会统计M′中的1的个数。当然，在通用图灵机U中，将M的代码置于U的带子的“程序”部分，将M置于带子的“输入”部分，U就能在M上运行M。为了好玩，我们也可以在U的带子的“程序”和“输入”部分都放置M，让M处理它自己的编码！这就好像让字数统计程序来计数它自己的字数。完全没有问题！
1701065744
1701065745
带子上的0/1序列既可以作为程序，也可以作为另一个程序的输入。对熟悉计算机的你来说，这一点可能稀松平常，但是在图灵提出他的证明的年代，这点洞察却是革命性的。
1701065746
1701065747
现在我们来看看图灵的证明。
1701065748
1701065749
图灵是用反证法证明判定问题的答案为“否”。首先假设答案是“是”，然后证明这个假设会导致矛盾，从而证明答案是相反的。
1701065750
1701065751
图灵首先假设，存在明确程序可以判定任意给定命题是否为真。然后他给出了这样一个命题：
1701065752
1701065753
图灵命题：图灵机M对于给定输入I会在有限步后停机。
1701065754
1701065755
根据前面的假设，将M和I作为输入，有一个明确程序可以判定这个命题是否为真。图灵证明，这个假设会导致矛盾。
1701065756
1701065757
我们注意到有一些图灵机永远也不会停机。例如，考虑与前面例子类似的一个图灵机，只有两条规则：
1701065758
1701065759
1.如果处于启动状态，读取到0或1，变为偶数状态，并往右移动一格。
1701065760
1701065761
2.如果处于偶数状态，读取到0或1，变为启动状态，并往左移动一格。
1701065762
1701065763
这个图灵机完全没有错误，但是它永远不会停机。用现在的话说是“死循环”——写程序时经常会碰到的bug。死循环有时候隐藏很深，让你很难发现。
1701065764
1701065765
前面假设了有明确程序能够判定图灵命题是否成立，这就等价于说我们能设计一个图灵机来检查死循环。
1701065766
1701065767
具体说，这个假设说的是我们能设计一个图灵机H，对于任何给定的图灵机M和输入I，都能在有限时间内判断M对输入I是会停机还是会进入死循环，停不了机。
1701065768
1701065769
设计H的问题被称为“停机问题”。注意到H本身必须总是能停机，不管答案是“是”还是“否”。因此H不能通过在I上运行M来做到这一点，因为有可能M不会停机，从而H也停不了。H必须想其他办法做到这一点。
1701065770
1701065771
虽然还不清楚H要如何做，但是我们假设了H是存在的。我们将运行H处理M和I记为H（M, I）。如果M对于I会停机就输出“是”（例如在带子上写一个1），如果M对于I不会停机就输出“否”（例如在带子上写一个0）。
1701065772
1701065773
然后图灵把H变了一下，将图灵机M也作为输入，计算H（M, M），记为H′。H′执行的步骤同H一样，它确定M处理它自身的编码M时会不会停机。不过，在得到结果后，H′执行的动作同H不一样。H在回答“是”或“否”后停机。H′则只有答案是“M对于编码M不会停机”时才会停机。如果答案是“M对于编码M会停机”，H′就进入死循环，永不停机。
1701065774
1701065775
这可能有点让人糊涂，希望你们能跟上。在计算理论的课程中，这是一个分水岭，一些学生会变得绝望，“我没法想明白这玩意！”一些学生则会拍手称快，“我喜欢这玩意！”
1701065776
1701065777
当初我也有些糊涂，不过我还是喜欢上了这些。也许你和我一样。我们来深呼吸一下，然后继续。
1701065778
1701065779
现在图灵抛出了最后的问题：
1701065780
1701065781
如果用H′自身的编码作为H′的输入，H′会怎么做呢？
1701065782
1701065783
到这个时候，拍手称快的学生也会开始头大。这确实很难想明白，不过我们还是试一试。
1701065784
1701065785
先假设H′对于输入H′不会停机。但这样就有个问题。前面说了，H′以图灵机M的编码作为输入时，如果M对于M会停机，H′就会进入死循环，反之则停机。因此，如果H′对于输入M不能停机，就意味着M对于输入M会停机。发现会有什么结果了吧？H′对于输入H′不会停机意味着H′对于输入H′会停机。但是H′不能既停机又不停机，这样就导致了矛盾。
[
上一页 ]
[ :1.701065736e+09 ]
[
下一页 ]