图灵机
这个装置由下面几个部分组成:一个无限长的纸带,一个读写头(中间那个大盒子),内部状态(盒子上的方块,比如A, B, E, H),另外,还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。
图灵机
当前内部状态s 输入数值i 输出动作o 下一时刻的内部状态s'
B 1 前移 C
A 0 往纸带上写1 B
C 0 后移 A
…………
图灵机
建模:
(1)小虫、纸带、方格
(2)黑色或者白色的信息就是小虫的输入信息
(3)小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格
(4)行动的规则
图灵机
程序1:
图灵机
程序2:
1
2
3
图灵机
程序2
4
5
6
7
图灵机
程序3
1
2
图灵机
3
4
5
图灵机
6
7
8
图灵机
小虫模型是对图灵机一个模拟,可以把小虫的输入集合、输出行动集合、内部状态集合进行扩大。
接下来对图灵机模型进行形式说明。
计算引论 计算模型 来自淘豆网www.taodocs.com转载请标明出处.