文章目录
一、图灵机特点
二、自动机特点
三、数的扩张
四、计算模型的扩张
一、图灵机特点
----
图灵机特点 :
① 读写头特点 : 图灵机 既可以读 , 也可以写 ;
② 移动方向 : 图灵机的读写头既可以向左移动...读头特点 : 自动机只能读 , 不能写 ;
② 移动方向 : 自动机的读头只能向右进行移动 ;
③ 带子长度 : 自动机的带子是输入字符串长度 ;
④ 停机判定 : 自动机在计算过程中 , 某个时刻可能到达接受状态..., 任何一个实数 , 都可以写成一个有理数序列的极限 ;
四、计算模型的扩张
----
下面开始讨论计算模型的扩张
计算模型从最简单的模型 确定性有限自动机 , 一步步进行扩张 , 最后得到计算的极限...存储能力无穷 的 栈 , 栈的特点是 后进先出 ;
在上述
1
个栈的下推自动机 基础上 , 再加一个栈 , 两个栈的下推自动机 , 与 图灵机 的计算能力是等价的 ;
两个栈的下推自动机 与...图灵机 等价 , 其计算能力已经达到计算的极限 ;
\rm n
(
n > 2
) 个栈的下推自动机的计算能力 , 与
2
个栈的下推自动机计算能力是相同的 ;