图灵机是什么（图灵机的工作方法是什么）

本文目录

• 图灵机的工作方法是什么
• 图灵机在计算机发展史上主要贡献是什么
• 什么是图灵机
• 图灵机的工作原理是什么
• 图灵机是一种什么机器
• 图灵机是什么东西啊
• 图灵是什么,
• 图灵机是什么具体点
• 图灵机是什么

图灵机的工作方法是什么

组成：图灵机主要有两部分组成

第一：一条无限长的纸带，纸带分成一个个小方格，用来无限存储

第二：一个读写头，能在纸带上读、写和来回移动

工作方法：图灵机开始工作时，纸带上只有输入串，其他地方是空的。若要保存信息，则读写头可以将信息写在纸带上，若要都已经写下的信息，则读写头可以来回移动。机械不停的计算，知道产出输出为至。

图灵机在计算机发展史上主要贡献是什么

它的意义有如下几点:

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

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

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

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

扩展资料：

图灵机是中央处理器（CPU）的一般示例，该处理器控制计算机完成的所有数据操作，而规范机则使用顺序存储器来存储数据。更具体地说，它是一种能够枚举字母表中有效字符串的任意子集的机器（自动机）；这些字符串是递归枚举集的一部分。图灵机具有无限长的磁带，可以在其上执行读取和写入操作。

假设黑匣子，图灵机无法知道它最终是否会使用给定程序枚举子集的任何特定字符串。这是由于无法解决暂停问题，这对计算的理论限制具有重大意义。

Turing机器能够处理不受限制的语法，这进一步意味着它能够以无数种方式稳健地评估一阶逻辑。通过lambda演算可以证明这一点。

能够模拟任何其他图灵机的图灵机称为通用图灵机（UTM，或简称为通用机）。用类似的“通用”性质更数学导向的定义是由引进邱奇，上演算，其工作的正式理论与图灵的交织在一起计算被称为教会图灵论题。

参考资料：百度百科-图灵机

什么是图灵机

图灵机 1936年，阿兰·图灵提出了一种抽象的计算模型 —— 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作： 在纸上写上或擦除某个符号； 把注意力从纸的一个位置移动到另一个位置； 而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成： 一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。 一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。 一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。 一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。 注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程 自动机 automata 对信号序列进行逻辑处理的装置。在自动控制领域内，是指离散数字系统的动态数学模型，可定义为一种逻辑结构，一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中，分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。在语言学中则把自动机作为语言识别器，用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型，用来研究神经生理活动和思维规律，探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型，研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数，研究各种算法。现代自动机的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。 自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。自动机可按其变量集和函数的特性分类，也可按其抽象结构和联结方式分类。主要有：有限自动机和无限自动机、线性自动机和非线性自动机、确定型自动机和不确定型自动机、同步自动机和异步自动机、级联自动机和细胞自动机等。参考资料：http://www.swarmagents.com/javaclass/ca.htm

图灵机的工作原理是什么

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

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

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

扩展资料：

通用机型

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

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

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

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

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

图灵机是一种什么机器

是图灵计算机。指一个抽象的机器。

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

 它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。 

意义

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

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

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

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

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

以上内容参考 百度百科-图灵机

图灵机是什么东西啊

