当前位置:首页 >> 工学 >>

第二讲 图灵机模型


第2讲 图灵机模型
?

?

?

图灵机(Turing machine)是由图灵(Alan Mathisom Turing)在1936年提出的,它是一 个通用的计算模型。 通过研究图灵机,来研究递归可枚举集 (recursively enumerable set)和部分地 归函数(partial recursive function) 。 对算法和可计算性进行研究提供形式化描述工 具。

1

主要内容、重难点
?

主要内容


图灵机作为一个计算模型,它的基本定义,即时描 述,图灵机接受的语言;图灵机的构造技术;图灵 机的变形;Church-Turing论题;通用图灵机。可 计算语言、不可判定性、P-NP问题)。

? ?

重点


图灵机的定义、图灵机的构造。

难点
– 图灵机的构造。

2

2.1 基本概念
?

图灵提出图灵机具有以下两个性质
– –

具有有穷描述。 过程必须是由离散的、可以机械执行的步骤组成。 一个有穷控制器。 一条含有无穷多个带方格的输入带。 一个读头。 改变有穷控制器的状态; 在当前所读符号所在的带方格中印刷一个符号; 将读头向右或者向左移一格。

?

基本模型包括
– – –

?

一个移动将完成以下三个动作
– –



3

直观物理模型

4

2.1.1 基本图灵机
?

图灵机(Turing machine)/基本的图灵机 M=(Q, ∑, Γ, δ,q0 , B , F) , Q为状态的有穷集合,?q∈Q,q为M的一个 状态;

?

?

q0∈Q,是M的开始状态,对于一个给定的输 入串,M从状态q0启动,读头正注视着输入带 最左端的符号;

5

2.1.1 基本图灵机
?

F?Q,是M的终止状态集,?q∈F,q为M的 一个终止状态。与FA和PDA不同,一般地, 一旦M进入终止状态,它就停止运行; Γ为带符号表(tape symbol),?X∈Γ,X为 M的一个带符号,表示在M的运行过程中,X 可以在某一时刻出现在输入带上;

?

6

2.1.1 基本图灵机
?

B∈Γ,被称为空白符(blank symbol),含有 空白符的带方格被认为是空的; ∑?Γ-{B}为输入字母表,?a∈∑,a为M的一 个输入符号。除了空白符号B之外,只有∑中 的符号才能在M启动时出现在输入带上;

?

7

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,然后将读头向左移一格。

8

例子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)

9

例子2-1说明
0 q0 q1 q2 (q0, 0, R) (q1, 0, R) 1 (q1, 1, R) (q2, B, R) B

10

2.1.1 基本图灵机
? ?

即时描述(instantaneous description, ID) α1α2∈Γ*,q∈Q,α1qα2称为M的即时描述
– –



q为M的当前状态。 α1α2为M的输入带最左端到最右的非空白符号组成 的符号串或者是M的输入带最左端到M的读头注视 的带方格中的符号组成的符号串 M正注视着α2的最左符号。

11

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 。

12

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;

13

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*。

14

2.1.1 基本图灵机
例 2-2. 例 2-1所给的M1在处理输入串的过程中 经历的ID变换序列。 (1)处理输入串000100的过程中经历的ID的变 换序列如下: q0000100├M 0q000100├M 00q00100 ├M 000q0100├M 0001q100├M 00010q10 ├M 000100 q1├M 000100Bq2
?

15

2.1.1 基本图灵机
(2)处理输入串0001的过程中经历的ID变换序 列如下: q00001├M 0q0001├M 00q001 ├M 000q01├M 0001q1├M 0001Bq2 (3)处理输入串000101的过程中经历的ID变换 序列如下: q0000101├M 0q000101├M 00q00101 ├M 000q0101├M 0001q101├M 00010q11
16

2.1.1 基本图灵机
(4)处理输入串1的过程中经历的ID变换序列 如下: q01├M 1q1├M 1Bq2 (5)处理输入串00000的过程中经历的ID变换 序列如下: q000000├M 0q00000├M 00q0000 ├M 000q000├M 0000 q00├M 00000q0B
17

2.1.1 基本图灵机
?

? ?

图灵机接受的语言 L(M)={x | x∈∑* & q0x├M* α1 qα2 & q∈F &α1、 α2∈Γ*} 图灵机接受的语言叫做递归可枚举语言 (recursively enumerable language,r.e.)。 如果存在图灵机 M=(Q, ∑, Γ, δ,q0 , B , F), L=L(M),并且对每一个输入串x,M都停机, 则称L为递归语言(recursively language)。

18

2.1.1 基本图灵机
?

