文章目录

• 一、接受状态作用
• 二、格局
• 三、图灵机语言
• 四、图灵机设计复杂性

一、接受状态作用

---

自动机 / 图灵机 与 现实计算 的区别是 现实计算中 没有 接受状态 概念 ,

自动机 / 图灵机 的目的是 将计算转为一个集合 , 从数学角度研究计算 ;

设置了 接受状态 概念 , 可以将字符串分为 接受字符串 , 非接受字符串 , 两部分 ;

接受字符串可以组成一个集合 , 集合组成的语言 , 刚好对应 计算模型 ;

此时就可以 将计算转为集合 , 方便进行数学证明 ;

图灵机 一旦达到 接受状态 , 自动停机 ;

自动机 即使达到了接受状态 , 也要将所有输入字符读取完毕 , 然后才停机 ;

二、格局

---

格局 Configuration , 格局是给图灵机照一个 快照 , 下图就是图灵机在计算过程中 , 某一个时刻的快照 ;

将图灵机计算过程 , 每个步骤都照一份快照 , 通过轨迹将这些快照联系到一起 , 就可以得到一个数据结构 ,

上述格局可以记作 $00\mathrm{q}1\mathrm{B}$ , 该写法表示 与 某个格局 ( 快照 ) 一一对应 ;

在 图灵机中 , 读头指向 $1$ , 就将状态写在 $1$ 的左边 ;

三、图灵机语言

---

给定一个字符串 , 将字符串写在带子上 , 让图灵机从开始状态 , 开始位置进行计算 ,

如果在计算过程中的 某个时刻 , 图灵机进入接受状态 , 那么称 该图灵机是接受这个字符串的 ;

将图灵机 $\mathrm{M}$ 所 接受的所有字符串 $\mathrm{w}$ 都放在一起 , 组成一个 集合 $\mathrm{L}$ , 则该集合就是 图灵机 $M$ 的语言 ;

使用符号化表示为 : $\mathrm{L}(\mathrm{M})=\{\mathrm{w}|\mathrm{M}接受\mathrm{w}字符串\}$

四、图灵机设计复杂性

---

图灵机设计是一个很复杂的工程 , 与设计电路等同 , 需要注意很多微妙的地方 ;

图灵给算法提供了一个严格的数学定义 , 如果要给一个算法提供一个严格的数学证明 , 必须将该算法写出来 , 即写出该算法对应的图灵机 , 设计一个简单算法对应的图灵机很复杂 ;

这里希望严格证明算法 , 但尽量避免设计图灵机 ;

设计一个图灵机 $\mathrm{M}2$ , 认识一种特定语言 , 该语言由 $0$ 组成 , 字符串的长度是 $2^{\mathrm{n}}$ 个 , $\mathrm{n}=0,1,2,\cdots$ ;

设计一个图灵机 , 认识一种特定语言 , $\mathrm{B}=\{\mathrm{w}\#\mathrm{w}|\mathrm{w}是0和1组成的字符串\}$ ;

设计一个图灵机 , 作乘法运算 , 语言为 $\mathrm{C}=\{{\mathrm{a}}^{\mathrm{i}}{\mathrm{b}}^{\mathrm{j}}{\mathrm{c}}^{\mathrm{k}}:\mathrm{i}\times \mathrm{j}=\mathrm{k}\}$ ;

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的【计算理论】图灵机 ( 接受状态作用 | 格局 | 图灵机语言 | 图灵机设计复杂性 )的全部内容，希望文章能够帮你解决所遇到的问题。

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