计算理论 第3章 丘奇-图灵论题

主要内容 3.1 图灵机 3.2 图灵机的变形 3.3 算法的定义 3.1.1 图灵机形式化定义 3.1.2 图灵机例子 3.1 图灵机 3.1.1 图灵机形式化定义 3.1.2 图灵机例子 3.2 图灵机的变形 3.2.1 多带图灵机 3.2.2 非确定型图灵机 3.2.1 枚举器 3.2.1 与其他模型的等价性 3.3 算法的定义 3.3.1 希尔伯特问题 3.3.2 描述图灵机的术语

§3.1 图灵机 What do we really know? 我们是否能确定某个语言是正则的或CFL？ 我们知道： §3.1 图灵机 What do we really know? 我们是否能确定某个语言是正则的或CFL？ 我们知道： { 1x | x = 0 mod 7 } is regular（比较规律，可有限描述） { 1x | x is prime素数 } is not regular （比较复杂，现在数学家还不能简单描述） But what about { 1x | x and x+2 are prime }? This is (yet) unknown. 说明：对语言的描述和判定是个需要研究的问题

§3.1 图灵机 计算机科学历史上关于概念的争论 什么是计算 什么是操作系统 基本上解决 什么internet ? 什么是数据库 §3.1 图灵机 计算机科学历史上关于概念的争论 什么是计算 什么是操作系统 基本上解决 什么internet ? 什么是数据库 什么是数据仓库 还在争论 什么是数据网格 解决方法， 给出大众能理解的代表

§3.1 图灵机 计算机科学历史上关于概念的争论 解决的办法， 给出一个代表 §3.1 图灵机 计算机科学历史上关于概念的争论 解决的办法， 给出一个代表 什么是 3的倍数 { 3N |N=1,2,3}, {x| x mod 3 =0} 代表元 ：3 什么是操作系统 代表元：Windows, Unix 什么internet 代表元：大众理解：Web ， IE 什么是计算? 多个模型；代表元：图灵机, 或 递归函数论

§3.1 图灵机 在还没有计算机的时候， 凭想象力把后来出现的 把计算机的理论模型建立起来了。 1936年 想得如此周到、严密 §3.1 图灵机 在还没有计算机的时候， 凭想象力把后来出现的 把计算机的理论模型建立起来了。 1936年 想得如此周到、严密 好像从高度文明的外星来的文化使者 Jack St. Clair Kilby 1958年第一块集成电路 ； Lady Ada Augusta Lovelace奥古斯塔艾达，拉弗拉斯伯爵夫人，英国数学家，世界上第一个计算机程序员。 爱德华•罗伯茨于1974年推出最早基于英特尔微处理器的个人电脑Altair 8800，虽然，Altair的生命非常短暂，却从此点燃了PC创新之火，并激发了乔布斯、盖茨等无数爱好者。作为第一个雇佣比尔•盖茨和保罗•艾伦的雇主，对于微软的地步起到了至关重要的作用。罗伯茨无愧于“PC之父”的称号。 斯蒂夫·沃兹尼亚克一手设计了苹果苹果I型和Ⅱ型电脑，带动了全球个人电脑普及应用浪潮，并迫使IBM PC于1981年面世，从此改变了整个计算机业的面貌。1977年，世界上只有少数人具备硬件、软件、电子设备和电路板布线等方面的知识，同时也只有少数人了解苹果Ⅱ计算机的制造技术、艺术特点，并欣赏它的设计优点，史蒂夫·沃兹尼克是个当之无愧的奇才。尽管他的贡献被某些人看作在适当的时间、适当的地点、整合适当的理念，恰好与因技术迅速发展而开始大量生产的电脑完美地相符，但沃兹的独创性和不懈的创造性使他成为唯一适合获得“推动PC革命”的头衔。他与斯蒂夫·乔布斯一起创办了苹果电脑。 现时他仍然是一位小学教师。

§3.1 图灵机 Alan M. Turing (1912–1954) In 1936, Turing introduced his abstract model for computation in his article “On Computable Numbers,”. At the same time, Alonzo Church published similar ideas and results. 殊途同归 Turing model 成为理论计算科学的标准模型 standard model

