图灵机设计

您所在的位置:网站首页 图灵机计算过程例题及解析视频 图灵机设计

图灵机设计

2024-07-14 07:40| 来源: 网络整理| 查看: 265

在这里插入图片描述

https://www.youtube.com/watch?v=5Q1KO_8bVug 原视频(咖喱味有点重)

比如上面的那个图示,这个x+y上面是输入,下面是输出fx的值,这里假设x=3,y=4,最终fx结果应该是7。 结合上面的图示和下面状态机的一起看: 首先看上面的流程图:B就是blank空格的意思,就是说它不是一个数,不用于计算。用0表示有几个数,你可以当做是算几个0输出就是几,可以看到output那里除掉头尾空格是7个0;1用来分隔开两边的数,就相当于符号运算。 下面的一排圈和箭头就是状态机: 最左边第一个圈表示开始状态; 有个东西叫指针,它就是会指向哪里,然后可以移动的一个箭头,一开始应该指向第一个0; 再看下面第二个箭头上0/0,表示用"0/0"斜杠右边的数字替代左边的数字,这里其实就相当于从第一个0开始,如果向指针向右移动指向的是0,那么用0替代0,其实也就是忽略指针所指向的0;这里的R是指针向右走一个;因此第一步就相当于指针指向0,好,现在忽略它,因为它是符号(就是1)左边的数不用动它,因此指针现在向右走指向第二个0; 然后第二个圈那里,箭头是指向自己的,说明循环箭头上面的那个操作,也就是一直向右走碰到了0就忽略掉; 然后看第三个横向的箭头那里是“1/0,R”,意思就是碰到了1这个符号(比如加号),ok现在就用0替换掉这里的1,然后再把指针向右移动; 然后第三个圈指向自己的箭头也是一样的操作,就是继续往右走碰到0就忽略掉; 好了现在如果指针指向了blank,就用blank替换掉它自己,反正空格都是一样的,所以这里只是提醒你已经到末尾了没有数了,然后指针向左走“B/B,L”; 然后指针向左走碰到了一个0,那么就用blank替换掉它,于是就剩下来了一堆0,数一下有几个0,一共7个,就是输出x+y的操作; 状态机最后那个圈里面有个圈,表示最终终止状态“Final m-config”。 你说的f(x)=x+2应该就是类似上述操作,x是一样的,然后碰到了符号就画两次“0/0,R"就是了吧大概。我这么讲可能有点啰嗦也不太清楚,具体的你想了解还是看看视频或者我给你的那个文档吧~



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3