文章目录

• 一、图灵机特点
• 二、自动机特点
• 三、数的扩张
• 四、计算模型的扩张

一、图灵机特点

---

图灵机特点 :

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

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

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

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

二、自动机特点

---

自动机特点 :

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

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

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

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

三、数的扩张

---

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

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

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

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

任何一个有理数的序列 ${\mathrm{a}}_1,{\mathrm{a}}_2,\cdots ,{\mathrm{a}}_{\mathrm{n}}$ 如果收敛的话 , 该数列的极限 , 一定是一个实数 , 任何一个实数 , 都可以写成一个有理数序列的极限 ;

四、计算模型的扩张

---

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

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

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

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

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

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

$\mathrm{n}$ ( $n>2$ ) 个栈的下推自动机的计算能力 , 与 $2$ 个栈的下推自动机计算能力是相同的 ;

总结

以上是生活随笔为你收集整理的【计算理论】图灵机 ( 图灵机特点 | 自动机特点 | 数的扩张 | 计算模型的扩张 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。