“图灵机”,究竟是什么?
“图灵机”,究竟是什么?
图灵机是计算机科学中的一个基础概念,它不仅是理解计算本质的关键,还为算法、复杂性理论、形式语言等多个领域提供了理论基础。本文将通过多个实例,深入浅出地解释图灵机的工作原理及其重要性。
图灵机的重要性
- 图灵机是计算机科学的基础概念,帮助我们理解计算的本质。
- 它让我们能够更清楚地理解算法,因为任何算法都可以看作是一个图灵机。
- 图灵机是复杂性理论的基础,帮助我们讨论算法的效率和复杂度。
- 它与形式语言、自动机理论等领域紧密相关,对于理解编程语言、编译器设计等非常重要。
- 图灵机提供了一个框架,让我们可以比较不同的计算机模型。
- 它不仅是一个技术概念,还具有深刻的历史和哲学意义,与人工智能的起源、计算的哲学问题都有关。
图灵机的构成
- 纸带(Tape):一个理论上无限长的纸带,被划分成许多单元格,每个单元格可以存储一个符号。
- 读写头(Head):一个可以沿着纸带左右移动的读写头,用于读取、写入或擦除纸带上的符号。
- 状态寄存器(State Register):一个有限的状态集合,图灵机在任何时刻都处于这些状态之一。
- 转移函数(Transition Function):一个规则集合,它根据当前的状态和读写头读取的符号来确定图灵机的下一个动作,包括改变状态、在纸带上写入符号以及移动读写头的方向。
图灵机实例
简单的二进制转换
我们假设状态有两个:0或1
纸带上的符号:0或1。
规则(转移函数):
- 初始时图灵机状态为0。
- 当读写头读取纸带格子为空时,如果图灵机状态为0,则读写头写入0,再将图灵机状态改变为1。如果图灵机状态为1,则读写头写入1,再将图灵机状态改变为0。最后读写头向左移动一个并读取符号
- 当读写头读取纸带上的符号为0时,图灵机的状态变为1,纸带向左移动一格,当读写头读取纸带上的符号为1时,图灵机的状态变为0,纸带向左移动一格。
第一步我们读取到了0,图灵机状态变成了1,读写头向左移动一格。
第二步我们读取到了1,图灵机状态变成了0,读写头向左移动一格。
第三步我们读取到了1,图灵机状态变成了0,读写头向左移动一格。
第四步我们读取到空,由于状态为零,故写入纸带0,状态改为1,读写头向左移动一格。
第五步我们读取到空,由于状态为零,故写入纸带1,状态改为零,读写头向左移动一格。
Cambridge大学的图灵机教程
这个例子来源于Computer laboratory of university of Cambridge,读者可以自行阅读。
原网址:https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html
翻译:https://zhuanlan.zhihu.com/p/33288542
二维世界的虫子举例
让虫子代替读写头,进一步具象化图灵机的工作原理
根据图灵机的特点,我们可以假设:
虫子所处的二维世界是一个无限长的纸带,这个纸带上被分成了若干小的方格,而每个方格都仅仅只有黑和白两种颜色。纸带的片段为:
虫子的感官只有眼睛,并且它的视力很短,只能看到当前格子的颜色
虫子可以向前爬一个格子或向后爬一个格子
虫子的操作系统、程序为:我们假设黑色是食物区,虫子吃到食物后前移一格,白色是空白区,没有食物后退一格
输入 输出
黑色 前移一格
白色 后移一格
在这个情况中格子的颜色是虫子的输入信息,集合为IN={黑色,白色},输出集合为 OUT= {前移一格,后移一格}
从开始位置开始,虫子会怎么移动呢?
- 开始是黑色,虫子前移一格,到达第2格
- 第2还是黑色,虫子前移一格,到达第3格
- 第3格还是黑色,虫子前移一格,到达第4格
- 第4格为白色,虫子后移一格,回到第3格
- 可见,这条带子上,虫子在第4格和第3格来回移动,循环不止。
现实中,虫子肯定不会真的无限循环,虫子会有饥饿、吃饱的感受,食物吃了后也会消失。因此我们在情况下中改进下模型。 - 虫子在黑色的格子时,如果是饥饿状态,吃掉食物把格子变成白色;如果是吃饱状态,后移一格
- 虫子在白色的格子时,如果是饥饿状态,停下来等食物长出来涂黑;如果是吃饱状态,前移一格
- 虫子的操作系统、程序为:
输入 当前状态 输出 下一个状态
黑色 吃饱 后移一格 饥饿
黑色 饥饿 吃完食物格子变白(不移动) 吃饱
白色 吃饱 前移一格 饥饿
白色 饥饿 等待食物长出来涂黑(不移动) 吃饱
在这种情况中,输入集合为IN={黑色,白色},输出集合为 OUT= {前移一格,后移一格,吃掉食物涂白,等待食物长出来涂黑},内部状态S={吃饱,饥饿}
二维纸带不变,从初始位置开始,虫子初始是饥饿状态,虫子会怎么移动呢?
- 第1格是黑色,虫子饥饿,吃掉食物格子变白,虫子新状态为吃饱
- 第1格为白色,虫子吃饱,虫子前移一格,到达第2格,虫子新状态为饥饿
- 第2格为黑色,虫子饥饿,吃掉食物格子变白,虫子新状态为吃饱
- 第2格为白色,虫子吃饱,虫子前移一格,到达第3格,虫子新状态为饥饿
- 第3格为黑色,虫子饥饿,吃掉食物格子变白,虫子新状态为吃饱
- 第3格为白色,虫子吃饱,虫子前移一格,到达第4格,虫子新状态为饥饿
- 第4格为白色,虫子饥饿,等待食物长出来涂黑,虫子新状态为吃饱
- 第4格为黑色,虫子吃饱,虫子后退一格,到达第3格,虫子新状态为饥饿
- 这时,第3格已经长出来食物,是黑色,因此流程和第5步的情况一样了
情况二中,小虫的行为虽然比情况一,复杂了一些,但小虫最后仍然会落入无限循环当中。
到此,如果你已经彻底搞懂了二维虫子是怎么移动的,那么你已经明白了图灵机的工作原理了!因为从本质上讲,最后的小虫模型就是一个图灵机!
注:此段引用自https://zhuanlan.zhihu.com/p/525834950
图灵完备
图灵完备是指在可计算性理论里,一系列操作数据的规则(如指令集、编程语言、细胞自动机)按照一定的顺序,可以计算出结果。这个词源于引入图灵机概念的数学家艾伦·图灵。虽然图灵机会受到储存能力的物理限制,图灵完全性通常指"具有无限存储能力的通用物理机器或编程语言"。
图灵指在可计算性理论中,编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之,此系统可与通用图灵机互相模拟。
简单地定性来说,图灵完备就是可以抽象成图灵机的系统或编程语言,可以解决一切可计算问题。相反,缺乏条件而无法抽象成图灵机的,就不是图灵完备,因为他是不可计算的。很多语言,像python,java,c/c++,javascript等,就是图灵完备的,相反,Bitcoin Script就不是图灵完备的了。
思考
我们可以看到图灵机的无限潜力。想想前面的虫子,即使不断地为他添置条件使之复杂,最终仍旧是一个可以被计算的问题。那么不断地丰富,最终是否可以抽象出一个可以被计算的人呢?
这个问题值得思考。我们想想那四个关键点,输入集合、输出集合、内部状态、固定的程序指令。要想让一个人可以被计算,那么他周围的环境,即输入输出集合就得当作是规则而非完全不可计算的,还要认为他的内部状态也十分稳定,最后他的大脑还必须一成不变。
这么一想,想必我们都已经有了答案。但是对于人工智能来说,情况就不一样了。人工智能的输入输出都是有限的,内部状态也是一个有限的集合。它的程序指令在每个特定的版本里都是不会变化的。那么显而易见,它是可计算,可预测的。
在如今人工智能大热的情况下,我们也许确实得想想关于它的基础性问题。思考,学习,才能更新我们的大脑,才能不让我们变得可计算,才能让我们有别于人工智能。