图灵机的工作原理是什么

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

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

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

扩展资料：

通用机型

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

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

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

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

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

普适图灵机的概念。虽然其细节是复杂的，但是它背后的原则并不十分复杂。它的基本思想是把任意一台图灵机T的指令的表编码成在磁带上表示成0和1的串。然后这段磁带被当作某一台特殊的被称作普适图灵机U的输入的开始部分，接着这台机器正如T所要进行的那样，作用于输入的余下部分。普适图灵机是万有的模仿者。“磁带”的开始部分赋予该普适机器U需要用以准确模拟任何给定机器T的全部信息！

为了了解这是如何进行的，我们首先需要一种给图灵机编号的系统方式。考虑定义某个特殊的，譬如讲在前面描述的图灵机的一个指令表。我们必须按照某种准确的方案把这表编码成0和1的串。我们可借助于以前采用的“收缩”步骤来办到。因为，如果我们用数2，3，4，5和6来分别代表符号R、L、STOP、箭头（→）以及逗点，那么我们就可以用110、1110、11110、111110以及1111110的收缩把它们编码。这样，出现在该表中的这些符号实际的串可以采用分别被编码成0和10的位数0和1。由于在该图灵机的表中，在二进位计数的结尾大写的数的位置足以把大写的0和1从其他小写的阿拉伯数字中区分开来，所以我们不需要用不同的记号。这样，1101将被读成二进位数1101，而在磁带上被编码成1010010。特别是，00读作00，它可毫不含糊地被编码成0，或者作为被完全省略的符号。实际上我们可以不必对任何箭头或任何在它紧前头的符号进行编码，而依靠指令的数字顺序去标明哪些符号必须是什么。尽管在采用这个步骤时，在必要之处要提供一些额外的“哑”指令，以保证在这个顺序中没有缝隙。这样的做法具有相当好的经济性。（例如，图灵机XN+1没有告诉我们对1100要做什么的命令，这是因为这条指令在机器运行时从不发生，所以我们应该插入一条“哑”指令，譬如讲1100→00R，它可合并到表中而不改变任何东西。类似地，我们应该把101→00R插入到XN×2中去。）若没有这些“哑的”，表中后面的指令的编码就会被糟蹋了。因为在结尾处的符号L或R足以把一条指令和另一条隔开，所以我们在每一指令中实际不需要逗号。因此，我们采用下面的编码：

0表示0或0，10表示1或1，110表示R，1110表示L，11110表示stop。

作为一个例子，让我们为图灵机XN+1编码（插入指令1100→00R）。在去掉箭头和在它们紧前面的位数以及逗号之后，我们得到

00R 11R 00R 101R 110L 101R 01STOP

1000L 1011L 1001L1100R101R00R1111R

111R 1110R

为了和早先说的相一致，我们可以去掉每一个00，并把每一个01简单地用1来取代，这样得到

R11RR101R110L101R1STOP1000L1011L1

001L1100R101RR1111R111R1110R

如下是在磁带上的相应的码：

11010101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100110

我们总是可以把开始的110（以及它之前的无限的空白磁带）删去。由于它表示00R，这代表开头的指令00→00R。而我已隐含地把它当作所有图灵机共有的。这样仪器可从磁带记号左边任意远的地方向右跑到第一个记号为止。而且，由于所有图灵机都应该把它们的描述用最后的110结束（因为它们所有都用R、L或STOP来结束），所以我们也可把它（以及假想跟在后面的0的无限序列）删去。这可以算作两个小节约。所得到的二进位数是该图灵机的号码，它在XN+1的情况下为：

101011011010010110101001110100101101011110100001110100101011101000101110101000110100101101101010101011010101101010100。

这一特殊的数在标准十进位记号下为

450813704461563958982113775643437908。

我们有时不严格地把号码为n的图灵机称为第n台图灵机，并用Tn来表示。这样，XN+1是第450813704461563958982113775643437908台图灵机！

我们必须顺着这图灵机的“表”走这么远，才找到一台甚至只进行如此平凡的（在扩展二进位记号上）对自然数加一的运算，这真使人印象深刻！（尽管在我的编码中还可以有很少的改善余地，但我认为自己进行得相当有效率。）实际存在某些更低号码的有趣的图灵机。例如，UN+1的二进位号码为

101011010111101010

它只是十进位制的177642！这样，只不过是把一个附加的1加到序列1的尾巴上的特别平凡的图灵机UN+1是第177642台图灵机。为了好奇的原因，我们可以注意在任一种进位制中“乘二”是在图灵机表中这两个号码之间的某处。我们找到XN×2的号码为10389728107，而UN×2的号码为1492923420919872026917547669。

