首页 >
图灵机
✍ dations ◷ 2024-07-05 04:04:10 #图灵机
图灵机(英语: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 }
的图灵机。另一个要注意的是,如果我们允许图灵机的纸带两端都可以无限伸展,这并不能增加图灵机的计算能力,因为我们显然可以用只有纸带一端能无限伸展的图灵机来模拟这种纸带两端都可以无限伸展的图灵机。如果我们允许图灵机的读写头在某一步保持原地不动,那也不会增加其计算能力,因为我们可以用向左移动一次再向右移动一次来代替在原地不动。其它的常见图灵机变种包括:除了图灵机以外,人们还发明了很多其它的计算模型。包括:然而这些模型无一例外地都和图灵机的计算能力等价,因此邱奇,图灵和哥德尔
提出了著名的邱奇-图灵论题:一切直觉上能计算的函数都可用图灵机计算,反之亦然。
相关
- 岛屿地区岛屿地区(Insular area)特指那些其不属于美国五十州以及联邦特区的美国领土。因为这些有人居住的岛屿地区,是非合并建制领土,所以这些地区本土出生的居民不被美国宪法承认为美国
- 废料放射性废料是一种包含放射性物质的废料,一般在如核裂变一类的核反应中产生。事实上,一些不与核工业直接关联的的产业在各自的生产活动中也会排放出一定量的放射性废料。放射性
- 谷氨酰胺合成酶结构 / ECOD结构 / ECOD谷氨酰胺合成酶(英语:glutamine synthetase,GS)是一种控制氮代谢的酶。谷氨酰胺这种氨基酸,不仅被细胞用来合成蛋白质,也是用来运输氮的。自由的铵离子对生
- Sc3d1 4s22,8,9,2蒸气压第一:633.1 kJ·mol−1 第二:1235.0 kJ·mol−1 第三:2388.6 kJ·mol−1 (主条目:钪的同位素钪(Scandium),其命名Scandium源自斯堪的纳维亚半岛的拉丁文名称Sc
- 发声与多种运动联合抽动障碍图雷特氏综合征(英语:Tourette Syndrome、TS),又称抽动症、托雷氏症、杜雷氏症,是一种抽动综合症(Tics)。这是一种遗传性的神经内科疾病,通常发生于学龄前至青春期前。有一部分的患
- 高棉语柬埔寨高棉语(高棉语:ភាសាខ្មែរ,高棉语发音:)是高棉族的语言,亦是以高棉人为主体民族的柬埔寨的官方语言和通用语言,故亦称柬埔寨语、柬语。高棉语属于南亚语系孟-高棉语
- 辣薄荷M. piperita (L.) Huds. M. balsamea Willd.辣薄荷(学名:Mentha × piperita,又名胡椒薄荷,英语:Peppermint)唇形科年生草本植物,是一种被广泛种植的混种薄荷,原产于欧洲,可用于食物
- 军事工程军事工程(Military engineering)可以大致定义为设计及建立军事设施及设备,维持军事运输及通讯的艺术、工程及实务。军事工程也要负责军事战术的后勤。现代的军事工程和土木工程
- 威拉米特河威拉米特河(Willamette River),源出美国喀斯喀特山脉,由Coast河(Coast)和Middle河(Middle)等河汇合而成,流经俄勒冈州西南部。在波特兰(Portland)西北注入哥伦比亚河。长约480公里,沿河
- 让-弗朗索瓦·米勒让-弗朗索瓦·米勒(法语:Jean-François Millet,1814年10月4日-1875年1月20日)法国巴比松派画家。他以写实手法描绘的乡村风俗画闻名法国画坛,被认为是写实主义艺术运动的参与者。