首页 >
图灵机
✍ dations ◷ 2025-04-02 11:20:23 #图灵机
图灵机(英语:Turing machine),又称确定型图灵机,是英国数学家艾伦·图灵于1936年提出的一种将人的计算行为抽象掉的数学逻辑机,其更抽象的意义为一种计算模型,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作:而在每个阶段,人要决定下一步的动作,依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。为了模拟人的这种运算过程,图灵构造出一台假想的机器,该机器由以下几个部分组成:注意这个机器的每一部分都是有限的,但它有一个潜在的无限长的纸带,因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。一台图灵机是一个七元有序组
(
Q
,
Σ
,
Γ
,
δ
,
q
0
,
q
a
c
c
e
p
t
,
q
r
e
j
e
c
t
)
{displaystyle (Q,Sigma ,Gamma ,delta ,q_{0},q_{accept},q_{reject})}
,其中
Q
,
Σ
,
Γ
{displaystyle Q,Sigma ,Gamma }
都是有限集合,且满足:图灵机
M
=
(
Q
,
Σ
,
Γ
,
δ
,
q
0
,
q
a
c
c
e
p
t
,
q
r
e
j
e
c
t
)
{displaystyle M=(Q,Sigma ,Gamma ,delta ,q_{0},q_{accept},q_{reject})}
将以如下方式运作:开始的时候将输入符号串
ω
=
ω
0
ω
1
…
ω
n
−
1
∈
Σ
∗
{displaystyle omega =omega _{0}omega _{1}ldots omega _{n-1}in Sigma ^{*}}
从左到右依此填在纸带的第
0
,
1
,
…
,
n
−
1
{displaystyle 0,1,ldots ,n-1}
号格子上,其他格子保持空白(即填以空白符
◻
{displaystyle square }
)。
M
{displaystyle M}
的读写头指向第0号格子,
M
{displaystyle M}
处于状态
q
0
{displaystyle q_{0}}
。机器开始运行后,按照转移函数
δ
{displaystyle delta }
所描述的规则进行计算。例如,若当前机器的状态为
q
{displaystyle q}
,读写头所指的格子中的符号为
x
{displaystyle x}
,设
δ
(
q
,
x
)
=
(
q
′
,
x
′
,
L
)
{displaystyle delta (q,x)=(q',x',L)}
,则机器进入新状态
q
′
{displaystyle q'}
,将读写头所指的格子中的符号改为
x
′
{displaystyle x'}
,然后将读写头向左移动一个格子。若在某一时刻,读写头所指的是第0号格子,但根据转移函数它下一步将继续向左移,这时它停在原地不动。换句话说,读写头始终不移出纸带的左边界。若在某个时刻
M
{displaystyle M}
根据转移函数进入了状态
q
a
c
c
e
p
t
{displaystyle q_{accept}}
,则它立刻停机并接受输入的字符串;
若在某个时刻
M
{displaystyle M}
根据转移函数进入了状态
q
r
e
j
e
c
t
{displaystyle q_{reject}}
,则它立刻停机并拒绝输入的字符串。注意,转移函数
δ
{displaystyle delta }
是一个部分函数,换句话说对于某些
q
{displaystyle q}
,
x
{displaystyle x}
,
δ
(
q
,
x
)
{displaystyle delta (q,x)}
可能没有定义,如果在运行中遇到下一个操作没有定义的情况,机器将立刻停机。设
M
=
(
Q
,
Σ
,
Γ
,
δ
,
q
0
,
q
a
c
c
e
p
t
,
q
r
e
j
e
c
t
)
{displaystyle M=(Q,Sigma ,Gamma ,delta ,q_{0},q_{accept},q_{reject})}
是一台图灵机,e
2
=
{
e
1
−
1
d
=
L
e
1
+
1
d
=
R
{displaystyle e_{2}={begin{cases}e_{1}-1&d=L\e_{1}+1&d=Rend{cases}}}
F
2
(
i
)
=
{
F
1
(
i
)
i
≠
e
1
x
i
=
e
1
{displaystyle F_{2}(i)={begin{cases}F_{1}(i)&ineq e_{1}\x&i=e_{1}end{cases}}}
设
M
{displaystyle M}
是一台图灵机,将字符串
ω
=
ω
0
ω
1
…
ω
n
−
1
{displaystyle omega =omega _{0}omega _{1}ldots omega _{n-1}}
作为其输入,若存在格局序列
C
1
,
C
2
,
…
,
C
k
{displaystyle C_{1},C_{2},ldots ,C_{k}}
,使得F
1
(
i
)
=
{
ω
i
0
≤
i
≤
n
−
1
◻
otherwise
{displaystyle F_{1}(i)={begin{cases}omega _{i}&0leq ileq n-1\square &{mbox{otherwise}}end{cases}}}
则称
M
{displaystyle M}
接受字符串
ω
{displaystyle omega }
,且
C
1
,
C
2
,
…
,
C
k
{displaystyle C_{1},C_{2},ldots ,C_{k}}
称为图灵机
M
{displaystyle M}
在输入
ω
{displaystyle omega }
上的接受计算历史。同理,若
C
k
{displaystyle C_{k}}
是拒绝格局,则称
M
{displaystyle M}
拒绝
ω
{displaystyle omega }
,且
C
1
,
C
2
,
…
,
C
k
{displaystyle C_{1},C_{2},ldots ,C_{k}}
称为图灵机
M
{displaystyle M}
在输入
ω
{displaystyle omega }
上的拒绝计算历史。
M
{displaystyle M}
所接受的所有字符串的集合称为
M
{displaystyle M}
的语言,记作
L
(
M
)
{displaystyle L(M)}
。设
M
=
(
{
0
,
1
,
10
,
11
}
,
{
0
,
1
}
,
{
0
,
1
,
◻
}
,
δ
,
0
,
,
)
{displaystyle M=({0,1,10,11},{0,1},{0,1,square },delta ,0,,)}
和
δ
:
{
0
,
1
,
10
,
11
}
×
{
0
,
1
}
→
{
0
,
1
,
10
,
11
}
×
{
0
,
1
}
×
{
R
,
L
,
E
,
S
}
{displaystyle delta :{0,1,10,11}times {0,1}to {0,1,10,11}times {0,1}times {R,L,E,S}}
.
比如做一个以1的个数表示数值的加法运算,在磁带上的数据是0000001110110000,就是3+2的意思。程序
δ
{displaystyle delta }
如下:第一行程序0,0->0,0R意思就是如果机器读到0,就将其变成0,状态变为0,读写头向右移动一格. R就是向右移动一格,L就是向左移一格,E是错误,S是停机. xx,y -> aa,b中xx是当前状态, y是当前格子的值, aa是程序下一步的状态, b是当前格的修改值。虽然这里给出与上面不同形式的定义,但两者是等价的,这里的定义能完成的工作并不比上面的定义多。对于任意一个图灵机,因为它的描述是有限的,因此我们总可以用某种方式将其编码为字符串。我们用
⟨
M
⟩
{displaystyle langle Mrangle }
表示图灵机
M
{displaystyle M}
的编码。我们可以构造出一个特殊的图灵机,它接受任意一个图灵机
M
{displaystyle M}
的编码
⟨
M
⟩
{displaystyle langle Mrangle }
,然后模拟
M
{displaystyle M}
的运作,这样的图灵机称为通用图灵机(Universal Turing Machine)。现代电子计算机的计算模型其实就是这样一种通用图灵机,它能接受一段描述其他图灵机的程序,并运行程序实现该程序所描述的算法。图灵机有很多变种,但可以证明这些变种的计算能力都是等价的,即它们识别同样的语言类。证明两个计算模型
A
{displaystyle A}
和
B
{displaystyle B}
的计算能力等价的基本思想是:用
A
{displaystyle A}
和
B
{displaystyle B}
相互模拟,若
A
{displaystyle A}
可模拟
B
{displaystyle B}
且
B
{displaystyle B}
可模拟
A
{displaystyle A}
,显然他们的计算能力等价。注意这里我们暂时不考虑计算的效率,只考虑计算的理论上“可行性”。首先我们可以发现,改变图灵机的带字母表并不会改变其计算能力。例如我们可以限制图灵机的带字母表为
{
0
,
1
}
{displaystyle {0,1}}
,这并不会改变图灵机的计算能力,因为我们显然可以用带字母表为
{
0
,
1
}
{displaystyle {0,1}}
的图灵机模拟带字母表为任意有限集合
Γ
{displaystyle Gamma }
的图灵机。另一个要注意的是,如果我们允许图灵机的纸带两端都可以无限伸展,这并不能增加图灵机的计算能力,因为我们显然可以用只有纸带一端能无限伸展的图灵机来模拟这种纸带两端都可以无限伸展的图灵机。如果我们允许图灵机的读写头在某一步保持原地不动,那也不会增加其计算能力,因为我们可以用向左移动一次再向右移动一次来代替在原地不动。其它的常见图灵机变种包括:除了图灵机以外,人们还发明了很多其它的计算模型。包括:然而这些模型无一例外地都和图灵机的计算能力等价,因此邱奇,图灵和哥德尔
提出了著名的邱奇-图灵论题:一切直觉上能计算的函数都可用图灵机计算,反之亦然。
相关
- 细胞死亡细胞死亡(Cell death)是描述生物细胞永久中止运作生理功能的状态。细胞死亡可能起因于个体计划性的细胞死亡,或是因疾病或创伤导致细胞不可逆的损伤而死亡。Category:Medical a
- 双胍类双胍类(英语:biguanides)是可以只一种分子或者是一系列基于这个分子所发展的药物。此类药物可以做为糖尿病或前期糖尿病的治疗药物;也可以作为抗疟疾药物。过去几个世纪,山羊豆(学
- 雪雪是降水形式的一种,是从云中降落的结晶状固体冰,常以雪花的形式存在。雪是由小的冰颗粒物构成,是一种颗粒材料(英语:granular material),它的结构开放,因此显得柔软。因为气温和湿
- 加拿大原住民音节文字加拿大原住民音节文字(Canadian Aboriginal syllabics),是一系列的音节文字,用于书写几种加拿大境内原住民语言,这些语言分别属于阿尔冈昆语族、爱斯基摩-阿留申语系和德内语支。
- 坦贾武尔坦贾武尔(泰米尔语:தஞ்சாவூர்;Thanjavur, Tanjore)是印度泰米尔纳德邦的城市之一,位于高韦里河(Kaveri)的南岸,曾经是朱罗王朝的国都。坦贾武尔的布里哈迪希瓦拉神庙1987年
- 北亚哥曼古须塔屋·北亚哥曼(Gustav Bergmann,1906年5月4日-1987年4月21日),奥地利犹太裔哲学家,维也纳圈成员之一,主要贡献为本体论。
- 电机电机(Electric Machine),是机械能与电能之间转换装置的通称。转换是双向的,大部分应用的是电磁感应原理。由机械能转换成电能的电机,通常称做“发电机”;把电能转换成机械能的电机
- 复系群多系群(英语:Polyphyletic group)在生物系统发生学中,是指一个分类群当中的成员,在演化树上分别位于相隔着其他分支的分支上;也就是说,该分类群并不包含其所有成员的最近共同祖先
- 异域物种形成现代生物分类群体从它们的 共同祖先遗传分化的图示。进化论介绍(英语:Introduction to evolution) 演化的证据 共同起源 共同起源的证据群体遗传学 · 遗传多样性 突变 · 自
- 引力助推在航天动力学和宇宙空间动力学中,所谓的重力助推(gravity assist;也被称为重力弹弓效应或绕行星变轨)是利用行星或其他天体的相对运动和引力改变飞行器的轨道和速度,以此来节省燃