例 2-3 设有M2=({q0, q1, q2, q3},{0, 1},{0, 1, B},δ,q0 , B ,{q3}),其中δ的定义如下: δ(q0, 0)= (q0, 0, R) δ(q0, 1)= (q1, 1, R) δ(q1, 0)= (q1, 0, R) δ(q1, 1)= (q2, 1, R) δ(q2, 0)= (q2, 0, R) δ(q2, 1)= (q3, 1, R)

19

2.1.1 基本图灵机
0 q0 q1 q2 q3 (q0, 0, R) (q1, 0, R) (q2, 0, R) 1 (q1, 1, R) (q2, 1, R) (q3, 1, R) B

20

2.1.1 基本图灵机
? 为了弄清楚M2接受的语言,需要分析它的工

作过程。 (1)处理输入串00010101的过程中经历的ID变 换序列如下: q000010101├ 0q00010101├ 00q0010101 ├ 000q010101├ 0001q10101├ 00010q1101 ├ 000101 q201├000101 0 q21├ 00010101q3
21

2.1.1 基本图灵机
?

M2在q0状态下,遇到0时状态仍然保持为q0, 同时将读头向右移动一格而指向下一个符号; 在q1状态下遇到第一个1时状态改为q1,并继 续右移读头,以寻找下一个1;在遇到第二个1 时,动作类似,只是将状态改为q2;当遇到第 三个1时,进入终止状态q3,此时它正好扫描 完整个输入符号串,表示符号串被M2接受。

?

22

2.1.1 基本图灵机
(2)处理输入串1001100101100的过程中经历的 ID变换序列如下: q01001100101100├ 1q1001100101100 ├ 10 q101100101100├ 100q11100101100 ├ 1001 q2100101100├10011q300101100 ? M2遇到第三个1时,进入终止状态q3,输入串 的后缀00101100还没有被处理。但是,由于 M2已经进入终止状态,表示符号串 1001100101100被M2接受。
23

2.1.1 基本图灵机
(3)处理输入串000101000的过程中经历的ID变换 序列如下: q0000101000├ 0q000101000├ 00q00101000 ├ 000q0101000├ 0001q101000├ 00010q11000 ├ 000101q2000├ 0001010 q200├ 00010100 q20 ├ 000101000 q2B ? 当M2 的ID变为000101000q2B时,因为无法进行 下一个移动而停机,不接受输入串000101000。
24

2.1.1 基本图灵机
?

M2接受的语言是字母表{0,1}上那些至少含有 3个1的0、1符号串。请读者考虑,如何构造出 接受字母表{0,1}上那些含且恰含有3个1的符 号串的TM。

25

2.1.1 基本图灵机
?

例 2-4 构造TM M3,使L(M)={0n1n2n | n≥1}。 分析: – 不能通过“数”0、1、或者2的个数来实现 检查。 – 最为原始的方法来比较它们的个数是否是 相同的:消除一个0、然后消除一个1,最 后消除一个2。 – 消除的0的带方格上印刷一个X,在消除的1 的带方格上印刷一个Y,在消除的2的带方 格上印刷一个Z。

26

2.1.1 基本图灵机






正常情况下,输入带上的符号串的一般形 式为 00…0011…1122…22 TM启动后,经过一段运行,输入带上的符 号串的一般情况为 X…X0…0Y…Y1…1Z…Z2…2BB 需要给予边界情况密切的关注。

27

2.1.1 基本图灵机
?

边界情况



– –



X…XX…XY…YY…YZ…Z2…2BB X…XX…XY…Y1…1Z…Z2…2BB X…X0…0Y…YY…YZ…Z2…2BB X…X0…0Y…Y1…1Z…ZZ…ZBB X…X0…0Y…YY…YZ…ZZ…ZBB

28

构造思路

29

移动函数
0 q0 q1 q2 q3 (q3,0,L) (q0,X,R) (q1,0,R) (q2,Y,R) (q2,1,R) (q3,1,L) (q3,Z,L) (q0,X,R) (q3,Y,L) 1 2 X Y (q4,Y,R) (q1,Y,R) (q2,Z,R) (q3,Z,L) Z B

q4 q5

(q4,Y,R)

(q4,Z,R)

(q5,B,R)

30

2.1.2 图灵机作为非负整函数的计算模型
?

?

非负整数进行编码 ——1进制 – 用符号串0n表示非负整数n。 用符号串

0 10 1?10

n1

n2

nk

表示k元函数f(n1, n2,…, nk)的输入。如果f(n1, n2,…, nk)=m,则该图灵机的输出为0m 。
31

2.1.2 图灵机作为非负整函数的计算模型
?

?

图灵可计算的(Turing computable) 设有k元函数f(n1, n2,…, nk)=m,TM M=(Q, ∑, Γ, δ,q0 , B , F)接受输入串