其实呢，图灵机的来历忒单纯。以前一个叫图灵的闲人养了只无所事事的小母鸡。图灵成天忙着跑马拉松，懒得照顾它，就装了条在鸡看来无限长分格的传送带，定时传送食物和水。而鸡闲来无聊，便走来走去，在带子上摆放物事，权作耍子。郁闷时在格子里放根树枝。兴奋了在某个格子里下个蛋。想起了还可以把蛋换成树枝，或者把树枝换成蛋。不高兴了在传送带上扔颗石头，于是传送带就卡住了。某天小母鸡不小心把一株野生大麻当鸡骨草吞了，high得不行，绕着传送带发疯： 在传送带靠左的地方放下一根树枝一个蛋：10 在传送带靠右的地方放下两根树枝：11 回到左边，把树枝拣起来，再把蛋换成树枝：1 回到右边，把两根树枝换成一根树枝两个蛋：100 回到左边，把树枝拣起来 回到右边，把最右边的蛋换成树枝：101 这下左边的树枝和蛋都没了。小母鸡意兴索然，一怒之下扔颗石头卡死机器。刚从杂货店提了袋苹果的图灵路过，目睹这一切。不由灵光一现：这不2+3=5么？原来加法还可以这么玩儿啊！以后不用为算帐发愁了。不过图灵的兴趣不在算帐，而在玩儿tic-tac-toe。问题是小母鸡智力有限。要她理解tic-tac-toe这样的东东还不如让公牛上树兔子下蛋。幸好图灵是个好琢磨的勤快人，没事喜欢读一个叫Kurt Godel的德国人的文章。而Godel崇拜一个叫David Hilbert的老乡。Hilbert在德国哥廷根讨生活时没事喜欢玄想，一不小心在世纪之交提出23个问题。居然引得此后100年来无数闲人神魂颠倒。Godel对第10个问题着了迷。研究几年后，写了篇帖子总结心得，顺便告诉大家，Hilbert也有猜错的时候。第10个问题的答案是我们不能依靠形式化方法找到所有丢番都方程的解。而推论就是大家就不用指望设立几个事实（闲人们管这叫公理），再用一套规则推出所有真理。“我们必须知道，我们必将知道”的难度比Hilbert预计的大多了。这一下彻底broke Hilbert’s heart。不过我跑题了。Godel的论文花了大量篇幅描述怎么用数字来表示自然数以外更复杂的东东（黑话叫encoding）。图灵应该看过这篇文章。他很快发现，用树枝和蛋完全可以模拟出tic-tac-toe。比如说四个蛋表示左上角画圈。三个蛋一根树枝, 0001，表示左上角画X。而且他证明了就算小母鸡吃了大力丸能用更复杂的符号在传送带上描述tic-tac-toe，也不过比她用树枝和蛋少花4log(|∑|)倍的时间而已。这里的|∑|代表一共有多少所谓的复杂符号。 于是图灵写了帖子，介绍他的鸡。后人就把这只鸡叫图灵鸡了。 而且人们惊奇地发现，虽然他们做出的机器越来越花哨，下国际象棋能让大尾巴狼卡斯帕罗夫肝肠寸断，失意江湖，也不过是一只摆放树枝和蛋时快如闪电的图灵鸡而已，和作古的正宗图灵鸡没有本质区别。我们为了纪念这个现象，就造了一专用名词，图灵等价。人们还观察到有些问题非图灵鸡不可，于是再造一词：图灵完备。现在很多老大喜欢把图灵完备和图灵等价混用。这好比说命题成立所以逆命题成立，多数时候不靠谱。不过这个话题值得单独写一帖子，以后再说吧。图灵并不满足于简单的2＋3＝5和tic-tac-toe，所以他敏锐地注意到另一个重大挑战：如果每只鸡都只能做一种计算，他得养多少鸡组装多少传送带才能算帐啊？更别说下国际象棋了。人肉计算机图灵是做化繁为简的高手。这个高难问题被他举重若轻地解决了：首先他证明了任何图灵机都可以用树枝和蛋表达。然后他养了只更聪明的鸡(图灵搞了N年的数学生理学和形态发生学，大家知道是为什么了吧？)。这只鸡吃脑白金喝农夫山泉，嘛都不干，不打鸣不下蛋，但会识别理解用树枝和蛋描述的其它图灵机，并在传送带上模拟它们的操作。用闲人们的黑话总结，就是对任意问题x, 和 , 总存在一只鸡U，使得 。这里的 是用a这串树枝加蛋的长列表示的图灵鸡。这样的鸡，一只顶一万只啊。从此，图灵不需要再养那么多鸡了，他只需用树枝和蛋摆出算帐的方法，和提供数据，这只鸡就能算出结果。想到这里，图灵只觉元气充沛，不禁仰天长啸：I do chicken right. 这只新品种的鸡从此被称为元图灵鸡(Universal Turing Machine)。Universal者，我鸡一出百鸡杀之意也。元图灵鸡具有重大意义，代表了两大计算支柱（还有一个是self-reference）：universality，和duality。Universality我们才说了。而duality是说数据和程序本是如来佛祖座前绞在一块儿的两根灯芯。比如用树枝和蛋表示的图灵鸡，你说它是程序呢，还是数据？理论界的元老Martin Davis在他的书里甚至说储存程序的计算机这一革命性的概念就是起源于这只元图灵鸡。对了，当年英国有图灵这样的先驱，造出世界上第一台通用计算机，为什么到头来计算机历史让美国人独大呢？说来也是一段让人嗟叹的故事。一言以蔽之，笼中鸡不如走地鸡，走地鸡不如野鸡。有兴趣的可以读Andy Kessler的How We Got Here。这本书语言之生动，段子之幽默，故事之曲折，史料之有趣，实在不可多得。而且免费。不能不推荐的说。当然，一只鸡是远远不够的。图灵在1952年写了一坨国际象棋程序，当时居然没有机器能跑动。很快闲人们一窝蜂扑向计算复杂性这个崭新的研究领域。4、50年前实在是烽烟四起的战国时代啊，到处是传奇英雄的传奇故事。好像随便什么领域都有震撼人心的发现。1964年，Alan Cobham和Jack Edmonds在ACM BBS上发帖，说如果一个问题能被一只图灵鸡用有限步骤解决，而解决的步数是这个问题长度的多项式，那么这个问题的复杂度就是P。P是Polynomial的缩写。可惜有些问题的算法远比P复杂，比如找出国际象棋对局的最佳策略。不过很快有人提出，有些问题虽然看似复杂，但验证这些问题的算法是否正确需要的复杂度却是P。比如判断一堆整数里面有没有几个整数的和刚好为0。验证某个可能答案太简单了：对答案里的数求和就行，花的时间最多等于这堆整数的个数。于是有达人就想：这样好办啊。如果一个问题的备选答案有N个，那我们就养它N只鸡，让每只鸡验证一个答案。如果每个答案的验证复杂度都是P，那最终的复杂度不也是P了么？可惜，得到验证结果前我们不知道哪个候选答案一定正确，也不能确定哪只鸡先得到答案，就好像不知道哪个女工先找到旺卡巧克力工厂的金券。为了和普通的图灵鸡区分，闲人们把这种兵团做战的鸡群叫做non-deterministic图灵鸡 。因为用这种图灵鸡能在多项式时间内找到答案，所以我们把这种复杂度叫NP，也就是Non-deterministic Polynomial的简写。还是很直观的吧？很明显，P是属于NP的，因为既然我们能在P内找到答案，自然能在P内验证答案。那有没有属于NP但不属于P的呢？俺就不知道了。如果我知道的话，我就证明了P=NP或P != NP，拿了Cray研究院的100万美元花红，到Bora Bora的海滩悠哉游哉地喝Pina Colada乐。 不能证明P是否等于NP没有打击闲人们的积极性。不知道是否等于总比知道不等于好吧？所以牛人们还是前赴后继地探索。于是NP-Hard就被提出来乐。NP-hard的概念也直观：我不知道你具体有多复杂，但我知道你至少和NP问题一样复杂。什么叫一样复杂呢？于是有牛人提出，反正多项式加上多项式还是多项式。所以可以判断，如果我们已知一个问题H的算法并且每一个属于NP的问题都可以在多项式时间内通过把玩H得出，那H就是NP-hard。也就是说，如果存在一个函数（或者算法）f, 使得f(H)＝所有NP问题的集合，且计算f(H)的开销是P，那H就是NP-hard的。当然，我们还是可以让一只图灵鸡来执行这个函数，所以有函数f存在被称为图灵多项式可归约（polynomial time Turing reducible）如果H同时也属于NP，那H就是NP-Complete乐。我们可以相对容易地证明，如果有一个问题，哪怕只有一个问题，既属于NP也属于P，那整个P和NP就坍塌了，P＝NP。有兴趣的老大可以自己证明一下。到了这里，关于复杂性的研究好像被堵死了。确定一个问题是否为NP-Hard，就得证明它能被多项式归约到所有NP问题。简直就是mission impossible嘛。就在这存亡之际，出身水牛城安家多伦多的库克爷爷小宇宙爆发，于1971年证明了SAT问题（也就是判断什么样的集合能让一个布尔公式为1）属于NP-Complete。一时间众生颠倒。有了SAT垫底，我们就不用去对付所有的NP问题，而只需要对付规约到SAT这一相对简单得多的问题。到目前为止，属于NP-Complete的问题没有1000也有500了吧？人们还相继发现了其它复杂类。这里罗列了几乎所有的复杂类，共有462种。

