文章目录
一、图灵机特点
二、自动机特点
三、数的扩张
四、计算模型的扩张
一、图灵机特点
----
图灵机特点 :
① 读写头特点 : 图灵机 既可以读 , 也可以写 ;
② 移动方向 : 图灵机的读写头既可以向左移动..., 又可以向右移动 , 可以 双向移动 ;
③ 带子长度 : 图灵机的带子是 无限长的 ;
④ 停机判定 : 图灵机一旦 到达接受状态 , 立刻停机 ;
二、自动机特点
----
自动机特点 :
①...图灵机 ;
下图是 确定性有限自动机 的示意图 , 带子上是输入字符 , 矩形框中是当前状态 , 读头指向带子上的字符 ;
下图是 下推自动机 , 是在 确定性有限自动机 的基础上 , 加上了一个...存储能力无穷 的 栈 , 栈的特点是 后进先出 ;
在上述
1
个栈的下推自动机 基础上 , 再加一个栈 , 两个栈的下推自动机 , 与 图灵机 的计算能力是等价的 ;
两个栈的下推自动机 与...图灵机 等价 , 其计算能力已经达到计算的极限 ;
\rm n
(
n > 2
) 个栈的下推自动机的计算能力 , 与
2
个栈的下推自动机计算能力是相同的 ;