形式语言学ch9.pdf

第9章图灵机导引 图灵机(Turing machine)是由图灵(Alan MathisomTuring) 在1936年提出的，它是一个通用的计算模型。 通过研究TM，来研究递归可枚举集(recursively enumerable set)和部分递归函数(partial recursive function) 。 对算法和可计算性进行研究提供形式化描述工具。 第9章图灵机 有效过程(effective procedure)与算法(algorithm)。 希尔伯特纲领: 计划构造一个可以判定所有数学命题真假的算法 1931年，奥地利25岁的数理逻辑学家哥德尔(Kuri Gödel) 发表了著名的不完整性理论。 具有有穷描述的过程是可数无穷多的，但函数却是不可 数无穷多的。 世界上存在着许多的问题和函数，是无法用具有有穷描 述的过程完成计算的——是不可计算的(incomputable) 。 图灵提出TM 的目的是为了对有效的计算过程，也就是算 法，进行形式化的描述。 1 第9章图灵机 主要内容 TM作为一个计算模型，它的基本定义，即时描述， TM 接受的语言；TM 的构造技术；TM 的变形； Church-Turing论题；通用TM 。可计算语言、不可判 定性、P-NP 问题) 。 重点 TM 的定义、构造。 难点 TM的构造。 9.1 基本概念 图灵提出TM具有以下两个性质 具有有穷描述。 过程必须是由离散的、可以机械执行的步骤组成。 基本模型包括 一个有穷控制器。 一条含有无穷多个带方格的输入带。 一个读头。 2 直观物理模型 9.1 基本概念 一个移动将完成以下三个动作： 改变有穷控制器的状态； 在当前所读符号所在的带方格中印刷一个符 号； 将读头向右或者向左移一格。 3 9.1.1 基本TM 图灵机(Turing machine)/基本的图灵机 TM M=(Q, ∑, Γ, δ,q , B , F) ， 0 Q为状态的有穷集合，∀q ∈Q，q为M的一个状态； q ∈Q，是M的开始状态，对于一个给定的输入串，M从 0 状态q0启动，读头正注视着输入带最左端的符号； 9.1.1 基本TM F⊆Q，是M的终止状态集，∀q ∈F，q为M的一个终止状 态。与FA和PDA不同，一般地，一旦M进入终止状态， 它就停止运行。 Γ为带符号表(tape symbol)，∀X ∈Γ，X 为M 的一个带 符号，表示在M 的运行过程中，X可以在某一时刻出现 在输入带上； 4 9.1.1 基本TM B ∈Γ，被称为空白符(blank symbol)，含有空白符的带 方格被认为是空的； ∑⊆Γ-{B}为输入字母表，∀a ∈∑，a为M 的一个输入符 号。除了空白符号B之外，只有∑中的符号才能在M启 动时出现在输入带上； 9.1.1 基本TM δ：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所