【计算理论】图灵机 ( 接受状态作用 | 格局 | 图灵机语言 | 图灵机设计复杂性 )

文章目录

一、接受状态作用

二、格局

三、图灵机语言

四、图灵机设计复杂性

一、接受状态作用

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

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

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

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

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

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

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

二、格局

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

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

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

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

三、图灵机语言

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

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

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

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

四、图灵机设计复杂性

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

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

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

设计一个图灵机 M 2 \rm M2M2 , 认识一种特定语言 , 该语言由 0 00 组成 , 字符串的长度是 2 n \rm 2^n2

n

 个 , n = 0 , 1 , 2 , ⋯ \rm n = 0, 1, 2, \cdotsn=0,1,2,⋯ ;

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

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

i

b

j

c

k

:i×j=k} ;