§3.1 图灵机 图灵机（Turing Machine，TM），是计算机的一种简单的数学模型。 §3.1 图灵机 图灵机（Turing Machine，TM），是计算机的一种简单的数学模型。 历史上，冯•诺曼计算机的产生就是由图灵机诱发的。 丘奇—图灵论题：一切合理的计算模型都等同于图灵机.

类型 文 法 结 构 产 生 式 形 式 限 制 条 件 0 短语结构文法 α→β α∈Ｖ+,β∈Ｖ* Phrase Structure 上下文有关文法 α1Aα2→α1βα2 |α1βα2|≥|α1Aα2| 1 Context Sensitive α1，α2∈Ｖ* （CSG ） A∈ＶＮ , β∈Ｖ+ 上下文无关文法 A→α A∈ＶＮ,α∈Ｖ* 2 Context Free （CFG） 正 右线性文法 A→xB，C→y A,B,C∈ＶＮ 3 规 文 左线性文法 A→Bx，C→y x,y∈ＶT* 法

§3.1 图灵机 0型语言 ———图灵机 1型语言(CSL) ———线性界限自动机 2型语言(CFL) ———下推自动机 §3.1 图灵机 0型语言 ———图灵机 1型语言(CSL) ———线性界限自动机 2型语言(CFL) ———下推自动机 3型语言(正规集)——有限自动机 图灵机所定义的语言类---递归可枚举集合 图灵机所计算的整数函数类---部分递归函数 以图灵机为模型,研究问题的可计算性，即确定该问题是可计算的、部分可计算的，还是不可计算的。

Recall 自动机和下推机 状态: 1 目标 。Goto 的目标， 标号 2 停顿 。连续动作离散化的停顿，（直观启示 可能来自于 手摇计算机，齿轮动作实现，是离散的，一步） 3 思考。新的起点，歇一口气，根据当前输入，思考下一步动作。（自动机不看历史，下推机看一点很短的历史 -- 栈顶值） 后面的图灵机中，三者都有

§3.1 图灵机 非形式化描述 internal state set Q R L 每一步，读写头在单向无穷带上左右移动并读写， §3.1 图灵机 非形式化描述 每一步，读写头在单向无穷带上左右移动并读写， internal state set Q R L 根据当前状态和字符 xi,决定 写 移 转三动作 -写 letter, 有存储器 - 左或右移动 转移状态 可以作循环语句 磁带相当于数组，可读写。这是增加的重要资源

§3.1 图灵机 输入约定 初始, 带子上只有输入串w*,其它地方是空的。开始状态q0. state q0 §3.1 图灵机 输入约定 数组结构 state q0 初始, 带子上只有输入串w*,其它地方是空的。开始状态q0. 计算过程中读写头左右移动，机器内部状态改变，带子上内容重写。

§3.1 图灵机 输出约定 三种输出：接受、拒绝、循环 state qaccept state qreject or §3.1 图灵机 非常规意义循环——不停机。引出可判定性p89 输出约定 三种输出：接受、拒绝、循环 state qaccept state qreject or

TM vs. DFA §3.1 图灵机 相似性: 不同: 有限状态集 TM 无限长磁带 TM 可在磁带上读写 读写头可以左右移动 §3.1 图灵机 TM vs. DFA 相似性: 有限状态集 不同: TM 无限长磁带 TM 可在磁带上读写 读写头可以左右移动 进入接受或退出状态立即停机