人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数根本不是可工作的图灵机的号码。现在我们根据这种编号把最先的十三台图灵机列出来：

T0：00→00R，01→00R，

T1：00→00R，01→00L，

T2：00→00R，01→01R，

T3：00→00R，01→00STOP，

T4：00→00R，01→10R，

T5：00→00R，01→01L，

T6：00→00R，01→00R，10→00R，

T7：00→00R，01→？？？，

T8：00→00R，01→100R，

T9：00→00R，01→10L，

T10：00→00R，01→11R，

T11：00→00R，01→01STOP，

T12：00→00R，01→00R，10→00R。

其中，T0简单地就是向右移动并且抹去它所遇到的每一件东西，永不停止并永不往回退。机器T1最终得到同样的效应。但它是以更笨拙的方法，在它抹去磁带上的每个记号后再往后跳回。机器T2也和机器T0一样无限地向右移动，但是它更有礼貌，简单地让磁带上的每一件东西原封不动。由于它们中没有一台会停下，所以没有一台可以合格地被称为图灵机。T3是第一台可敬的机器。它的确是在改变第一个（最左边）的1为0后便谦虚地停止。

T4遭遇了严重的问题。它在磁带上找到第一个1后就进入了一个没有列表的内态，所以它没有下一步要做什么的指令。T8、T9和T10遇到同样的问题。T7的困难甚至更基本。把它编码的0和1的串涉及到五个接续的1的序列：110111110。对于这种序列不存在任何解释，所以只要它在磁带上发现第一个1就被绊住。（我把T7或其他任何机器Tn，它的n的二进位展开包含多于四个1的序列称为不是正确指明的。）机器T5、T6和T12遭遇到和T0、T1和T2类似的问题。它们简单地、无限地、永远不停地跑下去。所有T0、T1、T2、T4、T5、T6、T7、78、T9、T10和T12都是伪品！只有T3和T11是可工作的，但不是非常有趣的图灵机。T11甚至比T3更谦虚，它在第一次遇到1时就停止，并且没有改变任何东西！

我们应该注意到，在表中还有一个多余。由于T6和T12从未进入内态1，机器T12和T6等同，并在行为上和T0等同。我们既不必为这个多余，也不必为表中的图灵机伪品而烦恼。人们的确可以改善编码以摆脱许多伪品和大大减少重复。所有这些都是以使我们可怜的普适图灵机变得更复杂作为代价。普适图灵机必须把所读到的号码n解码并假装成图灵机Tn。如果我们可以把所有伪品（或者多余量）取走，这还是值得做的。但是，我们很快就会看到，这是不可能的！这样，我们就不触动我们的编码好了。

例如，可方便地把具有

…0001101110010000…

接续记号的磁带解释成某个数字的二进位表示。我们记得0在两端会无限地继续下去，但是只有有限个1。我还假定1的数目为非零（也就是说至少有一个1）。我们可以选择去读在第一个和最后一个1（包括在内）之中的有限的符号串，在上述的情况是为一自然数的二进位写法

110111001，

它在十进位表示中为441。然而，这一过程只能给我们奇数（其二进位表示以1结尾的数）。而我们要能表示所有的自然数。这样，我们采取移走最后的1的简单方案（这个1仅仅被当作表示这一程序的终止记号），而把余下来的当成二进位数来读5。因此，对于上述的例子，我们有二进位数

11011100，

它是十进位的220。这个步骤具有零也用磁带上的记号代表的好处，也就是

…0000001000000…

我们考虑图灵机Tn对我们从右边提供给它的磁带上（有限的）0和1的串的作用。根据上面给出的方案，可方便地把这串也考虑作某一个数，譬如m的二进位代表。我们假定，机器Tn在进行了一系列的步骤后最终到达停止（即到达STOP）。现在机器在左边产生的二进位数串是该计算的答案。让我们也以同样方式把这当作，譬如是p的二进位代表来读。我们把表达当第n台图灵机作用到m上时产生p的关系写成：

Tn(m)=p。

