计算理论导引 3 丘奇-图灵论题.ppt

朴秀峰 xfpiao@126.com 引言 什么是计算？ 计算机的基本能力和局限性是什么？ 引言 什么是计算 什么是操作系统 基本上解决 什么internet ? 什么是数据库 什么是数据仓库 还在争论 什么是数据网格 解决方法， 给出大众能理解的代表 引言 解决的办法， 给出一个代表 什么是 3的倍数 { 3N |N=1,2,3}, {x| x mod 3 =0} 代表元 ：3 什么是操作系统 代表元：Windows, Unix 什么internet 代表元：大众理解：Web ， IE 什么是计算? 多个模型；代表元：图灵机, 或 递归函数论 引言 引言 引言 图灵机（Turing Machine，TM），是计算机的一种简单的数学模型。 历史上，冯?诺曼计算机的产生就是由图灵机诱发的。 丘奇—图灵论题：一切合理的计算模型都等同于图灵机. 主要内容 3.1 丘奇—图灵论题 3.1.1 图灵机的形式化定义 3.1.2 图灵机的例子 3.2 图灵机的变形 3.2.1 多带图灵机 3.2.2 非确定型图灵机 3.2.3 枚举器 3.2.4 与其他模型的等价性 3.3 算法的定义 3.3.1 希尔伯特问题 3.3.2 描述图灵机的术语 3.1 图灵机(Turning Machine) 图灵机 图灵机 图灵机与有限自动机 图灵机 考虑图灵机 M1，它检查语言 B = { w#w | w∈{0,1}* } 的成员关系。即设计 M1，使得如果输入是 B 的成员，它就接受，否则拒绝。 M1=“对于输入字符串 w (1) 在 # 两边对应的位置上来回移动，检查这些对应位置是否包含相同的符号，如不是，或者没有 #，则拒绝，为跟踪对应的符号，消去所有检查过的符号。 (2) 当 # 左边的所有符号都被消去时，检查 # 右侧是否还有符号，如果有则拒绝，否则接受。” M1 的运行示意图 M1 的运行示意图 M1 的运行示意图 M1 的运行示意图 M1 的运行示意图 M1 的运行示意图 M1 的运行示意图 图灵机的形式化定义 图灵机的计算方式 开始时，M 以最左边的 n 个带方格接收输入w=w1w2…wn ? ?*，带的其余部分保持空白(即填以空白符)，读写头从最左边的带方格开始运行，注意 ? 不含空字符，故出现在带上的第一个空字符表示输入的结束。 M 开始运行后，计算根据转移函数所描述的规则进行，如果 M 试图将读写头从带的最左端再向左移出，即使转移函数指示的是 L，读写头也停在原地不动。计算一直持续到它进入接受状态或拒绝状态，此时停机，如果二者都不发生，则 M 将永远运行下去。 图灵机的格局 图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局。 对于状态 q 和带字母表 ? 的两个字符串 u 和 v，以 uqv 表示如下格局：当前状态是 q，当前带上的内容是 uv，读写头的当前位置是 v 的第一个符号，带上 v 的字符最后字符以后的符号都是空白符。 例如，1011q701111 图灵机计算方式的形式化 如果图灵机能合法地从格局 C1 一步进入 C2，则称格局 C1产生格局 C2。 设 a, b 和 c 是 ? 中的符号，u 和 v 是 ?* 中字符串，qi 和 qj是状态，则 uaqibv 和 uqjacv 是两个格局。如果转移函数满足? (qi , b) = (qj , c, L)，则说uaqibv 产生和 uqjacv 。 M 在输入 w 上的起始格局是格局 q0w，表示机器处于起始状态 q0，并且读写头处于带子的最左端位置，在接受格局里，状态是 qaccept ，在拒绝格局里，状态是 qreject。接受和拒绝状态都是停机状态，它们都不再产生新的格局。 由于图灵机只在接受或拒绝状态下才停机，可以等价地将状态转移函数简化 ? : Q ×?? Q × ? ×{ L, R } 其中 Q 是取消 qaccept 和qreject 的 Q。 图灵机计算方式的形式化 图灵机 M 接受输入 w ，如果存在格局的序列 Cl, C2, …, Ck使得： (1) Cl 是 M 在输入 w 上的起始格局； (2) 每一个Ci 产生 Ci +1； (3) Ck 是接受格局。 M 接受的字符串的集合称为 M 的语言，或被 M 识别的语言，记为 L(M)。 图灵机的形式化定义 图灵机的形式化定义 图灵机举例 图灵机举例 图灵机的例子 每重复一次第 1 步，消去了一半个数的 0。由于在第 1