天天观速讯丨图灵机是什么(什么是图灵机？)

本文目录一览：

1、图灵机的核心贡献是什么?2、什么是图灵模型，什么是图灵机？3、什么是图灵机理论模型4、什么是图灵机？

图灵机的核心贡献是什么?

图灵提出的著名的图灵机模型为现代计算机的桥键逻辑工作方式奠定了基础。

(资料图)

图灵机它相当于通用计算机地解释程序，这一点直接促进了后来通用计算机的设计和研制工作，在给出通用图灵机的同时。

图灵就指出，通用图灵机在计算时，其“机械性地复杂性”是有临界限度地，超过这一限度，就要靠增加程序的长度和存贮量来解决.这种思想开启了后来计算机科学中计算复杂性理论的先河。

图灵恢复在理论计算机科学方面的研究，并结合战时的工作，具体研制出新地计算机来。同年，图灵开始从事“自动计算机”的逻辑设计和具体研制工作，制出了样机。

扩展资料

图灵机的意义：

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

用类似有限状态机的原理（注意仅是类似，因为图灵机的功能远超过了有限状态机）定义了“有限次运算”，并用图灵机运算过程定义了“可行的过程”并将之重新命名为“算法”（algoritm）。这便是如今计算机体系结构以及程序算法设计最开始萌芽的地方。

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

算法是一个古老的数学概念，算法事实上是解题的系统步骤。艾伦・图灵在1936年提出的“图灵机”概念,是一般算法的典型代表。

其目的是为了解决“希尔伯特第十问题”———数学问题的一般算法步骤问题,也就是在原则上是否存在一般数学问题的解题步骤的判决问题敏渗巧。希尔伯特的规划是要把数学置于无懈可击的牢固的基础上,其中的公理和步骤法则一旦确立就不再改变。他想一劳永逸地解决数学的可靠性问题。

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

通用图灵机等于向我们展示这样一个过程：程序和其输入可以先保存到存储带上，图灵机就按程序一步一步运行直到给出结果，结果也保存在存储带上。另外，我们也可以看到现代计算机主要构成（冯.诺依曼结构），存储器，处理器，IO系统。

参考资料来源：

百度百科——图灵机

什么是图灵模型，什么是图灵机？

图灵机是图灵理论中提出的理想模型，可以实现任意复杂的计算。

英国数学家艾伦·麦席森·图灵在1936年提出了“图灵机”的理论，图灵机设想有一条无限长的纸带，纸带上方有一个个方格，每个方格可以储存一个符号，纸带可以向左或者向右运动。

图灵机可以做下面三个基本的作：

下面我们通过一个小例子来简单理解图灵机是怎样进行计算的。这个例子比较简单，我们将在空白的纸带上打印1 1 0这三个数字。

首老察先，我们向指针头指向的方框中写入数字1：

接着，我们让纸带向左移动一个方框：

这样我们就完成了一个简单的图灵机作。

我们来尝试一个稍微复杂点的作，我们尝试将1 1 0做一个异或作，即将1 1 0变成0 0 1。要图灵机完成计算，就类似于向图灵机输入以下作指令，这些指令组成了一个小程序。

我们假设图灵机的纸带现在的状态是如下图所示：

现在读取到的符号是0，按照作指令，我们应该往方框写入1并向右移动一个方框：

类似地，现在读取到的符号是1，我们重复相同的作。

上面我们使用了图灵机成功完成了异或作，理论上来讲我们也可以完成加法、减法、乘法、除法作，只不过是实现的步骤（指令）复杂些而已。下面这个网站是一个图灵机的模拟器，其实现了一些基本运算冲腔，比如：加法、减法等，有兴趣的可以自己去试试看。

Online Turing Macine Simulator

让我们尝试这样的思考历程：

“图灵机”理论通过假设模型证明了任意复杂的计算都能通过一个个简单的作完成，从而从理论上证明了「无限复杂计算」的可能性，直接给计算机的诞生提供了理论基础。散含衫

从这样的思考历程来看，图灵机的出现为计算机的诞生奠定了理论基础，这就是图灵机诞生的意义。

什么是图灵机理论模型

图灵机由一条无限长的纸带、一个搭如读写头、一套腊兄控制规则和一个状态寄存器四部分组成，在无限长的纸条上有知局启一个个方格，每个方格可以存储一个符号，纸条可以向左或者向右运动。图灵机模型可以执行三个基本作：读取指针头指向的符号；修改方框中的字符；将纸带向左或向右移动，以便修改其临近方框的值。

参考资料：《大学计算机-计算思维导论》，清华大学出版社2019

什么是图灵机？

1936年，阿兰·图灵提出了一种抽象的计算模型 ── 图灵机 (Turing Macine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

在纸上写上或擦除某个符号；

把注意力从纸的一个位置移动到另一个位置；

而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

一条无限长的纸带。慧侍贺纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。

一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。

一套控制规则。它根据当前派前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。

注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程

图灵机停机问题(Te Halting Problem)的不可判定性

图灵机停机问题: 能否给出一个判断任意一个图灵机是否停机的一般方法? 答案是NO.

这个问题实际上是问: 是否存在一台"万能的"图灵机 H, 把任意一台图灵机 M 输入给 H, 它都能判定 M 最终是否停机, 输出一个明确的 "yes" 或 "no" 的答案? 可以利用反证法来证明这样的 H 不可能存在. 假定存在一个能够判定任意一台图灵机是否停机的万能图灵机 H(M), 如果 M 最终停机, H 输出 "谈斗alt"; 如果 M 不停机, H 输出 "loop". 我们把 H 当作子程序, 构造如下程序 P:

function P(M) {

if (H(M)=="loop") return "alt";

else if (H(M)=="alt") wile(true); // loop forever

}

因为 P 本身也是一台图灵机, 可以表示为一个字符串, 所以我们可以把 P 输入给它自己, 然后问 P(P) 是否停机. 按照程序 P 的流程, 如果 P 不停机无限循环, 那么它就停机, 输出"alt"; 如果 P 停机, 那么它就无限循环, 不停机; 这样无论如何我们都将得到一个矛盾, 所以假设前提不成立, 即不存在这样的 H. 或者说, 图灵机停机问题是不可判定的(undecidable)。

以上就是小编对图灵机是什么的相关信息分享，希望能对大家有所帮助。

关键词：