打字猴:1.701065715e+09
1701065715 复杂 [:1701064742]
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
1701065736 复杂 [:1701064743]
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
[ 上一页 ]  [ :1.701065715e+09 ]  [ 下一页 ]