0 10 1?10

n1

n2

nk

输出符号串0m;当f(n1, n2,…, nk)无定义时, TM M没有恰当的输出给出。称TM M计算k元 函数f(n1, n2,…, nk),也称f(n1, n2,…, nk)为TM M计算的函数。也称f是图灵可计算的。
32

2.1.2 图灵机作为非负整函数的计算模型
?

完全递归函数(total recursive function)


设有k元函数f(n1, n2,…, nk),如果对于任意 的n1, n2,…, nk ,f均有定义,也就是计算f的 图灵机总能给出确定的输出,则称f为完全 递归函数。

?

部分递归函数(partial recursive function)


图灵机计算的函数称为部分递归函数。

33

2.1.2 图灵机作为非负整函数的计算模型
例 2-5 构造TM M4,对于任意非负整数n,m, M4计算m+n。 分析:M4的输入为0n10m,输出0n+m的符号串。 n和m为0的情况需要特殊考虑。 (1)当n为0时,只用将1变成B就完成了计算, 此时无需考察m是否为0; (2)当m为0时,需要扫描过表示n的符号0,并 将1改为B。 (3)当n和m都不为0时,我们需要将符号1改为0, 并将最后一个0改为B。
?

34

构造思路

35

M4
M4=({q0, q1, q2, q3}, {0,1}, {0,1,B}, δ , q0, B, {q1}) δ(q0,1)=(q1,B,R) δ(q0,0)=(q2,0,R) δ(q2,0)=(q2,0,R) δ(q2,1)=(q2,0,R) δ(q2,B)=(q3,B,L) δ(q3,0)=(q1,B,R)
36

2.1.2 图灵机作为非负整函数的计算模型
?

例 2-6 构造图灵机 M5,对于任意非负整数n, m,M5计算如下函数:

n?m n?m ?{ ? 0

n≥ m n< m

37

构造思路

38

M5
?

M5=({q0, q1, q2, q3, q4, q5, q6,}, {0,1}, {0, 1, X, B}, δ, q0, B, {q6}) δ(q0, 0 )=(q1, B, R) δ(q0, 1 )=(q5, B, R) δ(q1, 0 )=(q1, 0, R) δ(q1, 1 )=(q1, 1, R) δ(q1, X )=(q2, X, R) δ(q2, X )=(q2, X, R) δ(q2, 0 )=(q3, X, L) δ(q2, B )=(q4, B, L) δ(q3, X )=(q3, X, L) δ (q3, 1 )=(q3, 1, L) δ(q3, 0 )=(q3, 0, L) δ(q3, B )=(q0, B, R)

39

M5
δ(q4, X )=(q4, B, L) δ(q4, 1 )=(q6, 0, R) δ(q5, X )=(q5, B, R) δ(q5, 0 )=(q5, B, R)

δ(q5, B )=(q6, B, R)。

40

2.1.3 图灵机的构造
1. 状态的有穷存储功能的利用

2. 多道(multi-track)技术
3. 子程序(subroutine)技术

41

1. 状态的有穷存储功能的利用
?

例 2-7 构造图灵机 M6,使得L(M6)={x | x∈{0,1}*& x中至多含3个1}。 分析:M6只用记录已经读到的1的个数。 q[0]表示当前已经读到0个1; q[1]表示当前已经读到1个1; q[2]表示当前已经读到2个1; q[3]表示当前已经读到3个1。

42

1. 状态的有穷存储功能的利用
?

M6=({q[0], q[1], q[2], q[3], q[f]}, {0,1}, {0,1,B}, δ , q[0], B, {q[f]})

δ(q[0], 0 )=(q[0], 0, R) δ(q[0], 1 )=(q[1], 1, R) δ(q[0], B )=(q[f], B, R) δ(q[1], 0 )=(q[1], 0, R) δ(q[1], 1 )=(q[2], 1, R) δ(q[1], B )=(q[f], B, R)
43

δ(q[2], 0 )=(q[2], 0, R) δ(q[2], 1 )=(q[3], 1, R) δ(q[2], B )=(q[f], B, R) δ(q[3], 0 )=(q[3], 0, R) δ(q[3], B )=(q[f], B, R)

1. 状态的有穷存储功能的利用
?

图灵机是要接受且仅接受恰含3个1的0、1串的 图灵机,对M6进行修改,得到M7 L(M7) ={x | x∈{0,1}*& x中含且仅含3个1} M7=({q[0], q[1], q[2], q[3], q[f]}, {0, 1}, {0, 1, B}, δ , q[0], B, {q[f]})

?

?

44

L(M7) ={x | x∈{0,1}*且 x中仅含3个1}
δ(q[0], 0 )=(q[0], 0, R) δ(q[0], 1 )=(q[1], 1, R) δ(q[1], 0 )=(q[1], 0, R) δ(q[1], 1 )=(q[2], 1, R) δ(q[2], 0 )=(q2), 0, R) δ(q[2], 1 )=(q[3], 1, R) δ(q[3], 0 )=(q[3], 0, R) δ(q[3], B )=(q[f], B, R)
45

