计算机数学基础第七章.pptVIP

计算机科学的数学基础 第七章图灵机 图灵机的基本模型 图灵机的基本模型： 图灵机的数学模型 一个图灵机M = (Q, ?, Γ, δ, q0, B, F)，其中： Q是状态的有穷集； Γ是所允许的带符号的有穷集； B是Γ中的一个符号，表示空白； ?是输入符号集，即不包含B的Γ的子集； 转换函数δ：Q×Γ ? Q×Γ×{L, R} ； q0是开始状态， q0在Q中； F?Q是终止状态集。 瞬时描述 用?1q?2表示图灵机M的一个瞬时描述。这里q ? Q，即M的当前状态；?1?2 ? Γ*，即带上直至最右的非空白符号的内容，?1位于磁头左边，?2位于磁头右边（注意空白符号B可以出现在?1?2中）。 为了避免混淆假定Q和Γ是不相交的。 最后，带磁头被认为正在扫描?2的最左字符，或当?2＝ε时，磁头正扫描空白符号。 瞬时描述——TM动作的描述 设ID = X1…Xi－1qXi…Xn为一个瞬时描述。 图灵机所接受的语言 M所接受的语言，表示为L(M)，是?*中的那些字的集合：M从初始状态q0开始阅读这个字，这个字使得M进入终止状态。形式上， L(M) = {w | w??*且?p?Q：q0w ├* ?1p?2}。 可计算语言和函数 被图灵机所接受的语言称为递归可枚举集(r.e.s)。这种语言的字可以用一个图灵机枚举，因此称为“可枚举的”。 递归可枚举集合类的一个真子类，称为递归集合，是那些至少有一个对所有输入都停机的图灵机来接受的语言。 除作为语言接收器，TM可做从In到I的函数计算。若M?TM，L(M)为{q00i110i2…10in├*0mp, p?F}，则M定义了 函数f：In ? I。 图灵机的构造技术 有限控制器的存储：用有限控制器来保存有限数量的信息。 为此，可把状态写成对偶，一个元素行使控制，而另一个元素存储符号。 必须强调，这样安置仅仅为了概念上的目的，并未对图灵机的定义作任何修改。 图灵机的构造技术 多道：对任何有穷的k，TM的带被分成k道。实际是把带符号看成k元组，一个分量对应一道。 图灵机的构造技术 查询符号：在带上引用一个保存一个空白或√的额外道。当图灵机在其各次比较的一次比较中考察了√下面的符号后，√便出现。 移动：用有限控制器存储可把非空白符号右移有穷多个单元的方法在其带上留空。 子程序：和程序一样，可以使用子程序来定义基本的处理。这时相当于一个图灵机调用另外一个图灵机。因此可以用若干个图灵机来构造一个新的图灵机。 图灵机的修改 双向无穷带 多带图灵机 不确定的图灵机 多维图灵机 多头图灵机 离线图灵机 所有这些图灵机的修改都等价于原型。 双向无穷带图灵机 双向无穷带TM是带的左右两端都是无穷的。 定理7.1：L被双向无穷带的TM所识别，当且仅当L被单向无穷带的TM所识别。 证明：用两道的单向无穷带就可以模拟双向无穷带。 多带图灵机 一台多带图灵机，由有限控制加上k个带和k个带头组成，每条带的两个方向都是无穷的。 每个带头都是独立的。 多带图灵机 定理7.2：如果一个语言被一个多带图灵机所接受，它也被单带图灵机所接受。 证明：令L被具有k条带的图灵机M1所接受。能够构造一具有2k道（两道对应着M1的每一条带）的单带图灵机M2来模拟M1。 不确定的图灵机 不确定TM对给定状态和带符号有多个动作选择。 定理7.3：若L被不确定TM M1接受，则L被某个确定TM M2接受。 证明：对确定状态和带符号， M1的动作选择可编号为1, …, r，r 为最大选择个数，则任何长度n的动作选择序列对应一个n位r进制数。 M2用三带模拟M1。带1保存输入。带2系统产生r进制数。对带2上每个序列，M2复制输入到带3，在带3上按该序列模拟M1。显然L(M2) = L。 多维图灵机 多维图灵机的带由k维无穷单元组成，带头可沿k个轴中的一轴移动。 定理7.4：若L被二维图灵机M2所接受，则L被某个一维图灵机M1所接受。 多维图灵机的带由k维无穷单元组成，带头可沿k个轴中的一轴移动。 定理7.4：若L被二维图灵机M2所接受，则L被某个一维图灵机M1所接受。 多头图灵机 k头TM有固定数目k个带头，带头各自独立。 定理7.5：如果L被某个k头TM M1接受，则L也被某个单头TM M2所接受。 证明：这个证明类似于定理7.2对多带图灵机的证明。M2在它的带上有k+1道，最后一道含有M1的带，并且对1 ≤ i ≤ k，第i道的带有一个标志来指示第i个带头的位置。 离线图灵机 一个离线TM是一个输入带是只读的多带TM 。通常输入端点标志括起来，左边是￠，而右边是＄。这种TM不允许输入带头移出￠和＄之间的区域。 显然这种离线TM只是多带图灵机的特殊情况，所以不会比已经考虑过的任何模型功能更强。