首页 >
图灵机
✍ dations ◷ 2025-04-03 11:49:49 #图灵机
图灵机(英语: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 }
的图灵机。另一个要注意的是,如果我们允许图灵机的纸带两端都可以无限伸展,这并不能增加图灵机的计算能力,因为我们显然可以用只有纸带一端能无限伸展的图灵机来模拟这种纸带两端都可以无限伸展的图灵机。如果我们允许图灵机的读写头在某一步保持原地不动,那也不会增加其计算能力,因为我们可以用向左移动一次再向右移动一次来代替在原地不动。其它的常见图灵机变种包括:除了图灵机以外,人们还发明了很多其它的计算模型。包括:然而这些模型无一例外地都和图灵机的计算能力等价,因此邱奇,图灵和哥德尔
提出了著名的邱奇-图灵论题:一切直觉上能计算的函数都可用图灵机计算,反之亦然。
相关
- 反义单链RNA病毒核糖核酸病毒(英语:RNA virus),又称RNA病毒,其遗传物质为RNA,这些核糖核酸通常是单链RNA(ssRNA),但是也可能是双链RNA(dsRNA)。由RNA病毒感染造成的著名人类疾病包括艾滋病(AIDS)、埃博
- 酵母亚门酵母亚门是子囊菌门中最低级的菌种,只有单细胞,通常单生,有明显的细胞壁和细胞核,有时数个细胞连成串,形成拟菌丝,以出芽的方式繁殖,芽脱落后就形成新个体,没有子囊果。酵母亚门只包
- 子实层子实层(hymenium),是子囊菌门与担子菌门真菌子实层体上的构造。子实体中,最内侧的组织为菌髓,其外为子实下层(subhymenium),最外侧即为子实层。子实层的部分细胞可发育成担子(英语:bas
- 时态时或时态(Tempus、英语:Tense),是一种语法范畴,在语法里是表示行为发生的时间和说话时的关系。一般分为过去时、现在时、将来时,通常也有与表示动作进行或终止的进行式和完成式等
- 正念疗法正念疗法英文为 Mindfulness,被归类在第三波认知行为疗法,正念是一种专注于当下,全然开放的自我觉察,不需要带有自我批判的心态,改以好奇心和接纳,迎接内心和脑海的每个念头,也就是
- 保健人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学健康是指生物的功能性和代谢效率的水
- 苯乙烯苯乙烯也被称为乙烯基苯,是用苯取代乙烯的一个氢原子形成的有机化合物。室温下,苯乙烯是一种具有甜味的粘稠易挥发液体,但苯乙烯浓度过高时,气味就会变得令人不愉快。苯乙烯中,乙
- 巴黎绿巴黎绿(英语:Paris Green),化学名醋酸亚砷酸铜(英语:Copper(II) acetoarsenite)是一种高毒性的铜盐,常温下为鲜绿色晶体。 虽然巴黎绿有剧毒,但因为价格便宜且天然,因此它曾是一种广泛
- 先兆流产先兆流产指发生于妊娠20周内的阴道出血。先兆流产意味着孕妇流产的风险加大,但经保胎治疗后部分孕妇可继续正常妊娠。大约30%的孕妇曾经历阴道出血的现象。发生先兆流产的孕
- 政府预算政府预算,是一种通常由立法机关批准、行政首脑批准的法律文书,其主要包括一定类型的国家收入和开支。收入和开支是所有预算的核心内容。在许多政府情况,收入主要来自税收。政府