L(M8)={x | x∈{0,1}*& x中至少含3个1}
M8=({q[0], q[1], q[2], q[f]}, {0, 1}, {0, 1, B}, δ, q[0], B, {q[f]}) δ(q[0], 0 )=(q[0], 0, R) δ(q[0], 1 )=(q[1], 1, R) δ(q[1], 0 )=(q[1], 0, R) δ(q[1], 1 )=(q[2], 1, R) δ(q[2], 0 )=(q[2], 0, R) δ(q[2], 1 )=(q[f], 1, R)
46

1. 状态的有穷存储功能的利用
?

例2-8 构造图灵机 M9它的输入字母表为{0, 1},现在要求M9在它的输入符号串的尾部添 加子串101。 分析:
– – – –

将待添加子串101存入穷控制器。 首先找到符号串的尾部。 将给定符号串中的符号依次地印刷在输入带上 每印刷一个符号,就将它从有穷控制器的“存储器” 中删去,当该“存储器”空时,图灵机就完成了工 作。

47

1. 状态的有穷存储功能的利用
M9=({q[101], q[01], q[1], q[ε]}, {0, 1}, {0, 1, B}, δ, q[101], B, {q[ε]}) 其中δ的定义为: δ(q[101], 0 )=(q[101], 0, R) δ(q[101], 1 )=(q[101], 1, R) δ(q[101], B )=(q[01], 1, R) δ(q[01], B )=(q[1], 0, R) δ(q[1], B )=(q[ε], 1, R)
48

1. 状态的有穷存储功能的利用
?

?

例2-9 构造图灵机 M10它的输入字母表为{0, 1},要求M10在它的输入符号串的开始处添加 子串101。 将有穷控制器中的“存储器”分成两部分
– – –

第一部分用来存放待添加的子串。 第二部分用来存储因添加符号串当前需要移动的输 入带上暂时无带方格存放的子串。 一般形式为q[x, y] ? x待添加子串 ? y当前需要移动的输入带上暂时无带方格存放的 子串。

49

1.状态的有穷存储功能的利用
? ? ? ?

q[x, ε]为开始状态; q[ε, ε]为终止状态。 设a、b为输入符号 δ(q[ax, y], b) = (q[x, yb], a, R)


表示在没有完成待插入子串的印刷之前,要将待插 入子串的首字符印刷在TM当前扫描的带方格上。

50

1. 状态的有穷存储功能的利用
?

δ(q[ε,a y], b) = (q[ε, yb], a, R)


表示当完成待插入子串的插入工作之后,必须将插 入点之后的子串顺序地向后移动。 表示读头当前所指的带方格为空白,现将“存储器” 的第二部分中的当前首符号a印刷在此带方格上, 同时将这个符号从存储器中删除。

?

δ(q[ε,a y], B) = (q[ε, y], a, R)


51

2. 多道(multi-track)技术
?

例2-10 构造M11,使L(M11)={xcy | x,y∈{0,1}+ 且 x≠y}。 分析:



– –



以符号c为分界线,逐个地将c前的符号与c后的符 号进行比较。 当发现对应符号不同时,就进入终止状态。 当发现x与y的长度不相同而进入终止状态。 发现它们相同而停机。 一个道存放被检查的符号串,另一个存放标记符。

52

构造思路

53

2. 多道(multi-track)技术
?

M11=({q[ε], q[0], q[1], p[0], p[1] , q, p, s, f}, {[B,0], [B,1], [B,c]}, {[B,0], [B,1], [B,c], [?,0], [?,1], [B,B]}, δ, q[ε], [B,B], {f}) δ(q[ε], [B,0] )=(q[0], [?,0], R) δ(q[ε], [B,1])=(q[1], [?,1], R) δ(q[a], [B,d])=(q[a], [B,d], R) δ(q[a], [B,c])=(p[a], [B,c], R) δ(p[a], [?,b])=(p[a], [?,b], R) δ(p[a], [B,a])=(p, [?,a], L)

54

2. 多道(multi-track)技术
δ(p, [?,b])=(p, [?,b], L) δ(p, [B,c])=(q, [B,c], L) δ(q, [B,a])=(q, [B,a], L) δ(q, [?,a])=(q[ε], [?,a], R) δ(p[a], [B,b])=(f, [B,b],R) δ(p[a], [B,B])=(p, [B,B], R) δ(s, [?,b])=(s, [?,b], R) δ(s, [B,a])=(f, [B,a], R)
55

