什么是图灵机

发布时间：2025-09-21 08:34:33 阅读量： 0 来源： 互联网转载

图灵机又称图灵计算机指一个抽象的机器，是，英国数学家艾伦・麦席森・图灵于1936年提出的一种抽象的计算模型，即将人们使用纸笔进行数**算的过程进行抽象，由一个虚拟的机器替代人类进行数**算。

图灵机，又称图灵计算机指一个抽象的机器，是，英国数学家艾伦・麦席森・图灵(1912―-1954年)于1936年提出的一种抽象的计算模型，即将人们使用纸笔进行数**算的过程进行抽象，由一个虚拟的机器替代人类进行数**算。它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

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

我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M 的编码，然后模拟 M 的运作，这样的图灵机称为通用图灵机(Universal Turing Machine)。现代电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。但要注意，它只是模拟，因为现实中的计算机的存储都是有限的，所以无法跨越有限状态机的界限。经典图灵机及其许多变形识别语言的能力都是相同的，正因为如此，图灵机可以作为计算的一般模型。另外，通用图灵机 (可编程图灵机) 是存在的，通用图灵机可以模拟任意一个图灵机，这也是将图灵机作为现代计算机的形式模型的根本原因。

图灵机有很多变种，但可以证明这些变种的计算能力都是等价的，即它们识别同样的语言类。证明两个计算模型A和B的计算能力等价的基本思想是：用A和B相互模拟，若A可模拟B且B可模拟A，则它们的计算能力等价。注意这里我们暂时不考虑计算的效率，只考虑计算的理论“可行性”。

改变图灵机的带字母表并不会改变其计算能力。例如我们可以限制图灵机的带字母表为（0，1），这并不会改变图灵机的计算能力，因为我们可以用带字母表为（0，1）的图灵机模拟带字母表为任意有限***厂的图灵机。

延伸阅读：

图灵机的意义

图灵提出图灵机的模型并不是为了同时给出计算机的设计，它的意义有如下几点:

(1)它证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计算机应有的主要架构；

(2)图灵机模型引入了读写与算法与程序语言的概念，极大的突破了过去的计算机器的设计理念；

(3)图灵机模型理论是计算学科最核心的理论，因为计算机的极限计算能力就是通用图灵机的计算能力，很多问题可以转化到图灵机这个简单的模型来考虑。

通用图灵机向人们展示这样一个过程:程序和其输入可以先保存到存储带上，图灵机就按程序一步一步运行直到给出结果，结果也保存在存储带上。更重要的是，隐约可以看到现代计算机主要构成，尤其是冯・诺依曼理论的主要构成。

50万+团队都在用的项目协作工具一个工具满足团队所需：任务、项目、文档、IM、目标、日历、甘特图、工时、审批以及更多，让工作更简单智能化研发管理工具PingCode 是简单易用的新一代研发管理平台，让研发管理自动化、数据化、智能化，帮助企业提升研发效能

下一篇: 如何科学规划外链建设，让你的 Python 读取外链图片代码飞起来！

什么是图灵机

热门文章