计算理论(哈工大 第一章 ).pdf

Chapter One 计算模型 李建中 海量数据计算研究中心 计算机科学与技术学院 Outline 1.1 符号行与编码 1.2 确定图灵机 1.3 多带图灵机 1.4 不确定图灵机 1.5 图灵机的变形 1.6 通用的图灵机 1.1 符号行与编码 1.2 确定图灵机 1.3 多带图灵机 1.4 不确定图灵机 1.5 图灵机的变形 1.6 通用的图灵机 参考书：计算复杂性导论 字母表、符号行  字母表  字母表是一个满足下列条件的优先符号集合: 两个由中符号组成的符号序列等同当且仅当其符号 个数相等且对应符号相同。 例. {0, 1}、{00, 01}、{1, 11}哪个可以做字母表？哪个不可以？  字母表{0,1}  经常只考虑{0,1}上的符号行—二元符号行  其他符号行都能通过编码转换为二元符号行  符号行  字母表的有限个符号的序列称为上的符号行  符号行x的长度|x |=x 中的符号个数, 空行的长度为0. 符号行的运算与语言 • 连接运算  符号行x和y 的链接：x y =xy  连接运算满足结合律：x(yz )=(xy)z • Kleen闭包  语言A和B的连接A B={xy |x A ，y B } 0 n n-1  A ={}，A =AA  n *  Kleen闭包A =A n 0 *  字母表的Kleen闭包 是上全部符号行的集合  语言和语言类 *  语言: L , 的符号行组成的集合. *  语言类: {L | L }, 由语言组成的集族. 1.1 符号行与编码 1.2 确定图灵机 1.3 多带图灵机 1.4 不确定图灵机 1.5 图灵机的变形 1.6 通用的图灵机 参考书：计算复杂性导论 确定图灵机的定义 …… y …… B B x1 x2 x3 x4 x5 B B q p 定义1. 确定图灵机是一个系统M=(Q, , , , q , B, F)， 0 Q : 有穷状态集合  : 有穷输入符号集合  : 有穷带符号集合,  q0 : 起始状态 B  － : 空白符号 FQ : 终