3. 子程序(subroutine)技术
?

?
? ?

将图灵机的设计看成是一种特殊的程序设计, 将子程序的概念引进来。 一个完成某一个给定功能的图灵机 M′从一个 状态q开始,到达某一个固定的状态f结束。 将这两个状态作为另一个图灵机 M的两个一 般的状态。 当M进入状态q时,相当于启动M′(调用M′对 应的子程序);当M′进入状态f时,相当于返回 到M的状态f。

56

3. 子程序(subroutine)技术
?

例2-11 构造M12完成正整数的乘法运算。 分析:

– – – –

设两个正整数分别为m和n。 输入串为0n10m 。 输出应该为0n*m 。 算法思想:每次将n个0中的1个0改成B,就在输入 串的后面复写m个0。 在M12的运行过程中,输入带的内容为

Bh0n-h10m10m*hB
57

正整数的乘法运算
(1)初始化。完成将第一个0变成B,并在最后 一个0后写上1。我们用q0表示启动状态,用q1 表示完成初始化后的状态。首先,消除前n个0 中的第一个0,
q00n10m ├+ Bq10n-110m1

(2)主控系统。从状态q1开始,扫描过前n个0 中剩余的0和第一个1,将读头指向m个0的第 一个,此时的状态为q2。其ID变化为
Bhq10n-h10m10m*(h-1)B ├+ Bh0n-h1 q20m10m*(h-1)B

58

正整数的乘法运算
?

当子程序完成m个0的复写后,回到q3。这个 状态相当于子程序的返回(终止)状态。然后 在q3状态下,将读头移回到前n个0中剩余的0 中的第一个0,并将这个0改成B,进入q1状态, 准备进行下一次循环 Bh0n-h1 q30m10m*hB ├+ Bh+1q10n-h-110m10m*hB

59

正整数的乘法运算
当完成m*n个0的复写之后,清除输入带上除 了这m*n个0以外的其他非空白符号。q4为终 止状态 Bnq110m10m*nB ├+ Bn+1+m+1 q4 0m*nB (3)子程序。完成将m个0复写到后面的任务。 从q2启动,到q3结束,返回到主控程序。
?

Bh+10n-h-11 q20m10m*hB ├+ Bh+10n-h-11 q30m10m*h+1B

60

2.2 图灵机的变形
?

从不同的方面对图灵机进行扩充。



– –

双向无穷带图灵机。 多带图灵机。 不确定的图灵机。 多维图灵机等。

?

它们与基本的图灵机等价。

61

2.2.1 双向无穷带图灵机
物理模型

62

2.2.1 双向无穷带图灵机
?

? ? ?

双向无穷带 (Turing machine with two-way infinite tape) 图灵机 M=(Q, ∑, Γ, δ,q0 , B , F) Q, ∑, Γ, δ,q0 , B , F的意义同定义9-1。 M的即时描述ID同定义9-2。 允许M的读头处在输入串的最左端时,仍然可 以向左移动。

63

2.2.1 双向无穷带图灵机
? ?

M的当前ID X1X2…Xi-1qXiXi+1…Xn 如果δ(q, Xi)=(p, Y, R)


当i≠1并且Y≠B时,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 。

64

2.2.1 双向无穷带图灵机






当i=1并且Y=B时,M的下一个ID为 pX2…Xn 记作 qX1X2…Xn├M pX2…Xn 这就是说,和基本图灵机在读头右边全部是B时, 这些B不在ID中出现一样,当双向无穷带图灵机的 读头左边全部是B时,这些B也不在该图灵机的ID 中出现。

65

2.2.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…n下,经过一次移 动,将ID变成X1X2…pXi-1YXi+1…Xn 。

66

2.2.1 双向无穷带图灵机






当i=1时,M的下一个ID为 pBYX2…Xn 记作 qX1X2…Xn├M pBYX2…Xn 表示M在ID qX1X2…Xn下,经过一次移动,将ID 变成pBYX2…Xn。

67

2.2.1 双向无穷带图灵机
定理2-1 对于任意一个双向无穷带图灵机M,存 在一个等价的基本图灵机M′。
证明要点: – 双向无穷存储的模拟:用一个具有2个道的基本 TM来模拟:一个道存放M开始启动时读头所注视 的带方格及其右边的所有带方格中存放的内容;另 一个道按照相反的顺序存放开始启动时读头所注视 的带方格左边的所有带方格中存放的内容。 – 双向移动的模拟:在第1道上,移动的方向与原来 的移动方向一致,在第2道上,移动的方向与原来 的移动方向相反。

