[工学]计算引论2 计算模型.ppt

计算引论 第二章 计算模型 主要内容 n 图灵机模型 n RAM机 n RASP机 n Lambda演算模型 2.1 图灵机模型 n图灵机组成： n线性带（读写介质） n基本符号表（表示信息） n信息处理状态 n信息处理动作（静止，左、右移） n信息处理方法（规则，即程序） 状态控制器 q0 q5 q4 q3 q1 q2 读写头 线性带 n定义：图灵机的M(Q, , , , B, q0, F)，其中： n Q 为状态的有限集合； n 为有限字母表，为输入符号集； n 为线性带符号集， ； n B空符号，B，B ； n q0Q为初始状态 n FQ是终止状态集; n ：Q Q(L, R, S)为转移函数。 n例1：(q, a) = (p, (b, L) 说明：若当前状态为q，读写头读取a，经过动 作后，图灵机状态改为p，线性带上a改变为b，同 时读写头左移一格。 n例2：(q, a) = (p, (a, R) 说明：若当前状态为q，读写头读取a，经过动 作后，图灵机状态改为p，线性带上a不改变，同 时读写头右移一格。 n例3：(q, a) = (q, (B, S) 说明：当前状态为q，读写头读取a，经过动作 后，图灵机状态不改变，仍为q，线性带上a被清 空为null，同时读写头不动。 n例4：有图灵机M定义如下： M=(q0,q1,q2, 0,1, 0,1,B, , q0, B, q2), 其中定义为： n(q0, 0) = (q0, 0, R), n(q0, 1) = (q1, 1, R), n(q1, 0) = (q1, 0, R), n(q1, B) = (q2, B, R). n表示： n图 n表 q0q1q2 0（0,R ） 1（1,R ） 0（0,R ） B（B,R ） n识别由0和1组成的且只含有一个1的字符 串。 n格局：机器的状态的表示，由当前状态、当前带 内容、读写头位置组成。属于(*Q*)。 n如（u，q，v）简记为：uqv. u v n初始格局：q0，*; n终止格局： n接受格局：qf, ,*; n停机格局：转换函数无定义。 n格局转换 ： 图灵机M根据转换函数定义合法地从格局C1进 入格局C2，则称格局C1产生格局C2，称这两 个格局之间有二元关系 。记为C1 C2。 n计算： 计算是从图灵机的初始格局到终止格局 按照动作函数规定的规则进行的一系列转 换的序列。 n例5：设计一台接受0与1出现次数相同且0 先出现的串0011的图灵机。 基本思路：读头将第一个0改为x，右移，把找到 的第一个1改为y，然后退回去直到遇到第一个x ，再右移把遇到的第一个0改为x，右移，把找到 的第一个1改为y，如此反复直读头指向空白B为 止。 n给出串0011的识别过程。 q00011 xq1011 x0q111 xq20y1 q2x0y1 xq00y1 xxq1y1 xxyq11 xxq2yy xq2xyy xxq0yy xxyq3y xxyyq3B xxyyBq4B n给出串0010的识别过程： q00010 xq1010 x0q110 xq20y0 q2x0y0 xq30y0 xxq1y0 xxyq10 xxy0q1B 拒绝停机 例6：设计一个图灵机，计算二个自然数m、n的 减法。 思路 ：整数n用0n表示。开始时，带上符号为 0m10n，结束时，带上符号为0。每当在1的左边 将一个0改变为B，就在1的右边将一个0改为1， 若1的右边无0时，再将左边改为B的0恢复回 来。 例7：设计一个图灵机，计算自然数n的以2为底的对 数。 思路：用一进制表示输入和输出值。an表示输入n, bm表示输出m.从左到右扫描带，把所碰到的a划掉 一个，留一个，并将计数器加1。重复此过程，直 至a不复存在。用字符c表示划掉的字符。 n例8：设有图灵机M =(q0,q1, 0,1, 0,1,B, , q0, B, ), 其中转换函数定义为： (q0,0) = (q1,（0,R）), (q0,1) = (q1,（1,R)）, (q0,B) = (q1,（B, R)）, (q1,0) = (q0, 0, L), (q1, 1) = (q0, 1, L), (q1, B) = (q0, B, L). n 考虑输入串01，10， n对输入串的不接受： n拒绝状态 n不停机 n图灵机的停机问题 n图灵机根据程序处理初始格局，有的导致停 机,有的导致无限格局序列。 n是否存在一个算法，能判定任意给定的图灵 机对任意的初始格局是否会导致停机。 n停机问题是不可判定的。已经证明,这样的算 法是不存在的。 n停机问题是研究不可判定问题的基础。把一 个问题的判定归结为停机问题 n图灵机M识别的语言： 图灵机M能够接受停机的所有输入 信息串的集合就是M能识别的语言。 n定义1（可识别）：如果有图灵机识别一 个语言，则称该语言是图灵可识别的。 又称为递归可枚举语言的。 n定义2（可判定）：如果有图灵机对所有 输入都停机，则称图灵可判定。这样的 语言称为图灵可判定的。简称可判定。 n定理： 图灵可判定语言都是图灵可识别的。 图灵可识别的不都是图灵可判定的。 n非确定图灵机 n 定理：每一个非确定图灵机都有一个与 之等价的确定图灵机。 n推论1： 一个语言是图灵可识别的，当且仅当有 确定图灵机识别它。 n推论2：一个语言是可判定的，当且仅当 有非确定图灵机判定它。 n多带图灵机 n定理： 对任意一个多带图灵机，存在一个 单带图灵机与之等价。 n通用图灵机：它接受任意一台图灵机 M 的编码，