现在，以稍微不同的方式看这一关系。我们把它认为是一种应用于一对数n和m以得到数p的一个特别运算。（这样，若给定两个数n和m，视第n台图灵机对m作用的结果而得出p。）这一特别运算是一个完全算法的步骤。所以它可由一台特殊的图灵机U来执行。也就是说，U作用到一对(n，m)上产生p。由于机器U必须作用于n和m两者以产生单独结果p，我们需要某种把一对(n，m)编码到一条磁带上的方法。为此，我们可假定n以通常二进位记号写出并紧接着以序列111110终结。（我们记得，任一台正确指明的图灵机的二进位数都是仅仅由0，10，110，1110和11110组成的序列，因此它不包含比四个1更多的序列。这样，如果Tn是正确指明的机器，则111110的发生的确表明数n的描述已终结。）按照我们上面的规定，跟着它的每一件东西简单地是代表m的磁带（也就是，紧跟二进位数m的是1000…）。这样，这第二个部分简单地就是Tn假设要作用的磁带。

作为一个例子，如果我们取n=11和m=6当作U要作用的磁带，其记号序列为

…000101111111011010000…

这是由以下组成的：

…0000（开始的空白带）

1011（11的二进位表示）

111110（终结n）

110…（6的二进位表示）

10000…（余下的磁带）。

在Tn作用到m上的运算的每一接续的步骤，图灵机U要做的是去考察n的表达式中的接续数位的结构，以使得在m的数位（也就是Tn的磁带）上可进行适当的代换。在原则上（虽然在实践中肯定很繁琐）不难看到人们实际如何建造这样的一台机器。它本身的指令表会简单地提供一种，在每一阶段读到被编码到数n中的“表”中，应用到m给出的磁带的位数时，合适元素的手段。肯定在m和n的数位之间要有许多前前后后的进退，其过程会极为缓慢。尽管如此，一定能提供出这台机器的指令表，而我们把它称为普适图灵机。把该机器对一对数n和m的作用表为U(n,m)，我们得到：

U(n,m)=Tn(m)。

这儿Tn是一台正确指明的图灵机6。当首先为U提供数n时，它准确地摸拟第n台图灵机！

因为U为一台图灵机，它自身也必须有一号码；也就是说，我们有

U=Tu

此处号码u待定。u究竟是多少呢？事实上我们可以准确地给出u=7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613632359365644443458382226883278767626556144692814117715017842551707554085657689753346356942478488597046934725739988582283827795294683460521061169835945938791885546326440925525505820555989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234151056980262734686429921838172157333482823073453713421475059740345184372359593090640024321077342178851492760797597634415123079586396354492269159479654614711345700145048167337562172573464522731054482980784965126988788964569760906634204477989021914437932830019493570963921703904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498

算法和程序的区别是：

(1) 两者定义不同。算法是对特定问题求解步骤的描述，它是有限序列指令。而程序是实现预期目的而进行 *** 作的一系列语句和指令。

说通俗一些算法是解决一个问题的思路，程序，是解决这些问题所具体好写的代码。算法没有语言界限。他只是一个思路。为实现相同的一个算法，用不同语言编写的程序会不一样。

(2)两者的书写规定不同。程序必须用规定的程序设计语言来写，而算法很随意。算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些逻辑判断。

简单算法举例 例：求 12345

步骤 1 ：先求 12 ，得到结果 2 。

步骤 2 ：将步骤 1 得到的乘积 2 再乘以 3 ，得到结果 6 。

步骤 3 ：将步骤 2 得到的乘积 6 再乘以 4 ，得到结果 24 。

步骤 4 ：将步骤 3 得到的乘积 24 再乘以 5 ，得到最后结果 120 。

算法与程序的联系 ：

算法和程序都是指令的有限序列 ，但是程序是算法，而算法不一定是 程序。程序 = 数据结构 + 算法。算法的主要目的在于为人们提供阅读了解所执行的工作流程与步骤。数据结构与算法要通过程序的实现，才能由计算机系统来执行。可以这样理解，数据结构和算法形成了可执行的程序。

程序

扩展资料：

（1）算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，

1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

（2）计算机程序是一组计算机能识别和执行的指令，运行于电子计算机上，满足人们某种需求的信息化工具。

它以某些程序设计语言编写，运行于某种目标结构体系上。打个比方，程序就如同以英语（程序设计语言）写作的文章，要让一个懂得英语的人（编译器）同时也会阅读这篇文章的人（结构体系）来阅读、理解、标记这篇文章。

一般的，以英语文本为基础的计算机程序要经过编译、链接而成为人难以解读，但可轻易被计算机所解读的数字格式，然后放入运行。

参考资料：

百度百科-程序

以上就是关于图灵机的工作原理是什么全部的内容，包括:图灵机的工作原理是什么、图灵机的工作原理、算法与程序的区别与联系等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！