68

用单向无穷带模拟双向无穷带

69

2.2.2 多带图灵机
?

?
?

多带图灵机(multi-tape turing machine) 允许图灵机有多个双向无穷带,每个带上有一 个相互独立的读头。 k带图灵机在一次移动中完成如下三个动作
⑴ 改变当前状态; ⑵ 各个读头在自己所注视的带方格上印刷一个希望的 符号。 ⑶ 各个读头向各自希望的方向移动一个带方格。

70

2.2.2 多带图灵机

71

2.2.2 多带图灵机
定理 2-2 多带图灵机与基本的图灵机等价。 证明要点: ? 对一个k带图灵机,用一条具有2k道的双向无穷 带图灵机M′,实现对这个k带图灵机M的模拟。 ? 对应M的每一条带,M′用两个道来实现模拟。 其中一条道用来存放对应的带的内容,另一条 道专门用来标记对应带上的读头所在的位置。

72

2.2.3 不确定的图灵机
不确定图灵机与基本图灵机的区别是对于任意 的(q,X)∈Q×Γ, δ(q,X)={(q1,Y1,D1),(q2,Y2,D2),…,(qk, Yk,Dk)} ? Dj为读头的移动方向。即Dj∈{R,L}。 ? 表示M在状态q,读到X时,可以有选择地进 入状态qj,印刷字符Yj,按Dj移动读头 ? L(M)={w | w∈∑*且ID1├*IDn,且IDn含M的 终止状态}。
?

73

2.2.3 不确定的图灵机
定理 2-3 不确定的图灵机与基本的图灵机等价
?

证明要点: – 让等价的基本图灵机M′ 具有3条带。 – 第1条带用来存放输入。 – 第2条带上系统地生成M的各种可能的移动序列 – M′在第3条带上按照第2条带上给出的移动系列处 理输入串,如果成功,则接受之,如果不成功,则 在第2条带上生成下一个可能的移动系列,开始新 一轮的“试处理”。

74

2.2.4 多维图灵机
?

多维图灵机(multi-dimensional Turing machine)


读头可以沿着多个维移动。

? ?

?

k维图灵机(k-dimensional Turing machine) 图灵机可以沿着k维移动。 k维图灵机的带由k维阵列组成,而且在所有 的2k个方向上都是无穷的,它的读头可以向着 2k个方向中的任一个移动。

75

2.2.4 多维图灵机
定理 2-4 多维图灵机与基本图灵机等价。 ? 用一维的形式表示k维的内容,就像多维数组 在计算机的内存中都被按照一维的形式实现存 储一样。 ? 段(Segment)用来表是一维上的内容。 ? 用#作为段分割符。 ? ¢用作该字符串的开始标志,$用作该字符串 的结束标志。
76

基本图灵机模拟2维图灵机
B B B a1
5

a1 a5 a1
1

a2 B B B B

a3 a6 B B a1
7

a
4

B a8 B B B

B a9 a12 B B

B a1
0

B B a13 B B

B B B B a1
8

B B a14 a16 B

a
7

B B B

B B B

a1
6

B

B

a1
9

a2
0

B B

B B

B B

B B

B B

B B

B B

B B

B a21

B

B

77

基本图灵机模拟2维图灵机
¢Ba1a2a3a4BBBBBB # Ba5Ba6a7a8a9a10BBB # Ba11BBBBa12Ba13Ba14 # a15 a16BBBBBBBB a16# BBB a17BBBBBa18B # a19a20BBBBBBBBB # BBBBBBBBBBa21$

78

2.2.5 其他图灵机
1. 多头TM 2. 离线TM 3. 作为枚举器的TM 4. 多栈机 5. 计数机 6. Church-Turing论题与随机存取机

79

1. 多头图灵机
? ?

多头图灵机(multi-head Turing machine) 指在一条带上有多个读头,它们受M的有穷控 制器的统一控制,M根据当前的状态和这多个 头当前读到的字符确定要执行的移动。在M的 每个动作中,各个读头所印刷的字符和所移动 的方向都可以是相互独立的。

80

1. 多头图灵机
定理 2-5 多头图灵与基本的图灵机等价。 ? 可以用一条具有k+1个道的基本图灵机来模拟 一个具有k个头的图灵(k头图灵机)。其中 一个道用来存放原输入带上的内容,其余k个 道分别用来作为k个读头位置的标示。

81

2. 离线图灵机
?

?

?
?

