个人笔记

您所在的位置:网站首页 图灵机计算1+2 个人笔记

个人笔记

2024-02-27 06:43| 来源: 网络整理| 查看: 265

用图灵机实现函数F(X,Y)=aX2+bY,

相当于包含两个部分,第一个部分解决乘法,第二部分解决加法。 采用的是比较传统的单带单道图灵机参数放置如下: q a 0 X 0 X 0 b Y 0

其中q表示的是初始状态,每个参数之间用0隔开区别。 拆分计算aX2,首先计算aX,假设c=aX,紧接着计算cX。

计算aX: (1)读取最左侧的1,将其替换为a并右移,直到遇到第一个0,右移; (2)遇到1则将其替换为x,并右移; (3)重复(2)直至再次遇到0; (4)左移直至遇到a,在右移一次,若遇到1则将其替换为a,转(5);遇到0则将0替换为空并回到最左侧,将所有的a替换为0,将x替换为1; (5)右移遇到x,将其替换为x1; 完成(1)~(5)的步骤将计算完成aX,令c=aX,按照同样的步骤完成cX。

计算bY的时候反向进行: (1)读取最右侧的1,将其替换为y并左移,直到遇到第一个0,左移; (2)遇到1则将其替换为b,并左移; (3)重复(2)直至再次遇到0; (4)右移直至遇到y,在左移一次,若遇到1则将其替换为y,转(5);遇到0则置空并右移到最右侧,将所有的y和0都替换为空,将b替换为1; (5)左移遇到b,将其替换为b1;

计算完成了aX2和bY,再将它们进行加减。令X=aX2,Y=bY,则下面需要计算X+Y的值。 计算X+Y: (1)从左侧开始右移,遇到1直接右移,遇到0,将其替换为1在右移,直至遇到空; (2)遇到空则左移一次,左移遇到1,则将其变为0; (3)接着左移,直至移动到做左侧。

例如a=3,X=2,b=2,Y=3,其移动模型如下: aX2:

→ # 1 1 1 0 1 1 0 1 1 0

→ # a 1 1 0 1 1 0 1 1 0

→ # a 1 1 0 x x 0 1 1 0

→ # a a 1 0 x 1 x 1 0 1 1 0

→ # a a a 0 x 1 1 x 1 1 0 1 1 0

→ # # # # # 1 1 1 1 1 1 0 1 1 0

→ 1 1 1 1 1 1 0 1 1 0

→ # a a a a a a 0 x 1 1 1 1 1 x 1 1 1 1 1 0

→ # # # # # # # # 1 1 1 1 1 1 1 1 1 1 1 1 0

→ # 1 1 1 1 1 1 1 1 1 1 1 1 0

bY: → 0 1 1 0 1 1 1 0 #

→ 0 1 1 0 1 1 y 0 #

→ 0 b b 0 1 1 y 0 #

→ 0 b 1 1 b 1 1 0 y y y 0 #

→ 0 1 1 1 1 1 1 # # # # #

→ 0 1 1 1 1 1 1 #

aX2+bY:

→ # 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 #

→ # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 #

→ # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 #

→ # 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 #

(省略了部分重复的步骤)



【本文地址】


今日新闻


推荐新闻


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