1701065701
1701065702
4.如果处于奇数状态，当前格子为0，就在格子中写入1，并变成停机状态。
1701065703
1701065704
5.如果处于偶数状态，当前格子为0，就在格子中写入0，并变成停机状态。
1701065705
1701065706
首先在带子上写好输入，然后让图灵机根据规则顺序处理输入，这个过程被称为“根据输入运行图灵机”。
1701065707
1701065709
定义为图灵机的明确程序
1701065710
1701065711
在上面的例子中，如果输入的格式正确，不管具体的输入是什么（包括一个1也没有的情况，这时视为有偶数个1），根据输入运行图灵机都能确保得出正确的输出。虽然这有点小儿科，但你还是得承认这是一个解决奇偶问题的“明确程序”，每一步都很明确。图灵的第一个目标就是落实明确程序的概念。其中的思想是，对于特定的问题，你可以通过设计一个解决这个问题的图灵机来构造明确程序。这样“明确程序”就定义为图灵机，虽然目前还有些模糊不清。
1701065712
1701065713
在对此进行思考时，图灵并没有真的去建造一台机器（虽然后来他这样做了）。他对图灵机的所有思考都是通过纸和笔完成的。
1701065714
1701065716
通用图灵机
1701065717
1701065718
接下来，图灵又证明了图灵机的一个神奇特性：人们可以设计出一种通用图灵机（称之为U），它可以模拟任何图灵机的运作。U在模拟图灵机M处理输入I时，U处理的带子上不仅包含编码输入I的序列，还包含编码图灵机M的序列。你可能会奇怪图灵机M也能被编码，不过这其实不难。首先，所有规则（同前面那五条差不多）都可以简写成下面这种形式：
1701065719
1701065720
—当前状态—当前符号—新状态—新符号—动作—
1701065721
1701065722
这样前面的规则1就表示成：
1701065723
1701065724
—启动—0—偶数—空—右移—
1701065725
1701065726
（分隔符“—”不是必需的，只是方便我们读规则。）然后用0/1序列对规则进行编码：例如，启动=000，偶数=001，奇数=010，停机=100。类似的，符号也能编码成0/1序列：例如，符号“0”=000，符号“1”=001，空符号=100。0/1序列可以随意设定，只要与符号一一对应就行。状态和符号——比如启动和“0”——之间使用的0/1序列可以相同；因为我们知道规则的结构形式，据此就能分析出编码的内容。
1701065727
1701065728
类似的，也可对动作进行编码，“右移”对应000，“左移”对应111。将分隔符“—”编码成111。这样整条规则都可以编成0/1序列了。编码出来的规则1是这个样子：
1701065729
1701065730
111000111000111001111100111000111
1701065731
1701065732
其他规则也可以依此编为0/1码。将所有规则的编码连到一起，形成一个长串，就是图灵机M的编码。为了让U模拟M处理I, U最初的带子上既包含I也包含M的编码。U的每一步在带子的输入部分读取I的当前符号，并从带子的M部分读取相应的规则，应用于输入部分；这样就能模拟跟踪M在处理给定输入时的状态和输出。
1701065733
1701065734
如果M到达停机状态，U也会停机，并且带子上产生的输出会与M处理给定输入I时产生的输出一样。因此我们说“U在I上运行M”。这里没有讨论U本身的状态和规则，因为比较复杂，但是这种图灵机是肯定可以设计出来的。事实上，现在的可编程计算机正是这样一台通用图灵机：它读取存储的程序，并在存储的输入I上运行这个程序。在图灵证明了存在通用图灵机之后十来年，第一台可编程的计算机就被建造出来了。
1701065735
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
[
上一页 ]
[ :1.701065701e+09 ]
[
下一页 ]