人工智能通识-科普-图灵机1

图灵机Turing machine是英国科学家阿兰·图灵Alan Turing在1937年构想的一个计算机原型，图灵机被计算机届公认为现代计算机理论的开端，可以说，没有这个图灵机，就没有现代计算机的诞生，因此，阿兰图灵也被称之为计算机科学之父。

以上是教科书式的内容，但到底图灵机是怎么个东西，原理是怎么样的，为什么这么有意义，却很少有人真的说清。

图灵首先是个数学家，他有一个超前的想法，那就是建造一台机器，用来模拟人们用纸和笔进行运算的过程，他仔细思考之后认为，人的计算过程就是两种动作的组合：

每次除了写擦和换位置，另一个关键因素就是人的思考和决定，而这个思考又是依赖两个因素进行：

开始的配图看起来有些神秘，看上去也很复杂，但那只是艺术家的幻想罢了，真实的图灵机并不复杂。

为了模拟人做运算的过程，图灵构想的机器包含以下几个部分：

下面是一个用于翻转0和1的图灵机程序。

只要我们把指针放在纸条最右侧的非空位置上，过一会儿运行完毕之后，整个纸条上的连续的0和1就会被翻转过来，最终指针也会停留在最左侧位置上。

END

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。

在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

在某些模型中，读写头沿着固定的纸带移动。要进行的指令（q1）展示在读写头内。在这种模型中“空白”的纸带是全部为 0 的。有阴影的方格，包括读写头扫描到的空白，标记了 1,1,B 的那些方格，和读写头符号，构成了系统状态。（由 Minsky (1967) p.121 绘制）。

扩展资料：

通用机型

对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。我们用 <M>表示图灵机 M 的编码。

我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M 的编码<M>，然后模拟 M 的运作，这样的图灵机称为通用图灵机(Universal Turing Machine）。

现代电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。但要注意，它只是模拟，因为现实中的计算机的存储都是有限的，所以无法跨越有限状态机的界限。

经典图灵机及其许多变形识别语言的能力都是相同的，正因为如此，图灵机可以作为计算的一般模型。另外，通用图灵机 (可编程图灵机) 是存在的，通用图灵机可以模拟任意一个图灵机，这也是将图灵机作为现代计算机的形式模型的根本原因。

参考资料来源：百度百科—图灵机

---