文章目录
- 一、接受状态作用
- 二、格局
- 三、图灵机语言
- 四、图灵机设计复杂性
一、接受状态作用
自动机 / 图灵机 与 现实计算 的区别是 现实计算中 没有 接受状态 概念 ,
自动机 / 图灵机 的目的是 将计算转为一个集合 , 从数学角度研究计算 ;
设置了 接受状态 概念 , 可以将字符串分为 接受字符串 , 非接受字符串 , 两部分 ;
接受字符串可以组成一个集合 , 集合组成的语言 , 刚好对应 计算模型 ;
此时就可以 将计算转为集合 , 方便进行数学证明 ;
图灵机 一旦达到 接受状态 , 自动停机 ;
自动机 即使达到了接受状态 , 也要将所有输入字符读取完毕 , 然后才停机 ;
二、格局
格局 Configuration , 格局是给图灵机照一个 快照 , 下图就是图灵机在计算过程中 , 某一个时刻的快照 ;
将图灵机计算过程 , 每个步骤都照一份快照 , 通过轨迹将这些快照联系到一起 , 就可以得到一个数据结构 ,
上述格局可以记作
, 该写法表示 与 某个格局 ( 快照 ) 一一对应 ;
在 图灵机中 , 读头指向
, 就将状态写在
的左边 ;
三、图灵机语言
给定一个字符串 , 将字符串写在带子上 , 让图灵机从开始状态 , 开始位置进行计算 ,
如果在计算过程中的 某个时刻 , 图灵机进入接受状态 , 那么称 该图灵机是接受这个字符串的 ;
将图灵机
所 接受的所有字符串
都放在一起 , 组成一个 集合
, 则该集合就是 图灵机
的语言 ;
使用符号化表示为 :
四、图灵机设计复杂性
图灵机设计是一个很复杂的工程 , 与设计电路等同 , 需要注意很多微妙的地方 ;
图灵给算法提供了一个严格的数学定义 , 如果要给一个算法提供一个严格的数学证明 , 必须将该算法写出来 , 即写出该算法对应的图灵机 , 设计一个简单算法对应的图灵机很复杂 ;
这里希望严格证明算法 , 但尽量避免设计图灵机 ;
设计一个图灵机
, 认识一种特定语言 , 该语言由
组成 , 字符串的长度是
个 ,
;
设计一个图灵机 , 认识一种特定语言 ,
;
设计一个图灵机 , 作乘法运算 , 语言为
;
