首页 >
图灵机
✍ dations ◷ 2025-07-19 07:37:16 #图灵机
图灵机(英语: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 }
的图灵机。另一个要注意的是,如果我们允许图灵机的纸带两端都可以无限伸展,这并不能增加图灵机的计算能力,因为我们显然可以用只有纸带一端能无限伸展的图灵机来模拟这种纸带两端都可以无限伸展的图灵机。如果我们允许图灵机的读写头在某一步保持原地不动,那也不会增加其计算能力,因为我们可以用向左移动一次再向右移动一次来代替在原地不动。其它的常见图灵机变种包括:除了图灵机以外,人们还发明了很多其它的计算模型。包括:然而这些模型无一例外地都和图灵机的计算能力等价,因此邱奇,图灵和哥德尔
提出了著名的邱奇-图灵论题:一切直觉上能计算的函数都可用图灵机计算,反之亦然。
相关
- 慢性疲劳综合征慢性疲劳(倦)症候群(英语:chronic fatigue syndrome, CFS、myalgic encephalomyelitis (ME)),又称为肌痛性脑脊髓炎(myalgic encephalomyelitis),(脊髓炎是有争议的,另一种说法为可
- DNA微阵列DNA微阵列(DNA microarray)又称DNA阵列或DNA芯片,比较常用的名字是基因芯片(gene chip)。是一块带有DNA微阵列(microarray)的特殊玻璃片或硅芯片片,在数平方公分之面积上布放数千或
- A01A·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码A01(口腔病药物)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO Collabor
- 跳婴儿节跳婴儿节(西班牙语:El Colacho),原意为魔鬼的跳跃(西班牙语:El Salto del Colacho),是西班牙传统的节日,最早可追溯至1620年,这个节庆的目的是用来庆祝举行在布哥斯省布哥斯卡斯特里略
- 南猿南猿,又称南方古猿类,是指两个非常接近的人亚族:南猿的祖先有可能是440万年前的地猿。人属有可能是于350万年前由南猿的祖先,即肯尼亚平脸人演化而来。另一个可能性是人属直接由
- 行为学派行为主义(英语:Behaviorism)又称作行为论,是20世纪初起源于美国的心理学流派,主张心理学应该研究可以被观察和直接测量的行为,反对研究没有科学根据的意识。其主要特色为以系统方
- 豹1型坦克豹1(德语:Leopard 1)是西德于冷战时期研制的一种主战坦克,它于1965年开始生产,是联邦德国在第二次世界大战重建军队后首款研发出来的主力坦克。豹1总共投入到全世界4个大陆11个国
- 鉈4f14 5d10 6s2 6p12, 8, 18, 32, 18, 3蒸气压第一:589.4 kJ·mol−1 第二:1971 kJ·mol−1 第三:2878 kJ·mol主条目:铊的同位素铊(拼音:tā,注音:ㄊㄚ,粤拼:taa1;英语:thallium)是化
- 杰斐逊县杰斐逊县(Jefferson County, Georgia)是位于美国佐治亚州东北部的一个县。面积1,372平方公里。根据美国人口调查局2000年统计,共有人口17,266人。县治路易斯维尔。成立于1796年
- 科西嘉坐标:42°9′N 9°5′E / 42.150°N 9.083°E / 42.150; 9.083科西嘉领土集体(Collectivité Territoriale de Corse)是法国的一个领土集体,其范围包括科西嘉岛及附近小岛。科西