离线图灵机(off-line Turing machine) – 有一条输入带是只读带(read-only tape)的多 带图灵机。 符号¢和$用来限定它的输入串存放区域,¢ 在左边,$在右边。 不允许该带上的读头移出由¢和$限定的区 域——离线的图灵机。 如果只允许只读带上的读头从左向右移动,则 称之为在线图灵机(on-line Turing machine)。

82

2. 离线图灵机
定理 2-6 离线图灵机与基本的图灵机等价。 证明要点:让模拟M的离线图灵机比M多一条 带,并且用这多出来的带复制M的输入串。然 后将这条带看作是M的输入带,模拟M进行相 应的处理。

83

3. 作为枚举器的图灵机
?

?

?
?

作为枚举器的图灵机(Turing machine as enumerator) – 多带图灵机,其中有一条带专门作为输出带,用来 记录产生语言的每一个句子。 在枚举器中,一旦一个字符被写在了输出带上,它就 不能被更改。如果该带上的读头的正常移动方向是向 右移动的话,这个带上的读头是不允许向左移动的。 如果这个语言有无穷多个句子,则它将永不停机。它 每产生一个句子,就在其后打印一个分割符“#”。 枚举器产生的语言记为G(M)。

84

3. 作为枚举器的图灵机
规范的顺序(canonical order) 定理 2-7 L为递归可枚举语言的充分必要条件是 存在一个图灵机 M,使得L=G(M)。
?

定理 2-8 一个语言L为递归语言的充分必要条件 是存在一个图灵机M,使得L=G(M),并且L 是被M按照规范顺序产生的。
85

4. 多栈机
?

多栈机(multi-stack machines)是一个拥有一条只读输 入带和多条存储带的不确定图灵机。 – 多栈机的只读带上的读头不能左移。 – 存储带上的读头可以向左和向右移动。
? ?

右移时,一般都在当前注视的带方格上印刷一个非空白 字符。 左移时,必须在当前注视的带方格中印刷空白字符B。

?

一个确定的双栈机(double stack machines)是一个确定 的图灵机,它具有一条只读的输入带和两条存储带。 存储带上的读头左移时,只能印刷空白符号B 。

86

4. 多栈机
?

下推自动机是一种非确定的多带图灵机。它有 一条只读的输入带,一条存储带。

定理 2-9 一个任意的单带图灵机可以被一个确定 的双栈机模拟。

87

5. 计数机
?

计数机(counter machine)
– – –

有一条只读输入带和若干个用于计数的单向无穷带 的离线图灵机。 拥有n个用于计数带的计数机被称为n计数机。 用于计数的带上仅有两种字符,一个为相当于是作 为栈底符号的Z,该字符也可以看作是计数带的首 符号,它仅出现在计数带的最左端;另一个就是空 白符B。这个带上所记的数就是从Z开始到读头当 前位置所含的B的个数。

定理 2-10 图灵机可以被一个双计数机模拟。
88

6.丘奇-图灵论题与随机存取机
? ?

对于任何可以用有效算法解决的问题,都存在解决此 问题的图灵机。 随机存取机(random access machine,RAM)含有无穷 多个存储单元,这些存储单元被按照0、1、2、…进 行编号,每个存储单元可以存放一个任意的整数;有 穷个能够保存任意整数的算术寄存器。这些整数可以 被译码成通常的各类计算机指令。

定理 2-11如果RAM的基本指令都能用图灵机来 实现,那么就可以用图灵机实现RAM。
89

2.3 通用图灵机
?

通用图灵机(universal Turing machine)


实现对所有图灵机的模拟。 它可以在实现对图灵机的表示的同时,实现对该 TM处理的句子的表示。 用0和1对这些除空白符以外的其他的带符号进行编 码。同时也可以用0和1对图灵机的移动函数进行编 码。

?

编码系统




90

2.3 通用图灵机
?

?
?

M=({q1, q2, …, qn}, {0,1}, {0,1,B}, δ,q1 , B , {q2}) 用X1、X2、X3分别表示0、1、B,用D1、D2分 别表示R、L。 δ(qi, Xj)=(qk , Xl, Dm)可以用0i10j10k10l10m表示。

91

2.3 通用图灵机
?

? ?

图灵机M可用 111 code1 11 code2 11 …… 11 coder 111 codet 是动作δ(qi, Xj)=(qk , Xl, Dm)的形如 0i10j10k10l10m的编码。 图灵机M和它的输入串w则可以表示成 111 code1 11 code2 11 …… 11 coder 111w 按照规范顺序分别对表示图灵机的符号行和表 示输入的符号行进行排序。

?

92

2.3 通用图灵机
?

?

Ld={w | w是第j个句子,并且第j个图灵机不接 受它}不是递归可枚举语言。 通用语言(universal language)
– –

