1
11.4 图灵机
? 图灵机的基本模型
? 图灵机接受的语言
—— 递归可枚举语言
? 用图灵机计算函数
—— 部分可计算函数与可计算函数
2
问题的提出
1900年 D,Hilbert 在巴黎第二届数学家大会上提出
著名的 23个问题,
第 10个问题,如何判定整系数多项式是否有整数根?
要求使用“有限次运算的过程”
1970 年证明不存在这样的判定算法,即这个问题是
不可判定的,或不可计算的,
3
计算模型
从 20世纪 30年代先后提出
图灵机 A.M.Turing,1936年
λ转换演算 A.Church,1935年
递归函数 K.G?del,1936年
正规算法 A.A.Markov,1951年
无限寄存器机器 J.C.Shepherdson,1963年
…
4
Church-Turing论题
已经证明这些模型都是等价的,即它们计算
的函数类 (识别的语言类 ) 是相同的,
Church-Turing论题, 直观可计算的函数类
就是图灵机以及任何与图灵机等价的计算模
型可计算 (可定义 ) 的函数类
5
图灵机的基本模型
定义 图灵机 (TM) M=?Q,Σ,Γ,δ,q0,B,A ?,其中
(1) 状态集合 Q,非空有穷集合 ;
(2) 输入字母表 Σ,非空有穷集合 ;
(3) 带字母表 Γ,非空有穷集合且 Σ?Γ;
(4) 初始状态 q0?Q;
控制器
6
图灵机的基本模型 (续 )
(5) 空白符 B?Γ-Σ;
(6) 接受状态集 A?Q;
(7) 动作函数 δ是 Q?Γ到 Γ?{L,R}?Q的部分函数,
即 dom δ ? Q?Σ,
δ(q,s)=(s?,R,q?)的含义, 当处于状态 q,读写头扫视
符号 s时,M的下一步把状态转移到 q?,读写头把这
个 s改写成 s?,并向右移一格 ;
δ(q,s)=(s?,L,q?)的含义类似,只是读写头向左移一
格 ; 若 δ(q,s)没有定义,则 M停机,
7
一个 TM M的 实例 （例 1）
δ 0 1 B
→ q0
q1
q2
*q3
(0,R,q0) (1,R,q0) (B,L,q1)
(B,L,q2) (1,R,q0) (B,R,q0)
(B,L,q3) — —
— — —
8
图灵机的计算
格局, 带的内容,当前的状态和读写头扫视的方格
ζ = αqβ,其中 α,β?Γ*,q?Q
初始格局 ζ0= q0w,其中 w?Σ*是输入字符串
接受格局 ζ = αqβ, q?A
停机格局 ζ = αqsβ, δ(q,s)没有定义
ζ1 ζ2,从 ζ1经过一步能够到达 ζ2,称 ζ2是 ζ1的 后继
ζ1 ζ2,从 ζ1经过若干步能够到达 ζ2
9
图灵机的计算 (续 )
计算, 一个有穷的或无穷的格局序列,序列中的每一
个格局都是前一个格局的后继,
?w?Σ*,M从 ζ0= q0w开始的计算有 3种可能,
(1) 停机在接受格局,即计算为 ζ0,ζ1,…,ζn,其中 ζn是
接受的停机格局 ;
(2) 停机在非接受格局,即计算为 ζ0,ζ1,…,ζn,其中 ζn
是非接受的停机格局 ;
(3) 永不停机,即计算为 ζ0,ζ1,…,ζn,…
10
图灵机接受的语言
定义 ?w?Σ*,如果 M从 ζ0= q0w开始的计算停机在
接受格局,则称 M接受输入串 w,M接受的语言 L(M)
是 M接受的所有输入串,即 L(M)={w?Σ* | M接受 w},
例 1 (续 ) M关于输入 w=10100的计算,
q010100B ? 1q00100B ? 10q0100B ? 101q000B ? 1010q00B
? 10100q0B ? 1010q10B ? 101q20BB ? 101Bq3BB
由于停机在接受格局,故 M接受 10100,
L(M)={w00 | w?{0,1}*}
11
图灵机 接受的语言 (续 )
定义 能被图灵机接受的语言称作 递归可枚举的,
记作 r.e,
定理 语言 L是 r.e.当且仅当 L是 0 型语言,
图灵机与 0 型文法是等价的
12
用图灵机计算函数
Σ上的 m元部分字函数, (Σ*)m的 某个子集到 Σ*的部分函数
TM M计算的 m元部分字函数 f, 设输入字母表为 Σ,
?x1,…,xm?Σ*,如果 M从初始格局 ζ0= q0x1B… xmB开始的计
算停机 (不管是否停机在接受状态 ),从停机时带的内容中
删去 Σ以外的字符,得到字符串 y,则 f(x1,x2,…,xm)=y; 如果
M从初始格局 ζ0开始的计算永不停机,则 f(x1,x2,…,xm)没有
定义,记作 f(x1,x2,…,xm)?,
例 1(续 ) M计算函数, ?x?{0,1}*,
?
?
?
?
?
?
?
?
?
否则
若
若
,
10,1
00,
)( wxw
wxw
xf
13
数论函数
数论函数, 自然数集合 N上的函数
N上的 m元部分函数
N上的 m元全函数, 在 Nm的每一点都有定义
例如 x+y是全函数,x-y是部分函数,当 x<y时,x-y?
一进制表示, 用 1x表示自然数 x
例如 111表示 3,空串 ε表示 0
数论函数的一进制表示,字母表 {1}上的字函数,用一进制表示
自然数
例如 x+y 可表成 f(1x,1y)=1x+y
14
递归函数
定义 设 f 是 N上的 m元部分函数,如果图灵机 M计算 f 的
一进制表示,即 M的输入字母表为 {1},?x1,…,xm?N,
从初始格局 ζ0= 开始,若 f(x1,…,xm)
=y,则 M的计算停机,且停机时带的内容 (不计 {1}以
外的字符 )为 1y; 若 f(x1,…,xm)?,则 M永不停机,那么
称 M以一进制方式计算 f,
定义 图灵机 M以一进制方式计算的 N上的 m元部分函
数称作 部分递归函数,或 部分可计算函数 ; 部分递归
的全函数称作 递归函数,或 可计算函数,
BBBq mxxx 111 210 ?
15
递归函数 (续 )
例 1(续 ) M以一进制方式计算
?
?
?
?
?
?
?
否则
整除但不被整除被若
整除被若
,
4,2,2/
4,4/
)( xx
xx
xf
这是一个部分递归函数,
11.4 图灵机
? 图灵机的基本模型
? 图灵机接受的语言
—— 递归可枚举语言
? 用图灵机计算函数
—— 部分可计算函数与可计算函数
2
问题的提出
1900年 D,Hilbert 在巴黎第二届数学家大会上提出
著名的 23个问题,
第 10个问题,如何判定整系数多项式是否有整数根?
要求使用“有限次运算的过程”
1970 年证明不存在这样的判定算法,即这个问题是
不可判定的,或不可计算的,
3
计算模型
从 20世纪 30年代先后提出
图灵机 A.M.Turing,1936年
λ转换演算 A.Church,1935年
递归函数 K.G?del,1936年
正规算法 A.A.Markov,1951年
无限寄存器机器 J.C.Shepherdson,1963年
…
4
Church-Turing论题
已经证明这些模型都是等价的,即它们计算
的函数类 (识别的语言类 ) 是相同的,
Church-Turing论题, 直观可计算的函数类
就是图灵机以及任何与图灵机等价的计算模
型可计算 (可定义 ) 的函数类
5
图灵机的基本模型
定义 图灵机 (TM) M=?Q,Σ,Γ,δ,q0,B,A ?,其中
(1) 状态集合 Q,非空有穷集合 ;
(2) 输入字母表 Σ,非空有穷集合 ;
(3) 带字母表 Γ,非空有穷集合且 Σ?Γ;
(4) 初始状态 q0?Q;
控制器
6
图灵机的基本模型 (续 )
(5) 空白符 B?Γ-Σ;
(6) 接受状态集 A?Q;
(7) 动作函数 δ是 Q?Γ到 Γ?{L,R}?Q的部分函数,
即 dom δ ? Q?Σ,
δ(q,s)=(s?,R,q?)的含义, 当处于状态 q,读写头扫视
符号 s时,M的下一步把状态转移到 q?,读写头把这
个 s改写成 s?,并向右移一格 ;
δ(q,s)=(s?,L,q?)的含义类似,只是读写头向左移一
格 ; 若 δ(q,s)没有定义,则 M停机,
7
一个 TM M的 实例 （例 1）
δ 0 1 B
→ q0
q1
q2
*q3
(0,R,q0) (1,R,q0) (B,L,q1)
(B,L,q2) (1,R,q0) (B,R,q0)
(B,L,q3) — —
— — —
8
图灵机的计算
格局, 带的内容,当前的状态和读写头扫视的方格
ζ = αqβ,其中 α,β?Γ*,q?Q
初始格局 ζ0= q0w,其中 w?Σ*是输入字符串
接受格局 ζ = αqβ, q?A
停机格局 ζ = αqsβ, δ(q,s)没有定义
ζ1 ζ2,从 ζ1经过一步能够到达 ζ2,称 ζ2是 ζ1的 后继
ζ1 ζ2,从 ζ1经过若干步能够到达 ζ2
9
图灵机的计算 (续 )
计算, 一个有穷的或无穷的格局序列,序列中的每一
个格局都是前一个格局的后继,
?w?Σ*,M从 ζ0= q0w开始的计算有 3种可能,
(1) 停机在接受格局,即计算为 ζ0,ζ1,…,ζn,其中 ζn是
接受的停机格局 ;
(2) 停机在非接受格局,即计算为 ζ0,ζ1,…,ζn,其中 ζn
是非接受的停机格局 ;
(3) 永不停机,即计算为 ζ0,ζ1,…,ζn,…
10
图灵机接受的语言
定义 ?w?Σ*,如果 M从 ζ0= q0w开始的计算停机在
接受格局,则称 M接受输入串 w,M接受的语言 L(M)
是 M接受的所有输入串,即 L(M)={w?Σ* | M接受 w},
例 1 (续 ) M关于输入 w=10100的计算,
q010100B ? 1q00100B ? 10q0100B ? 101q000B ? 1010q00B
? 10100q0B ? 1010q10B ? 101q20BB ? 101Bq3BB
由于停机在接受格局,故 M接受 10100,
L(M)={w00 | w?{0,1}*}
11
图灵机 接受的语言 (续 )
定义 能被图灵机接受的语言称作 递归可枚举的,
记作 r.e,
定理 语言 L是 r.e.当且仅当 L是 0 型语言,
图灵机与 0 型文法是等价的
12
用图灵机计算函数
Σ上的 m元部分字函数, (Σ*)m的 某个子集到 Σ*的部分函数
TM M计算的 m元部分字函数 f, 设输入字母表为 Σ,
?x1,…,xm?Σ*,如果 M从初始格局 ζ0= q0x1B… xmB开始的计
算停机 (不管是否停机在接受状态 ),从停机时带的内容中
删去 Σ以外的字符,得到字符串 y,则 f(x1,x2,…,xm)=y; 如果
M从初始格局 ζ0开始的计算永不停机,则 f(x1,x2,…,xm)没有
定义,记作 f(x1,x2,…,xm)?,
例 1(续 ) M计算函数, ?x?{0,1}*,
?
?
?
?
?
?
?
?
?
否则
若
若
,
10,1
00,
)( wxw
wxw
xf
13
数论函数
数论函数, 自然数集合 N上的函数
N上的 m元部分函数
N上的 m元全函数, 在 Nm的每一点都有定义
例如 x+y是全函数,x-y是部分函数,当 x<y时,x-y?
一进制表示, 用 1x表示自然数 x
例如 111表示 3,空串 ε表示 0
数论函数的一进制表示,字母表 {1}上的字函数,用一进制表示
自然数
例如 x+y 可表成 f(1x,1y)=1x+y
14
递归函数
定义 设 f 是 N上的 m元部分函数,如果图灵机 M计算 f 的
一进制表示,即 M的输入字母表为 {1},?x1,…,xm?N,
从初始格局 ζ0= 开始,若 f(x1,…,xm)
=y,则 M的计算停机,且停机时带的内容 (不计 {1}以
外的字符 )为 1y; 若 f(x1,…,xm)?,则 M永不停机,那么
称 M以一进制方式计算 f,
定义 图灵机 M以一进制方式计算的 N上的 m元部分函
数称作 部分递归函数,或 部分可计算函数 ; 部分递归
的全函数称作 递归函数,或 可计算函数,
BBBq mxxx 111 210 ?
15
递归函数 (续 )
例 1(续 ) M以一进制方式计算
?
?
?
?
?
?
?
否则
整除但不被整除被若
整除被若
,
4,2,2/
4,4/
)( xx
xx
xf
这是一个部分递归函数,
