图灵机(英語:Turing machine),又称确定型图灵机,是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的数学逻辑机,其更抽象的意义为一种计算模型,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
图灵机的艺术表示
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作:
- 在纸上写上或擦除某个符号;
- 把注意力从纸的一处移动到另一处;
而在每个阶段,人要决定下一步的动作,依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。
在某些模型中,纸带移动,而未用到的纸带真正是“空白”的。要进行的指令(q4
)展示在扫描到方格之上(由Kleene(1952)p.375绘制)。
在某些模型中,读写头沿着固定的纸带移动。要进行的指令(q1
)展示在读写头内。在这种模型中“空白”的纸带是全部为0的。有阴影的方格,包括读写头扫描到的空白,标记了1,1,B的那些方格,和读写头符号,构成了系统状态。(由Minsky(1967)p.121绘制)
为了模拟人的这种运算过程,图灵构造出一台假想的机器,该机器由以下几个部分组成:
- 一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子,每个格子上包含一个来自有限字母表的符号,字母表中有一个特殊的符号
表示空白。纸带上的格子从左到右依次被编号为0, 1, 2, ...,纸带的右端可以无限伸展。
- 一个读写头HEAD。它可以在纸带上左右移动,能读出当前所指的格子上的符号,并能改变它。
- 一套控制规则數量有限的TABLE(A finite table of instructions)。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作,并改变状态寄存器的值,令机器进入一个新的状态。
按照以下顺序告知图灵机命令:
- 1. 写入(替换)或擦除当前符号;
- 2. 移动 HEAD, 'L'向左, 'R'向右或者'N'不移动;
- 3. 保持当前状态或者转到另一状态。
- 一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的,并且有一个特殊的状态,称为停机状态。参见停机问题。
注意这个机器的每一部分都是有限的,但它有一个潜在的无限长的纸带,因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。
一台图灵机是一个七元有序组
,其中
都是有限集合,且满足:
是非空有穷状态集合;
是非空有穷输入字母表,其中不包含特殊的空白符
;
是非空有穷带字母表且
;
为空白符,也是唯一允许出现无限次的字符;
是转移函数,其中
表示读写头是向左移还是向右移, - 表示不移动;
是起始状态;
是接受状态。
是拒绝状态,且
。
图灵机
将以如下方式运作:
开始的时候将输入符号串
从左到右依此填在纸带的第
号格子上,其他格子保持空白(即填以空白符
)。
的读写头指向第0号格子,
处于状态
。机器开始运行后,按照转移函数
所描述的规则进行计算。例如,若当前机器的状态为
,读写头所指的格子中的符号为
,设
,则机器进入新状态
,将读写头所指的格子中的符号改为
,然后将读写头向左移动一个格子。若在某一时刻,读写头所指的是第0号格子,但根据转移函数它下一步将继续向左移,这时它停在原地不动。换句话说,读写头始终不移出纸带的左边界。若在某个时刻
根据转移函数进入了状态
,则它立刻停机并接受输入的字符串;
若在某个时刻
根据转移函数进入了状态
,则它立刻停机并拒绝输入的字符串。
注意,转移函数
是一个部分函数,换句话说对于某些
,
,
可能没有定义,如果在运行中遇到下一个操作没有定义的情况,机器将立刻停机。
设
是一台图灵机,
的带描述(tape description)是一个函数
,其中
表示
的带上第
个格子中的符号;
的格局(configuration)是一个三元组
,其中
是当前的带描述,
是当前的状态,
是当前读写头所处的位置;
- 设
,
是
的格局,设
,若满足
,![{\displaystyle e_{2}={\begin{cases}e_{1}-1&d=L\\e_{1}+1&d=R\end{cases}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0b947d133e3937231804c3ab70c659517f701c26)
以及![{\displaystyle F_{2}(i)={\begin{cases}F_{1}(i)&i\neq e_{1}\\x&i=e_{1}\end{cases}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/f0ebd4e232c7b0be8948b6290ce769ae6ab4d4d6)
则称
从格局
产生格局
,记作
。
- 设
为
的格局,若
则称
为接受格局;若
则称
为拒绝格局;接受格局和拒绝格局统称为停机格局。
设
是一台图灵机,将字符串
作为其输入,若存在格局序列
,使得
是
在输入
上的起始格局,即
,其中![{\displaystyle F_{1}(i)={\begin{cases}\omega _{i}&0\leq i\leq n-1\\\square &{\mbox{otherwise}}\end{cases}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/c21cf564e32a3ef450d980e3881279ff1770f7f1)
,其中
;
是接受格局。
则称
接受字符串
,且
称为图灵机
在输入
上的接受计算历史。同理,若
是拒绝格局,则称
拒绝
,且
称为图灵机
在输入
上的拒绝计算历史。
所接受的所有字符串的集合称为
的语言,记作
。
設
和
.
比如做一個以1的個數表示數值的加法運算,在磁带上的数据是0000001110110000,就是3+2的意思。程序
如下:
- 0,0 -> 0,0R
- 0,1 -> 1,1R
- 1,0 -> 10,1R
- 1,1 -> 1,1R
- 10,0 -> 11,0L
- 10,1 -> 10,1R
- 11,0 -> E
- 11,1 -> 0,0S
第一行程序0,0->0,0R意思就是如果機器讀到0,就將其變成0,狀態變為0,讀寫頭向右移動一格. R就是向右移動一格,L就是向左移一格,E是錯誤,S是停機. xx,y -> aa,b中xx是當前狀態, y是當前格子的值, aa是程序下一步的狀態, b是當前格的修改值。
雖然這裡給出與上面不同形式的定義,但兩者是等價的,這裡的定義能完成的工作並不比上面的定義多。
更多信息 步数, 状态(执行前) ...
步数
|
状态(执行前) |
状态(执行后) |
磁带(执行前)
|
磁带(执行后)
|
1
|
0 |
0 |
0000001110110000
|
0000001110110000
|
2
|
0 |
0 |
0000001110110000
|
0000001110110000
|
3
|
0 |
0 |
0000001110110000
|
0000001110110000
|
4
|
0 |
0 |
0000001110110000
|
0000001110110000
|
5
|
0 |
0 |
0000001110110000
|
0000001110110000
|
6
|
0 |
0 |
0000001110110000
|
0000001110110000
|
7
|
0 |
1 |
0000001110110000
|
0000001110110000
|
8
|
1 |
1 |
0000001110110000
|
0000001110110000
|
9
|
1
|
1
|
0000001110110000
|
0000001110110000
|
10
|
1
|
10
|
0000001110110000
|
0000001111110000
|
11
|
10
|
10
|
0000001111110000
|
0000001111110000
|
12
|
10
|
10
|
0000001111110000
|
0000001111110000
|
13
|
10
|
11
|
0000001111110000
|
0000001111110000
|
14
|
11
|
0
|
0000001111110000
|
0000001111100000
|
关闭
除了图灵机以外,人们还发明了很多其它的计算模型。包括:
然而这些模型无一例外地都和图灵机的计算能力等价,因此邱奇,图灵和哥德尔
提出了著名的邱奇-图灵论题:一切直觉上能计算的函数都可用图灵机计算,反之亦然。
- Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem(页面存档备份,存于互联网档案馆), Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David(ed.), The Undecidable, Hewlett, NY: Raven Press, 1965;
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997. ISBN 0-534-94728-X