“图灵机”，究竟是什么？
“图灵机”，究竟是什么？
图灵机是计算机科学的基础概念，它能够帮我们理解计算到底是怎么一回事。就像数学里的加减乘除，图灵机是计算机科学里的基本概念。
想必大部分人理工科专业的大学生都在计算机这门课上听说过“图灵机”这个概念。那么，不知有没有人想过它为什么是计算机学科里必学的一个概念呢？这其实并不难理解，只要你稍微了解一下它的成就和背景，就会对此坚定不移了。
首先，我们要明白，图灵机是计算机科学的基础概念，它能够帮我们理解计算到底是怎么一回事。就像数学里的加减乘除，图灵机是计算机科学里的基本概念。
其次，图灵机还能让我们能够更清楚地理解算法究竟是什么，从而对算法这个重要概念有更深刻的理解，因为任何算法都可以看作是一个图灵机。
再来，图灵机是每一个复杂性理论的基础。通过图灵机，我们可以讨论算法的效率，复杂度之类的东西。它还帮我们定义了“可计算性”，就是说哪些问题是理论上能解决的，哪些是解决不了的。这对于我们理解计算机能做什么，不能做什么，非常重要。
图灵机还和形式语言、自动机理论这些领域紧密相关，这对于理解编程语言、编译器设计，甚至是自然语言处理都很重要。
图灵机还提供了一个框架，让我们可以比较不同的计算机模型，比如量子计算机。
最后，图灵机不仅仅是技术概念，它还有很深的历史和哲学意义，和人工智能的起源、计算的哲学问题都有关。
除此以外，因为图灵机是个抽象概念，所以学习图灵机还能锻炼我们的抽象思维和逻辑推理能力，这对于学计算机科学来说特别重要。
总的来说，图灵机是计算机科学教育的基石，它建立起了计算机科学坚实的理论基础。看到这，你应该就明白了他的重要性了。
图灵机经典概念图
遗憾的是，这个概念相对而言并不是考察重点，不能很好的出题，所以无论是老师干练的ppt里，还是让人头大的教材里，这部分都被一笔带过了。但我想很多人还是会像我一样被这玩意勾起了好奇心。所以我这篇帖子为此而生的。
图灵机
我们先来看看百科是如何解释的
百度百科
图灵机，又称图灵计算机，是一个抽象的机器。它由英国数学家艾伦・麦席森・图灵(1912―-1954年)于1936年提出的一种抽象的计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。 [2]图灵机有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个读写头在纸带上移来移去。读写头有一组内部状态，还有一些固定的程序。在每个时刻，读写头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动
维基百科
图灵机（Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
都挺抽象的对吧。我们来对他进行拆分讲解。
1.图灵机的构成：
纸带（Tape）：一个理论上无限长的纸带，被划分成许多单元格，每个单元格可以存储一个符号。
读写头（Head）：一个可以沿着纸带左右移动的读写头，用于读取、写入或擦除纸带上的符号。
状态寄存器（State Register）：一个有限的状态集合，图灵机在任何时刻都处于这些状态之一。
转移函数（Transition Function）：一个规则集合，它根据当前的状态和读写头读取的符号来确定图灵机的下一个动作，包括改变状态、在纸带上写入符号以及移动读写头的方向。
简单来说，图灵机的读写头可以在纸带上移动，还能够读取和修改单元格里的符号。而读写头移动的规则来自于转移函数，转移函数正如上面所介绍的，可以改变状态，每一个状态又是处于状态寄存器里的，状态寄存器里存储的状态一定是有限的。
2.图灵机实例
我们由浅入深的举例子。
- 我们假设状态有两个：0或1
纸带上的符号：0或1。
规则（转移函数）： - 初始时图灵机状态为0。
- 当读写头读取纸带格子为空时，如果图灵机状态为0，则读写头写入0，再将图灵机状态改变为1。如果图灵机状态为1，则读写头写入1，再将图灵机状态改变为0。最后读写头向左移动一个并读取符号
- 当读写头读取纸带上的符号为0时，图灵机的状态变为1，纸带向左移动一格，当读写头读取纸带上的符号为1时，图灵机的状态变为0，纸带向左移动一格。
我们可以设定纸带上原本如下图，读写头选中0，启动图灵机，我们就可以进行程序运算了。
第一步我们读取到了0，图灵机状态变成了1，读写头向左移动一格。
第二步我们读取到了1，图灵机状态变成了0，读写头向左移动一格。
第三步我们读取到了1，图灵机状态变成了0，读写头向左移动一格。
第四步我们读取到空，由于状态为零，故写入纸带0，状态改为1，读写头向左移动一格。
第五步我们读取到空，由于状态为零，故写入纸带1，状态改为零，读写头向左移动一格。
……
以此类推，最后我们会得到一条写着从左到右写着0110101010101…….的纸带。
很明显这个图灵机是没有运算结果的，他会一直进行下去，所以我们想让它停机得出结果的话，我们得修改一下规则（转移函数），比如说，读写头只会进行10次读取，之后便会停机。
那么最后就有结果了，从左到右0110101010。
2.这个例子来源于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
用这三个例子，我们说说明了图灵机究竟是如何工作的。相必很多写过一些算法题的读者会感到熟悉了：图灵机里的规则（转移函数）不就是程序嘛，然后改变纸带上的信息就是改变变量的值。我也是这么想的。但这也正是图灵机的意义之所在，它奠定了计算机思想的基础。
除了这点以外，图灵机还有什么伟大之处呢？
一切图灵完备的可计算问题，图灵机都能算出来
比如说，如果我们给虫子加一些条件呢？让虫子从纸条移动到平面网格；让虫子可以可以读取周围五百格的信息；不同时间虫子的读取能力有规律的不同；虫子本身还可以改变环境而不是只能听天由命；虫子具有健康、饥饿、疲倦等状态，影响着它的能力。
这些变化仍旧可以写作一个程序，输入到图灵机里，然后被图灵机算出来。因为它是图灵完备的，并没有脱离输入集合、输出集合、内部状态、固定的程序指令这四个基本点。尽管可能需要大量的计算，但如果运用到有特殊需求领域，它一定是能够发挥巨大作用的。
而且，在任何一个图灵完备的问题里，图灵机模型永远是最优解，它可以最快速地解决一切可计算问题。没有其他模型在解决可计算问题上可以超越它。
那么，什么是图灵完备？
3.图灵完备
百度百科
图灵完备是指在可计算性理论里，一系列操作数据的规则（如指令集、编程语言、细胞自动机）按照一定的顺序，可以计算出结果。 这个词源于引入图灵机概念的数学家艾伦·图灵。
虽然图灵机会受到储存能力的物理限制，图灵完全性通常指“具有无限存储能力的通用物理机器或编程语言”。
维基百科
图灵指在可计算性理论中，编程语言或任意其他的逻辑系统如具有等用于通用图灵机的计算能力。换言之，此系统可与通用图灵机互相模拟。
都讲的不是很清楚对吧，简单地定性来说，图灵完备就是可以抽象成图灵机的系统或编程语言，可以解决一切可计算问题。相反，缺乏条件而无法抽象成图灵机的，就不是图灵完备，因为他是不可计算的。很多语言，像python,java,c/c++,javascript等，就是图灵完备的，相反，Bitcoin Script就不是图灵完备的了。
通过我上面举的三个例子，我们现在应该能够很好的理解上述的图灵完备。
至此，我们对图灵机的认识基本就结束了。
思考
我们可以看到图灵机的无限潜力。想想前面的虫子，即使不断地为他添置条件使之复杂，最终仍旧是一个可以被计算的问题。那么不断地丰富，最终是否可以抽象出一个可以被计算的人呢？
这个问题值得思考。
我们想想那四个关键点，输入集合、输出集合、内部状态、固定的程序指令。要想让一个人可以被计算，那么他周围的环境，即输入输出集合就得当作是规则而非完全不可计算的，还要认为他的内部状态也十分稳定，最后他的大脑还必须一成不变。
这么一想，想必我们都已经有了答案。
但是对于人工智能来说，情况就不一样了。人工智能的输入输出都是有限的，内部状态也是一个有限的集合。它的程序指令在每个特定的版本里都是不会变化的。那么显而易见，它是可计算，可预测的。
在如今人工智能大热的情况下，我们也许确实得想想关于它的基础性问题。
思考，学习，才能更新我们的大脑，才能不让我们变得可计算，才能让我们有别于人工智能。
关于图灵机，这是我最后的感想。