图灵机

图灵机及其计算思维1234阿兰图灵其人图灵机模型图灵机的工作原理图灵机的计算能力阿兰·图灵阿兰·麦席森·图灵（AlanMathisonTuring，1912年6月23日－1954年6月7日），英国数学家、逻辑学家，被称为计算机之父，人工智能之父。1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。图灵对于人工智能的发展有诸多贡献，提出了一种用于判定机器是否具有智能的试验方法，即图灵试验，至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。图灵机的基本思想图灵认为，所谓计算，就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0或1，执行指令、程序，一步一步地改变纸带上地0或1，经过有限步骤，最后得到一个满足预先规定地符号串地变换过程。图灵机将控制处理地规则用0和1表达，将待处理地信息及处理结果也有0和1表达，处理即是对0和1的变换（可以用机械/电子系统实现）№图灵机的工作原理机器从给定带子上的某起始点出发，根据其初始状态及机内五元组决定其动作，经过有限步骤机器停止时，带子上的信息即为机器计算的结果。可能产生的问题：•无休止工作•如：q1S2S2Rq3指令和q3S3S3Lq1指令同时出现在机器中时•产生二义性•如：q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中时№图灵机的特征图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成写在带子上的符号为一个有穷字母表：{S0，S1，S2，Sp}一个给定机器的程序认为是机器内的五元组（qiSjSkRql或qiSjSkLql或qiSjSkNql）形式的指令集•qi表示机器目前所处的状态•Sj表示机器从方格中读入的符号•Sk表示机器用来代替Sj写入方格中的符号•R、L、N分别表示向右移一格、向左移一格、不移动•ql表示下一步机器的状态图灵机计算模型№q101Lq2q110Lq3q1bbNq4q200Lq2q211Lq2q2bbNq4q301Lq2q310Lq3q3bbNq4实例设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是10100010，读入头对准最右边第一个为0的方格，状态为初始状态q1。按照以下规则执行之后，输出正确的计算结果。№图灵机计算过程S(x)=x+12小虫的比喻假设一个小虫在地上爬，那么我们应该怎样从小虫信息处理的角度来建立它的模型呢？首先，我们需要对小虫所在的环境进行建模。我们不妨假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小方格，而每个方格都只有黑白两种颜色。黑色表示该方格有食物，白色就表示没有。假设小虫仅具有一个感觉器官：眼睛，而且它的视力差得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因而这个方格所在的位置的黑色或者白色的信息就是小虫的输入信息。其次，小虫有输出动作，它可以在方格上前移、后移，还可以涂写方格成黑色或者白色。最后，小虫还会有两种内部状态，即{饥饿，吃饱}。这样小虫的行动按照下面的程序进行：输入当前内部状态输出下时刻的内部状态黑饥饿涂白吃饱黑吃饱后移饥饿白饥饿涂黑饥饿白吃饱前移吃饱即如果当前处于饥饿状态，则有食物就吃掉，没有食物就“自行解决问题”（即自己会吐出食物）；如果当前处于吃饱的状态，则如果没有食物就前移，如果有就后退，并且转入饥饿状态。那么当小虫子读入黑白白黑白……这样的纸带的时候，会怎样行动呢？在图中，小虫用圆圈表示，它从最左边开始移动，灰色表示饥饿状态，白色表示吃饱状态。箭头表示移动的方向。从上到下，小虫一步一步地根据纸带的颜色和它自己的内部状态查找规则表中的对应项而采取行动。例如第5步读入方格是黑色，内部状态为吃饱，根据这两项输入信息查找规则表找到对应项是第二项，根据它，小虫应该后移，且内部状态变为饥饿。不难看到，到了第8步，情况跟第4步完全相同，输入都是白色纸带和饥饿状态，根据程序，小虫将重复4~8之间的动作，并一直持续下去……。34567尽管从长期来看，小虫会落入机械的循环。然而当你输入给小虫白色信息的时候，它的反应可能完全不同（如第4步和第6步的行为），所以只要小虫子的内部状态和程序非常复杂，那么小虫的行为也会越来越超出你的想象！№现代计算机的产生自从图灵机思想提出不到10年，世界上第一台电子计算机诞生了–图灵机反映的是一种计算模型，而现代计算机正是这种模型的具体实现–它是一种离散的，有穷的，构造性的问题求解思路凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了THANKS