§3.1 图灵机 B = { w#w | w is in {0,1}* } 对于输入字符串“w” 例：011000#011000 §3.1 图灵机 B = { w#w | w is in {0,1}* } 对于输入字符串“w” 在#两边对应的位置上来回移动，检查这些对应位置是否包含相同的符号，如不是，或者没有#，则拒绝，为跟踪对应的符号，消去所有检查过的符号 当#左边的所有符号都被消去时，检查#右侧是否还有符号，如果是则拒绝，否则接受 例：011000#011000

Snapshots of Execution (1) 1 #  L X 1 #  L X 1 #  L X 1 #  L M Tape head moves to right

Snapshots of Execution (2) 1 #  L X 1 #  L X 1 #  L X 1 #  L M Tape head moves to left

Snapshots of Execution (3) 1 #  L X 1 #  L X 1 #  L X 1 #  L M Tape head moves to right

Snapshots of Execution (4) 1 #  L X 1 #  L X 1 #  L X 1 #  L M Tape head moves to left

Snapshots of Execution (5) 1 #  L X 1 #  L X # 1  L X # 1  L M Tape head moves to right

Snapshots of Execution (6) #  L X #  L M Tape head moves to left X #  L X #  L

Snapshots of Execution (7) #  L X #  L M Tape head moves to right X #  L X #  L accept

§3.1.1 图灵机形式化定义 : Q\{qaccept,qreject}    Q    {L,R} §3.1.1 图灵机形式化定义 TM是一个7元组(Q, , , , q0, qAcc, qRej) ，其中： Q ： 状态集  ： 输入字母表, 不包括空白字符  ： 带字母表,    and     ： 转移函数  : Q x   Q x  x { L, R }, q0：开始状态 qAcc： 接受状态, qRej：拒绝状态 定义3.1 : Q\{qaccept,qreject}    Q    {L,R} 状态。当前字符 转， 写， 移

§3.1.1 图灵机形式化定义 q9 becomes “101 q9 1_0#1” 格局 类似NFA的状态 §3.1.1 图灵机形式化定义 类似NFA的状态 Configuration of a TM包括： 当前状态q Q 当前带内容  * 读写头位置  {0,1,2,…} 格局 格局=状态＋已经处理部分＋今后任务， 目前形式与任务 对于状态q和带字母表上的两个字符串u、v，以uqv表示如下格局：状态q、当前带内容uv，读写头位置为v的第一个符号，v后面为空白符 q9 becomes “101 q9 1_0#1”

§3.1.1 图灵机形式化定义 相关术语 starting configuration on input w: “q0w” 初始格局 §3.1.1 图灵机形式化定义 相关术语 starting configuration on input w: “q0w” 初始格局 accepting configuration: “uqacceptv” 接受格局 返回true rejecting configuration: “uqrejectv” 拒绝格局 返回false The accepting and rejecting configurations are the halting configurations.停机状态

§3.1.1 图灵机形式化定义 Turing machine M 录取标准，程序委员会 §3.1.1 图灵机形式化定义 TM M= (Q, , , , q0, qAcc, qRej)接受 (Formal Definition) 输入w，如果存在一个格局序列C1, C2, …, Ck 有： 1）C1 是M在输入w上的起始格局； 2）每一个Ci产生Ci+1 3）Ck是接受格局 比喻 录取 会议论文 Turing machine M 录取标准，程序委员会 accepts input w* 字符串，论文， configurations C1,C2,…,Ck 评审过程 accepting configuration “uqacceptv” 录用 uqrejectv” 拒绝 评审无反响 -- 死机

§3.1.1 图灵机形式化定义 一种进入循环 对于一个输入，TM有两种方式不接受它： 一种拒绝状态 定义3.2 §3.1.1 图灵机形式化定义 定义3.2 如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。 输入上运行一个TM时，可能出现三种结果： 接受、拒绝、循环（仅仅指机器不停机） 对于一个输入，TM有两种方式不接受它： 一种拒绝状态 一种进入循环 问题：如何区别长计算 与 死循环？ 因此，我们喜欢对所有输入都停机的图灵机，永不循环，这种机器为判定器。因为它们总能决定是接受还是拒绝，也称识别某个语言的判定器判定该语言。

Turing Recognizable (Def. 3.2) A language L is Turing-recognizable if and only if there is a TM M such that L=L(M). 图灵可识: 对 wL 函数M(w)返回true， 对wL，无承诺 Also called: a recursively enumerable language. L 又称为 递归可枚举语言 Note: On an input wL, the machine M can halt in a rejecting state, or it can ‘loop’ indefinitely. How do you distinguish between a very long computation and one that will never halt? 问题：如何区别 长计算 与 死循环？

Turing Decidable (Def. 3.3) 图灵可判定 A language L=L(M) is decided by the TM M if on every w, the TM finishes in a halting configuration. (That is: qaccept for wL and qreject for all wL.) 图灵可判定: 对 wL 函数M(w) 返回true， 对wL，返回false A language L is Turing-decidable if and only if there is a TM M that decides L.图灵可判定语言 Also called: a recursive language. 递归语言，比递归可枚举 要求高

可识别与可判定？ §3.1.1 图灵机形式化定义 1、可识别——M识别某种语言，输入w最后到达接受格局； §3.1.1 图灵机形式化定义 定义3.3 如果一个语言能被某一图灵机判定，则称它是图灵可判定的。 可识别与可判定？ 1、可识别——M识别某种语言，输入w最后到达接受格局； 2、可判定——判定器M识别某个语言。

详见书90页 §3.1.2 图灵机的例子 A = { w#w| w∈{0，1}*} 例3.4 例3.5 §3.1.2 图灵机的例子 例3.4 描述TM M2，它判定的语言是所有由0组成、长度为2的方幂的字符串，即A = { 0j | j=2n } 例3.5 A = { w#w| w∈{0，1}*} 详见书90页

书上的例 3.5,3.6, 3.7比较细致，有点繁而不难，学生应仔细读一遍。 Reject state not shown for simplicity start q1 1  X, R 0  X, R 0  0, R #  #, R q3 1  1, R 0  0, R q2 1  1, R 书上的例 3.5,3.6, 3.7比较细致，有点繁而不难，学生应仔细读一遍。 q8 X  X, R #  #, R #  #, R   , R q5 q4 X  X, R X  X, R 1  X, L 0X, L q6 0  0, L 1  1, L #  #, L X  X, L X  X, R q7 = accept state 0  0, L 1  1, L

Questions Let L’ be the complement（反、补） of language L Is the following true? If L is Turing-decidable, L is Turing-recognizable If L is Turing-recognizable, L is Turing-decidable If L is Turing-decidable, so is L’ If L is Turing-recognizable, so is L’ If both L and L’ are Turing-recognizable, L is Turing-decidable

主要内容 3.1 图灵机 3.2 图灵机的变形 3.3 算法的定义 3.1.1 图灵机形式化定义 3.1.2 图灵机例子 3.1 图灵机 3.1.1 图灵机形式化定义 3.1.2 图灵机例子 3.2 图灵机的变形 3.2.1 多带图灵机 3.2.2 非确定型图灵机 3.2.1 枚举器 3.2.1 与其他模型的等价性 3.3 算法的定义 3.3.1 希尔伯特问题 3.3.2 描述图灵机的术语

It is like a TM, but with several tapes §3.2 图灵机的变形 3.2.1 多带图灵机  = blank symbols 1  L control a b  L a b  L It is like a TM, but with several tapes

§3.2 图灵机的变形 3.2.1 多带图灵机 一个 k-带图灵机M具有k个不同的带子与读/写头,是一个7-tuple (Q,,,,q0,qaccept,qreject), 其中 Q finite set of states  finite input alphabet (without “_”)  finite tape alphabet with { _ }     q0 start state  Q qaccept accept state  Q qreject reject state  Q  the transition function : Q\{qaccept,qreject}  k  Q  k  {L,R}k 转 写 移 允许多个带子同时进行读、写和移动读写头， k:带子个数

§3.2 图灵机的变形 3.2.1 多带图灵机 最初时, 输入被写在第一条带子上，所有其他的带子为空 §3.2 图灵机的变形 3.2.1 多带图灵机 最初时, 输入被写在第一条带子上，所有其他的带子为空 一个 k-tape TM 转移函数如下：  : Q x k  Q x k x { L, R, S }k （qi,a1,a2,…,ak）=(qj,b1,b2,…,bk,L,R,…,L) 机器处于qi状态，读写头1到k所读的符号a1,…,ak,机器转移到状态qj,各读写头分别写下符号b1,…,bk,并按指示移动读写头。 很明显, 给定一个TM, 我们可以找到一个k-tape TM 识别相同的语言 如何变换?

Multi-tape TM = one-tape TM §3.2 图灵机的变形 3.2.1 多带图灵机 定理3.8 每个多带图灵机等价于某一个单带图灵机 Multi-tape TM = one-tape TM 增加存储和数组(多带)只提速和简化， 无本质改变 证明: 假设 M 是k-tape TM. 如何将其转换为一个单带 TM S？关键是怎样用S来模拟M

§3.2 图灵机的变形 3.2.1 多带图灵机 假设M有k个带子，s把此k个带子的信息都存储在它的唯一的带子上，并以此来模拟k个带子的效果。用一个新的符号 #作为定界符，以分开不同带子的内容。 2. 除了带内容之外，S必须记录每个读写头的位置。为此，在一个符号的顶上加个点，以此来标记读写头在其带上的位置，S把它们想象为虚拟带子与虚拟读写头。  下面例子说明如何用一个带子来表示三个带子

Note: M = {0,1,a,b,} and S = {0,1,a,b,,#,0*,1*,a*,b*,*,#*} E.g. 1  L M a  L a b  L S # 0* 1 a a* b* b  L Note: M = {0,1,a,b,} and S = {0,1,a,b,,#,0*,1*,a*,b*,*,#*}

Outline Proof Thm. 3.8 假设 M=(Q,,,,q0,qaccept,qreject) 为一个k-带TM. 造单带机模拟多带机 （多带机模拟单带机不需证明） 假设 M=(Q,,,,q0,qaccept,qreject) 为一个k-带TM. 扩展’ =  {#}构建一个1-带 M’ M-格局表示为： u1qja1v1, u2qja2v2, …, ukqjakvk M’-格局为：, qj # u1a1v1 # u2a2v2 # … # ukakvk 分带符 #, K带上当前字符 第1带 第k带格局

Proof Thm. 3.8 (cont.) 在输入 w=w1…wn上，TM M’ 按如下方式工作： 多带复制到单带 读带有下划线的输入字符 k 各带当前字 通过更新输入与头的位置模拟M 通过下标映射模拟动作 重复 2-3直到 M 到达一个停机状态 停机 PS: 如果更新需要重写 # 符号，向右转移# _ 部分

§3.2 图灵机的变形 3.2.2 非确定图灵机 control 与TM相似, 只是进行非确定性控制  = blank symbols a §3.2 图灵机的变形 3.2.2 非确定图灵机  = blank symbols control a b  L 与TM相似, 只是进行非确定性控制

非确定图灵机 一个 非确定性图灵机 M 在每一步可以有几种选择。由一个7元组定义(Q,,,,q0,qaccept,qreject), 其中， Q 状态集  输入字母表 (不包括 “_”)  带字母表 { _ }     q0 起始状态  Q qaccept 接受状态  Q qreject 拒绝状态 Q  转移函数 : Q\{qaccept,qreject}    P (Q    {L,R}) 格局演进是多前途的

NTM的计算 NTM 转移函数的形式  : Q x   2Q x  x { L, R } 对于一个输入 w, 可以通过一个计算树表示其所有可能的计算： 根 = 初始格局, 节点C的儿子 = 所有由C产生的格局 NTM接受 输入 w 如果有计算的分支能够到达接受状态（存在一条从根——接受状态的路径）

NTM的计算 只要一条被接受，就算被接受了，允许多次失败换取一次成功。 C1 t=1 t=2 C2 C4 C3 t=3 C5 C6 “reject”  “accept”

§3.2 图灵机的变形 3.2.2 非确定图灵机 定理3.10 每个非确定型图灵机等价于某一个确定图灵机 NTM = TM 证明: 假设N 为NTM. 转换N 为TM D. 基本思路是用N’s 计算所有可能分支来模拟N. 如果一个分支导致接受状态，D 接受，否则，D’s模拟永不终止。 详细证明见书94-95页。

It is like a TM, but with a printer §3.2 图灵机的变形 3.2.3 枚举器 aa cc aba control printer  = blank symbols a b  L It is like a TM, but with a printer

§3.2 图灵机的变形 3.2.3 枚举器 定理3.13 一个语言是图灵可识别的，当且仅当有枚举器枚举它。

§3.2 图灵机的变形 证明： 首先证明如果有枚举器E枚举语言L，则存在图灵机M识别L。构造M如下： §3.2 图灵机的变形 证明： 首先证明如果有枚举器E枚举语言L，则存在图灵机M识别L。构造M如下： 对于任意输入串w，运行E。每当E输出一个串时，与w比较，若相等，接受w，并停机。 显然，M接受在E输出序列中出现过的那些串。 现在证明若有图灵机M识别语言L，则有枚举器E枚举L。 设L={w1，w2，w3，…}，构造E如下： 对i=1,2,3,…执行如下步骤： （1）对w1，w2，w3，…, wi中的每一串，让M以其作为输入运行i步。 （2）若在这个计算中，M接受wj，则打印wj， M接受w，它最终将出现在E的枚举打印中。事实上，它可能在E的列表在出现无限多次，因为每一次重复运行，M在每一个串上都从头开始运行。

§3.2 图灵机的变形 3.2.4 与其它模型的等价性 考虑其他一些合理的计算模型如： DNA computing 神经网络 量子… §3.2 图灵机的变形 3.2.4 与其它模型的等价性 考虑其他一些合理的计算模型如： DNA computing 神经网络 量子… 经验告诉我们，每一种这样的模型都可用图灵机模拟

REVIEW(2011-03-21) PDA与CFG之间的等价性 CFG转换为PDA： PDA转换为CFG： 对P轻微修改: 重复下述步骤： 如果栈顶是变元A，则非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串。 如果栈顶是终结符a，则读输入中的下一个符号，并且将其与a比较。如果它们匹配，则重复，如果不匹配，则这个非确定性分支拒绝。 如果栈顶是符号$，则进入接受状态，如果此刻输入已全部读完，则接受这个输入串 PDA转换为CFG： 对P轻微修改: 有唯一的接受状态, qaccept 在接受之前清空栈 每一个转移把一个符号推入栈，或者把一个符号弹出栈，但不同时做这两个动作 对P中的每一对状态p, q,建立一个 CFG变量Apq增加规则： Apq  AprArq Apq  aArsb App  

REVIEW(2011-03-21) 非上下文无关语言 图灵机 图灵机的变形 关于上下文无关的泵引理（证明） 判定某个语言L不是CFL 图灵机形式化定义 7元组(Q, , , , q0, qAcc, qRej) : Q\{qaccept,qreject}    Q    {L,R} 格局 接受、拒绝、循环 图灵可识别 图灵可判定 图灵机的变形 多带图灵机 非确定型图灵机 枚举器 与其他模型的等价性

主要内容 3.1 图灵机 3.2 图灵机的变形 3.3 算法的定义 3.1.1 图灵机形式化定义 3.1.2 图灵机例子 3.1 图灵机 3.1.1 图灵机形式化定义 3.1.2 图灵机例子 3.2 图灵机的变形 3.2.1 多带图灵机 3.2.2 非确定型图灵机 3.2.1 枚举器 3.2.1 与其他模型的等价性 3.3 算法的定义 3.3.1 希尔伯特问题 3.3.2 描述图灵机的术语

§3.3 算法的定义 非形式地说，算法是为实现某个任务而构造的简单指令集。在日常用语来说，算法有时称为过程或处方。算法在数学中也起着重要的作用。古代数学文献中包含了各种各样任务的算法描述，如寻找素数和最大公因子。当代数学中更是充满了算法。

3.3.1 希尔伯特问题 一个多项式是一些项的和，其中：每个项都是一个常数和一些变元的积，此常数叫系数（coefficient）。 例如，6·x·x·x·y·z·z=6x3yz2是一个项，其系数是6； 6x3yz2+3xy2-x3-10 是一个多项式，它有四个项和三个变元x、y、z 多项式的根（root）是对它的变元的一个赋值，使此多项式的值为0。 上述多项式的一个根是x=5、y=3和z=0，这个根是整数根（integral root），因为所有变元都被赋予整数值。

3.3.1 希尔伯特问题 希尔伯特第10问题旨在设计一个算法来检测一个多项式是否有整数根。“通过有限多次运算就可以决定的过程” 丘奇-图灵论题（Church-Turing thesis） 现在用上述术语来重新陈述希尔伯特第10问题，设 D={p|p是有整数根的多项式} 本质上，希尔伯特第10问题是问；集合D是不是可判定的?答案是否定的。 算法的直觉概念 等于 图灵机算法

3.3.1 希尔伯特问题 考虑只有一个变元的多项式，如4x3-2x2+x-7。设 D1 ={p|p是有整数根x的多项式} 下面是识别D1的图灵机M1： M1 =“输入是关于变元x的一个多项式p： 当x相继被设置为值0，1，-1，2，-2，3，-1，…时，求p的值，一旦求得0值，就接受。” 如果p有整数根，M1最终将找到它，从而接受；如果p没有整数根，则M1将永远运行下去。 对于多变元的情形，可以设计一个类似的图灵机M来识别D，只是M要检查多个变元所有可能取的整数值。

本章给出了许多图灵机的描述，都是形式化或实现描述的例子 3.3.2 描述图灵机的术语 现在到了计算理论研究的转折点 讨论对象还是图灵机，但真正的焦点是算法，图灵机只是作为算法定义的一个精确模型——TM刻画了所有的算法 将图灵机算法的描述方式标准化。 描述算法时，什么样的详细程度是适当的？ 描述的详细程度有三种： 形式化描述：详尽地写出图灵机的状态、转移函数等，属于最低层次、最详细程度的描述； 实现描述：使用日常语言描述图灵机动作，如怎么移动读写头、怎么在带上存储数据等，这种程度的描述没有给出状态和转移函数的细节； 高水平描述：也使用日常语言来描述算法，但忽略了实现的模型，不需要提及机器怎样管理它的带子或读写头。 本章给出了许多图灵机的描述，都是形式化或实现描述的例子

描述图灵机的格式和记号 图灵机的输入总是一个串。如果想以一个对象而不是字符串的作为输入，必须先将那个对象字符串化。 对象O的编码成字符串的记号是<O>。如果有多个对象O1， O2，…， Ok，它们的编码是一个串，记为< O1， O2，…， Ok >。 描述图灵机算法的格式是带引号的文字段，且排成锯齿形状。将算法分成几个步骤，每个步骤可能包括图灵机计算的许多步，用更深的缩进方式来指示算法的分块结构。算法的第一行描述机器的输入。如果输入描述仅仅被写成w，则这个串就被当作输入，如果输入描述是一个对象的编码< A > ，则暗示图灵机需要首先检查此输入是否确实是所要的对象的编码，如果不是，则拒绝它。

A={<G>|G是连通无向图} 描述图灵机的术语 例3.14 设A是由表示连通无向图的串构成的语言。回忆一下，如果一个图从任意顶点出发，都可以沿着边走到其它所有顶点，则称这个图是连通的。记A为 A={<G>|G是连通无向图} 下面是判定A的TM M的一个高层次描述： M=“输入是图G的编码<G> ： 1)选择G的第一个顶点，并标记之。 2)重复下列步骤，直到没有新的顶点可作标记。 3)对于G的每一个顶点，如果能通过一条边将其连到另一 个已被标记的顶点，则标记该顶点。 4)扫描G的所有顶点，确定它们是否都已做了标记，如果 是，则接受，否则拒绝。

描述图灵机的术语 图G和它的编码方式。 TM实现细节： 1.对输入进行检查 2.M继续运行，详细过程见99-100页 边 顶点序列 序列 4 边 序列 顶点序列 1 G= <G>= (1,2,3,4,)((1,2),(2,3),(3,1),(1,4)) 2 3 可以有多种编码方式 图G和它的编码方式。 TM实现细节： 1.对输入进行检查 2.M继续运行，详细过程见99-100页

Homework 3.1、3.2、3.4、3.5、3.7、3.15、3.16