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
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擦掉,并往右移动一格。
1701065701
1701065702
4.如果处于奇数状态,当前格子为0,就在格子中写入1,并变成停机状态。
1701065703
1701065704
5.如果处于偶数状态,当前格子为0,就在格子中写入0,并变成停机状态。
1701065705
1701065706
首先在带子上写好输入,然后让图灵机根据规则顺序处理输入,这个过程被称为“根据输入运行图灵机”。
1701065707
1701065709
定义为图灵机的明确程序
1701065710
1701065711
在上面的例子中,如果输入的格式正确,不管具体的输入是什么(包括一个1也没有的情况,这时视为有偶数个1),根据输入运行图灵机都能确保得出正确的输出。虽然这有点小儿科,但你还是得承认这是一个解决奇偶问题的“明确程序”,每一步都很明确。图灵的第一个目标就是落实明确程序的概念。其中的思想是,对于特定的问题,你可以通过设计一个解决这个问题的图灵机来构造明确程序。这样“明确程序”就定义为图灵机,虽然目前还有些模糊不清。
1701065712
1701065713
在对此进行思考时,图灵并没有真的去建造一台机器(虽然后来他这样做了)。他对图灵机的所有思考都是通过纸和笔完成的。
1701065714
[
上一页 ]
[ :1.701065665e+09 ]
[
下一页 ]