第二讲-图灵机模型.pptVIP

第2讲 图灵机模型 图灵机(Turing machine)是由图灵（Alan Mathisom Turing）在1936年提出的，它是一 个通用的计算模型。 通过研究图灵机，来研究递归可枚举集（recursively enumerable set）和部分地 归函数（partial recursive function） 。 对算法和可计算性进行研究提供形式化描述工具。 主要内容、重难点 主要内容 图灵机作为一个计算模型，它的基本定义，即时描述，图灵机接受的语言；图灵机的构造技术；图灵机的变形；Church-Turing论题；通用图灵机。可计算语言、不可判定性、P-NP问题)。 重点 图灵机的定义、图灵机的构造。 难点 图灵机的构造。 2.1 基本概念 图灵提出图灵机具有以下两个性质 具有有穷描述。 过程必须是由离散的、可以机械执行的步骤组成。 基本模型包括 一个有穷控制器。 一条含有无穷多个带方格的输入带。 一个读头。 一个移动将完成以下三个动作 改变有穷控制器的状态； 在当前所读符号所在的带方格中印刷一个符号； 将读头向右或者向左移一格。 直观物理模型 2.1.1 基本图灵机 图灵机（Turing machine）/基本的图灵机 M=(Q, ∑, Γ, δ,q0 , B , F) ， Q为状态的有穷集合，?q∈Q，q为M的一个状态； q0∈Q，是M的开始状态，对于一个给定的输入串，M从状态q0启动，读头正注视着输入带最左端的符号； 2.1.1 基本图灵机 F?Q，是M的终止状态集，?q∈F，q为M的一个终止状态。与FA和PDA不同，一般地，一旦M进入终止状态，它就停止运行； Γ为带符号表（tape symbol），?X∈Γ，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上； 2.1.1 基本图灵机 B∈Γ，被称为空白符（blank symbol），含有空白符的带方格被认为是空的； ∑?Γ-{B}为输入字母表，?a∈∑，a为M的一个输入符号。除了空白符号B之外，只有∑中的符号才能在M启动时出现在输入带上； 2.1.1 基本图灵机 δ：Q×Γ?Q×Γ×{R, L}，为M的移动函数（transaction function）。 δ(q , X)=(p , Y, R)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向右移一格； δ(q , X)=(p , Y , L)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向左移一格。 例子2-1说明 例 2-1 设M1=({q0, q1, q2},{0, 1},{0, 1, B},δ,q0 , B ,{q2})，其中δ的定义如下，对于此定义，也可以用表2-1表示。 δ(q0, 0)= (q0, 0, R) δ(q0, 1)= (q1, 1, R) δ(q1, 0)= (q1, 0, R) δ(q1, B)= (q2, B, R) 例子2-1说明 2.1.1 基本图灵机 即时描述(instantaneous description, ID) α1α2∈Γ*，q∈Q，α1qα2称为M的即时描述 q为M的当前状态。 α1α2为M的输入带最左端到最右的非空白符号组成的符号串或者是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串 M正注视着α2的最左符号。 2.1.1 基本图灵机 设X1X2…Xi-1qXiXi+1…Xn是M的一个ID 如果δ(q, Xi)=(p, Y, R)，则，M的下一个ID为X1X2…Xi-1YpXi+1…Xn 记作 X1X2…Xi-1qXiXi+1…Xn├M X1X2…Xi-1YpXi+1…Xn 表示M在ID X1X2…Xi-1qXiXi+1…Xn下，经过一次移动，将ID变成X1X2…Xi-1YpXi+1…Xn 。 2.1.1 基本图灵机 如果δ(q, Xi)=(p, Y, L)则， 当i≠1时，M的下一个ID为 X1X2…pXi-1YXi+1…Xn 记作 X1X2…Xi-1qXiXi+1…Xn├M X1X2…pXi-1YXi+1…Xn 表示M在ID X1X2…Xi-1qXiXi+1…Xn下，经过一次移动，将ID变成X1X2…pXi-1YXi+1…Xn； 2.1.1 基本图灵机 ├M是Γ*QΓ*×Γ*QΓ*上的一个二元关系 ├Mn表示├M的n次幂：├Mn =(├M)n ├M+表示├M的正闭包：├M+ =(├M)+ ├M*表示├M的克林闭包：├M* =(├M)* 在意义明确时，分别用├、├n 、├+、├*表示├M 、├Mn、├M+、├M*。 2.1.1 基本图灵机 例 2-2. 例 2-1所给的M