图灵机简介图灵机又称图灵计算、图灵计算机，是数学家艾伦麦吉森图灵(1912 ~ 1954)提出的一种抽象计算模型，即人们抽象出用纸笔进行数学运算的过程，用一个虚拟机代替人进行数学运算。
所谓图灵机是指一种抽象机器，有一条无限长的纸带。纸带被分成小方块，每个方块有不同的颜色。有一个机头在纸带上来回移动。机头有一套内部状态和一些固定程序。每一刻，机头都要从当前纸带读入一个网格信息，然后结合自身内部状态查程序表，根据程序输出信息到纸带网格，转换自身内部状态，然后移动。
图灵机的主要功能和作用：作为研究计算一般性质的抽象工具，代替人进行数学运算，具有以下功能：
1、作为语言接受者：M接受的语言记为L(M)，是中一些字符串的集合。当这些字符串放在M的磁带上，M处于q0状态，M的头在最左边的单元时，这些字符串可以使M进入一个终止状态并停止。给定一个识别语言为L的图灵机M，一般假设当接受输入时，M停止，即没有下一个动作。但是，对于不能接受的字符串，M可能永远不会停止。图灵机接受的语言官员称为递归可枚举语言。递归集是递归可枚举集的一个子类，它总能被能停止所有输入的图灵机接受。
2、作为整数函数计算机：图灵机计算的函数称为部分递归函数。在某种意义上，部分递归函数类似于递归可枚举语言，因为计算它的图灵机可能不会停在给定的输入上。完全递归函数对应的是递归语言教育，因为它可以用总能停下来的图灵机来计算。
3、作为语言生成器：设M是一个多带图灵机，用一个带作为输出带，在这个带上面一旦写了符号就不能重写，输出带的头也不能左移。假设在输出磁带上，M写下某个单词的几个不带的字符串，用分隔符隔开，最后打印在输出磁带上的那组字符串称为M生成的语言，记为G(M)和G (m) 。如果L是图灵机生成的语言，那么L是递归可枚举集，反之亦然。
图灵机的背景任何科学思想和概念都有其背景，背景中往往有许多引人入胜的故事。计算的理论可以追溯到1900年，当时著名数学家希尔伯特在世纪之交的数学家大会上向国际数学界提出了23个著名的数学问题。第十个问题是这样的：有没有一个有限的、机械的步骤来判断丢番图方程是否有解？这里提出了有限的、机械的证明步骤的问题，用今天的话说就是一个算法。但当时人们并不知道什么是“算法”。事实上，当时数学领域的很多问题都与“算法”密切相关，于是一个科学的“算法”定义便呼之欲出。然后到了30年代，终于有两个人提出了精确定义算法的方法，一个是图灵，一个是丘奇。其中图灵提出的图灵机模型比较直观，所以很快被大家接受。
不知道大家有没有听说过图灵这个名字。也许有人知道牛顿，爱因斯坦，甚至冯诺依曼，但不知道图灵。但是，图灵的贡献绝对不亚于这些科学大师。图灵最大的贡献就是用他的图灵机模型把算法这样一个基础而深刻的概念说清楚了。正是因为有了图灵的理论基础，人们才有可能发明出20世纪以来乃至人类历史上最伟大的发明：计算机。因此，人们称图灵为：计算机理论之父。
图灵生活在二战的时代。二战期间，他为英国政府工作，成功破解了德国密码，为英国做出了突出贡献。事实上，正是因为二战，英国政府才愿意付钱给图灵制造最原始的计算机。当然，这台电脑是专门用来破解密码的，不是我们现在用的通用电脑。(有一部电影叫《密码迷情》，英文名是《enigma》，取材于当时图灵破译德国密码的故事。有兴趣可以找找看。)
图灵是个奇怪的人，只喜欢自己好好学习，不喜欢和别人交流。而且据说他也是同性恋。要知道，在当时的英国，同性恋行为是很大的违法行为。最后，就在事业如日中天的时候，他自杀了。为了纪念这位伟大的学者，计算机界设立了最高荣誉奖：ACM图灵奖。
一方面，图灵机的出现奠定了现代数字计算机的基础(你要知道冯诺依曼后来根据图灵的想法设计了第一台计算机)。另一方面，根据图灵机的基本简明概念，也可以看出可计算极限是什么。也就是说，实际上计算机的能力原则上是有限的。请注意，这里的电脑极限并不是指不能吃饭、扫地等硬件极限，只是从信息处理的角度来说，电脑还是有极限的。这就是图灵机的停机时间问题。这个问题在图灵看来更重要。他在论文中，其实是“手动”提出了图灵机模型来论证图灵停机时间。
图灵机的基本思想图灵的基本思想是用机器模拟人用纸笔进行数学运算的过程。他认为这个过程是以下两个简单的动作：
在纸上书写或擦除符号；
把你的注意力从纸的一个位置转移到另一个位置；
在每个阶段，一个人对下一步行动的决定取决于这个人当前关注的纸上某个位置的符号和这个人当前的思维状态。
为了模拟这个操作过程，图灵构建了一个假想的机器，它由以下几部分组成：
1.无限长的纸带。纸带被分成一个接一个的小格子，每个格子包含一个来自有限字母表的符号，字母表中的特殊符号表示空格。纸带上的方块从左到右编号为0，1，2。纸带的右端可以无限拉伸。
2.读写磁头。读写头可以在纸带上左右移动，可以读取当前网格上的符号，也可以改变当前网格上的符号。
3.一组控制规则表。它根据机器的当前状态和当前读写头指向的网格上的符号决定读写头的下一步动作，并改变状态寄存器的值，使机器进入新的状态。
4.状态寄存器。它用于保存图灵机的当前状态。图灵机所有可能状态的数量是有限的，有一种特殊的状态，叫做停止状态。参见关机问题。
注意，这台机器的每个部分都是有限的，但它有一个潜在的无限纸带，所以这台机器只是一个理想的设备。图灵认为，这样的机器可以模拟人类能够进行的任何计算过程。
在某些型号中，读写头沿着固定的纸带移动。要执行的指令(q1)显示在读写头中。在这个模型中，“空白”纸带全是零。阴影方块，包括读写头扫描的空白，标有1、1、B的，以及读写头符号，构成系统状态。(由明斯基(1967)绘制，第121页)。
标签：图灵状态纸带