Lu={<M,w> | M接受w} <M , w> 为 如 下 形 式 的 串 , 表 示 图 灵 机 M=({q1, q2, …, qn}, {0,1}, {0,1,B}, δ,q1 , B , {q2})和它的 输入串w。

111 code1 11 code2 11 … 11 coder 111w
93

2.3 通用图灵机
?

例 2-12 设图灵机 M2=({ q1, q2, q3, q4}, {0, 1}, {0, 1, B}, δ, q4 , B ,{q3}),其中δ的定义如下: δ(q4, 0)= (q4, 0, R) δ(q4, 1)= (q1, 1, R) δ(q1, 0)= (q1, 0, R) δ(q1, 1)= (q2, 1, R) δ(q2, 0)= (q2, 0, R) δ(q2, 1)= (q3, 1, R)

94

2.3 通用图灵机
?

?

编码为 1110000101000010101100001001010010110101 0101011010010010010110010100101011001001 00010010111 通用图灵机检查M是否接受字符串001101110 1110000101000010101100001001010010110101 0101011010010010010110010100101011001001 00010010111001101110

95

2.4 几个相关的概念
? ? ? ?

可计算性(computability)理论是研究计算的一般性质 的数学理论。计算的过程就是执行算法的过程。 可计算理论的中心问题是建立计算的数学模型,研究 哪些是可计算的,哪些是不可计算的。 可计算理论又称为算法理论(algorithm theory)。 在直观意义下,算法具有有限性、机械可执行性、确 定性、终止性等特征。 可计算问题可以等同于图灵可计算问题。

?

96

2.4 几个相关的概念
? ?

可判定的(decidable)问题


它对应的语言是递归的。 没有这样的算法,它以问题的实例为输入,并能给出相应的 “是”与“否”的判定。

不可判定的(undecidable)


?

递归语言举例 (1)LDFA={<M, w> | M是一个DFA,w是字符串,M 接受w}。 (2)LNFA={<M, w> | M是一个NFA,w是字符串,M 接受w}。

97

2.4 几个相关的概念
(3)LRE={<r, w> | r是一个RE,w是字符串,w是r的 一个句子}。 (4)EDFA={<M> | M是一个DFA,且L(M)=Φ}。 (5)EQDFA={<M1, M2> | M1, M2是DFA,且 L(M1)=L(M2)}。 (6)LCFG={<G, w> | G是一个CFG,w是字符串,G产 生w}。 (7)ECFG={<G> | G是一个CFG,且L(G)=Φ}。

98

2.4 几个相关的概念
?

P类问题(class of P)




P表示确定的图灵机在多项式时间(步数)内可判定 的语言类。这些语言对应的问题成为是P类问题, 这种语言称为多项式可判定的。 例如,判定一个有向图中的两个顶点之间是否存在 有向路的的问题、检查两个数是否互素的问题、判 定一个字符串是否为一个上下文无关语言的句子的 问题都是P类问题。

99

2.4 几个相关的概念
? ?

?
?

10 0

NP类问题(class of NP) NP表示不确定的图灵机在多项式时间(步数)内 可判定的语言类。这些语言对应的问题称为是 NP类问题,也称这些问题是NP复杂的,或者 NP困难的。 这种语言称为非确定性多项式可判定的。 P=NP?是理论计算机科学和当代数学中最大 的悬而未决的问题之一。

2.4 几个相关的概念
?

NP完全问题(NP complete problem)


– – –

10 1



NP类中有某些问题的复杂性与整个类的复杂性相 关联。如果能找到这些问题中的任何一个的多项式 时间判定算法,那么,所有的NP问题都是多项式 时间可以判定的。 TSP(旅行商问题)。 划分问题。 可满足性问题。 带有先次序的调度问题。

2.5 小结
图灵机是一个计算模型,用图灵机可以完成的 计算被称为是图灵可计算的。 (1) 图灵机的基本概念:形式定义、递归可枚 举语言、递归语言、完全递归函数、部分递归 函数。 (2) 构造技术:状态的有穷存储功能的利用、 多道技术、子程序技术。
10 2

2.5 小结
(3) 图灵机的变形:双向无穷带图灵机、多带 图灵机、不确定的图灵机、多维图灵机、多头 图灵机、离线图灵机、多栈图灵机,它们都与 基本图灵机等价。 (4) Church-Turing论题:如果RAM的基本指 令都能用图灵机来实现,则RAM就可以用图 灵机实现。所以,对于任何可以用有效算法解 决的问题,都存在解决此问题的图灵机。 (5) 通用图灵机可以实现对所有图灵机的模拟。 (6) 可计算语言、不可判定性、P-NP问题。

10 3


赞助商链接
相关文章:
更多相关标签: