【计算理论】图灵机 ( 图灵机特点 | 自动机特点 | 数的扩张 | 计算模型的扩张 )

文章目录

一、图灵机特点

二、自动机特点

三、数的扩张

四、计算模型的扩张

一、图灵机特点

图灵机特点 :

① 读写头特点 : 图灵机 既可以读 , 也可以写 ;

② 移动方向 : 图灵机的读写头既可以向左移动 , 又可以向右移动 , 可以 双向移动 ;

③ 带子长度 : 图灵机的带子是 无限长的 ;

④ 停机判定 : 图灵机一旦 到达接受状态 , 立刻停机 ;

二、自动机特点

自动机特点 :

① 读头特点 : 自动机只能读 , 不能写 ;

② 移动方向 : 自动机的读头只能向右进行移动 ;

③ 带子长度 : 自动机的带子是输入字符串长度 ;

④ 停机判定 : 自动机在计算过程中 , 某个时刻可能到达接受状态 , 但是不会停机 , 字符串读取完成后 , 才会停机 , 停机状态不一定是接受状态 ;

三、数的扩张

自然界中存在的数字 , 是自然数 ;

自然数 通过 加减运算 扩张到 整数 ;

整数 通过 乘除运算 扩张到 有理数 ;

有理数 通过 极限运算 扩张到 实数 ;

任何一个有理数的序列 a 1 , a 2 , ⋯   , a n \rm a_1 , a_2, \cdots , a_na

1

,a

2

,⋯,a

n

 如果收敛的话 , 该数列的极限 , 一定是一个实数 , 任何一个实数 , 都可以写成一个有理数序列的极限 ;

四、计算模型的扩张

下面开始讨论计算模型的扩张

计算模型从最简单的模型 确定性有限自动机 , 一步步进行扩张 , 最后得到计算的极限 图灵机 ;

下图是 确定性有限自动机 的示意图 , 带子上是输入字符 , 矩形框中是当前状态 , 读头指向带子上的字符 ;

下图是 下推自动机 , 是在 确定性有限自动机 的基础上 , 加上了一个 存储能力无穷 的 栈 , 栈的特点是 后进先出 ;

在上述 1 11 个栈的下推自动机 基础上 , 再加一个栈 , 两个栈的下推自动机 , 与 图灵机 的计算能力是等价的 ;

两个栈的下推自动机 与 图灵机 等价 , 其计算能力已经达到计算的极限 ;

n \rm nn ( n > 2 n > 2n>2 ) 个栈的下推自动机的计算能力 , 与 2 22 个栈的下推自动机计算能力是相同的 ;