图灵是什么,

图灵是一位英国数学家,他发明了一个计算模型被成为“图灵机”,是现代计算机的理论基础,因此被誉为“计算机科学之父”,计算机科学的最高奖以他的名字命名. 另一位有关的数学家是冯诺依曼,被誉为“计算机之父”,就是他找到了实现“通用图灵机”的方法,当然需要对转移函数做文章,就是有有限的指令组装成任何转移函数,这样的话彻底奠定现代计算机的基础.

图灵机是什么具体点

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

图灵机是什么

即确定型图灵机 1936年 ， 阿兰·图灵 提出了一种抽象的 计算模型 —— 图灵机 (Turing Machine)。图灵的基本思想是用机器来樠拟人们用纸笔进行 数学 运算的过程，他把这样的过程看作下堗两种简单的动作： - 在纸上写上或擦除某个符号； 一个状态寄存器。它用来保存图灵机堓前所处的状态。图灵机的所有可能状栁的数目是有限的，并且有一个特殊的砶态，称为停机状态。 一条无限长的纸带。纸带被划分为一䠪接一个的小格子，每个格子上包含一䠪来自有限字母表的符号，字母表中有䠀个特殊的符号 \square 表示空白。纸带上的格子从左到右依栤被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。 一个读写头。该读写头可以在纸带上堦右移动，它能读出当前所指的格子上砄符号，并能改变当前格子上的符号。 - 把注意力从纸的一个位置移动到另一䠪位置； 而在每个阶段，人要决定下丠步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符堷和(b) 此人当前思维的状态。为了模拟人的蠙种运算过程，图灵构造出一台假想的栺器，该机器由以下几个部分组成： 一套控制规则。它根据当前机器所处砄状态以及当前读写头所指的格子上的砦号来确定读写头下一步的动作，并改堘状态寄存器的值，令机器进入一个新砄状态。 注意这个机器的每一部分都映有限的，但它有一个潜在的无限长的纠带，因此这种机器只是一个理想的设够。图灵认为这样的一台机器就能模拟亠类所能进行的任何计算过程。