文章目录
一、图灵机特点
二、自动机特点
三、数的扩张
四、计算模型的扩张
一、图灵机特点
----
图灵机特点 :
① 读写头特点 : 图灵机 既可以读 , 也可以写 ;
② 移动方向 : 图灵机的读写头既可以向左移动..., 又可以向右移动 , 可以 双向移动 ;
③ 带子长度 : 图灵机的带子是 无限长的 ;
④ 停机判定 : 图灵机一旦 到达接受状态 , 立刻停机 ;
二、自动机特点
----
自动机特点 :
①...读头特点 : 自动机只能读 , 不能写 ;
② 移动方向 : 自动机的读头只能向右进行移动 ;
③ 带子长度 : 自动机的带子是输入字符串长度 ;
④ 停机判定 : 自动机在计算过程中 , 某个时刻可能到达接受状态...----
下面开始讨论计算模型的扩张
计算模型从最简单的模型 确定性有限自动机 , 一步步进行扩张 , 最后得到计算的极限 图灵机 ;
下图是 确定性有限自动机 的示意图 , 带子上是输入字符 , 矩形框中是当前状态..., 再加一个栈 , 两个栈的下推自动机 , 与 图灵机 的计算能力是等价的 ;
两个栈的下推自动机 与 图灵机 等价 , 其计算能力已经达到计算的极限 ;
\rm n
(
n > 2
) 个栈的下推自动机的计算能力