图灵机
抽象計算模型 来自维基百科,自由的百科全书
Remove ads
抽象計算模型 来自维基百科,自由的百科全书
图灵机(英語:Turing machine),又称确定型图灵机,是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的数理逻辑机,其更抽象的意义为一种计算模型,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
此條目需要补充更多来源。 (2019年1月4日) |
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作:
而在每个阶段,人要决定下一步的动作,依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。
为了模拟人的这种运算过程,图灵构造出一台假想的机器,该机器由以下几个部分组成:
注意这个机器的每一部分都是有限的,但它有一个潜在的无限长的纸带,因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。
一台图灵机是一个七元有序组,其中都是有限集合,且满足:
图灵机将以如下方式运作:
开始的时候将输入符号串 从左到右依此填在纸带的第号格子上,其他格子保持空白(即填以空白符)。 的读写头指向第0号格子, 处于状态。机器开始运行后,按照转移函数所描述的规则进行计算。例如,若当前机器的状态为,读写头所指的格子中的符号为,设,则机器进入新状态,将读写头所指的格子中的符号改为,然后将读写头向左移动一个格子。若在某一时刻,读写头所指的是第0号格子,但根据转移函数它下一步将继续向左移,这时它停在原地不动。换句话说,读写头始终不移出纸带的左边界。若在某个时刻根据转移函数进入了状态,则它立刻停机并接受输入的字符串; 若在某个时刻根据转移函数进入了状态,则它立刻停机并拒绝输入的字符串。
注意,转移函数是一个部分函数,换句话说对于某些,,可能没有定义,如果在运行中遇到下一个操作没有定义的情况,机器将立刻停机。
设是一台图灵机,
以及
则称从格局 产生格局,记作。
设是一台图灵机,将字符串 作为其输入,若存在格局序列,使得
则称 接受字符串,且称为图灵机在输入上的接受计算历史。同理,若是拒绝格局,则称 拒绝,且称为图灵机在输入上的拒绝计算历史。所接受的所有字符串的集合称为的语言,记作。
設和. 比如做一個以1的個數表示數值的加法運算,在磁带上的数据是0000001110110000,就是3+2的意思。程序如下:
第一行程序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 |
对于任意一个图灵机,因为它的描述是有限的,因此我们总可以用某种方式将其编码为字符串。我们用表示图灵机的编码。
我们可以构造出一个特殊的图灵机,它接受任意一个图灵机的编码,然后模拟圖靈機的运作,这样的图灵机称为通用图灵机(Universal Turing Machine)。现代电子计算机的计算模型其实就是这样一种通用图灵机,它先接受一段描述另一图灵机,例如圖靈機的action table的字串,然後运行寫給圖靈機的程序,這樣通用圖靈機執行程序就像圖靈機一樣,能正確執行並实现程序所描述的算法。
图灵机有很多变种,但可以证明这些变种的计算能力都是等价的,即它们识别同样的语言类。证明两个计算模型和的计算能力等价的基本思想是:用和相互模拟,若可模拟且可模拟,显然他们的计算能力等价。注意这里我们暂时不考虑计算的效率,只考虑计算的理论上“可行性”。
首先我们可以发现,改变图灵机的带字母表并不会改变其计算能力。例如我们可以限制图灵机的带字母表为,这并不会改变图灵机的计算能力,因为我们显然可以用带字母表为的图灵机模拟带字母表为任意有限集合的图灵机。
另一个要注意的是,如果我们允许图灵机的纸带两端都可以无限伸展,这并不能增加图灵机的计算能力,因为我们显然可以用只有纸带一端能无限伸展的图灵机来模拟这种纸带两端都可以无限伸展的图灵机。
如果我们允许图灵机的读写头在某一步保持原地不动,那也不会增加其计算能力,因为我们可以用向左移动一次再向右移动一次来代替在原地不动。
其它的常见图灵机变种包括:
除了图灵机以外,人们还发明了很多其它的计算模型。包括:
然而这些模型无一例外地都和图灵机的计算能力等价,因此邱奇,图灵和哥德尔 提出了著名的邱奇-图灵论题:一切直觉上能计算的函数都可用图灵机计算,反之亦然。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.