什么是图灵机和通用计算机？图灵在计算机科学领域对人类的重大贡献有哪些

本文目录

• 什么是图灵机和通用计算机
• 图灵在计算机科学领域对人类的重大贡献有哪些
• 图灵在计算机发展史上的主要贡献有哪些
• 在图灵计算模型里,字母表里的符号多少应该怎么考虑
• 图灵机的通用机型

什么是图灵机和通用计算机

图灵机，又称图灵计算机，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。对于任意一个图灵机，因为它的描述是有限的，因此总可以用某种方式将其编码为字符串。，用 《M》 表示图灵机 M 的编码。

通用计算机是指各行业、各种工作环境都能使用的计算机。通用计算机适应性很强，应用面很广，但其运行效率、速度和经济性依据不同的应用对象会受到不同程度的影响。通用计算机不但能办公，还能做图形设计、制作网页动画、上网查询资料等。

扩展资料：

图灵提出图灵机的模型的意义：

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

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

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

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

参考资料来源：百度百科-通用计算机

图灵在计算机科学领域对人类的重大贡献有哪些

1936年11月30日出版的《伦敦数学学会会刊》，有一篇标题看来平平无奇的文章︰〈论可计算数及其在判定问题上的一个应用〉，作者是图灵。2012年，图灵诞生100周年，学界将该年订为「图灵年」，举办活动以纪念其重大贡献。2014年电影《模仿游戏》也讲述了图灵于二战时协助破解德军密码的故事（虽然忽略了波兰数学家的贡献），相信不少人对图灵的名字、贡献及其因同性恋倾向被迫害的经历略有所闻。图灵的众多贡献当中，最为重要的正是1936年这份论文，因为在文中他首次提出「图灵机」这个概念——文中他称为a-机器，a代表「自动」（automatic）——为现代计算机、计算机科学及计算理论奠下数学基础。当然，除图灵以外，他之前及之后均有不少人对计算机发展贡献良多。不过在这篇文章，让我们先看一看他的「图灵机」为何如此重要。数学基础一切源自一个貌似非常奇特、与计算机毫不相干的问题︰我们如何确定数学知识可靠？19世纪，数学发展越来越抽象，因此亦出现了各种公理系统——公理是指被视作「不证自明」的命题，数学家以公理为基础，再用逻辑推论出不同数学定理。但到了20世纪初，有批数学家（以及关心数学的哲学家）开始担心数学知识不够稳固，他们想确保由特定公理出发时，不会推论出现矛盾——假如有矛盾的话，数学就完了。他们不是杞人忧天，当时集合论中出现了数个悖论（指一种导致矛盾的命题），或许会导致数学出现矛盾。幸运的话，有些悖论可以透过引入新概念去解决，例如自数学界出现「极限」的严格定义后，甚少人会认为「阿基利斯永远无法追上乌龟」的芝诺悖论是个问题。那个时候这批数学家大概分成三派，其中一派是数学家主导的「形式主义」。简略来说，形式主义者希望藉由把数学还原成纯粹符号的形式系统，再用（有限制的）数学去证明这个系统不会出现「0=1」之类的矛盾句，从而确保数学不会产生矛盾。罗素及怀海德三大册《数学原理》，则是从逻辑主义出发，尝试以逻辑公理推导出整个数学系统——他们想的是，既然逻辑不可能自相矛盾，只要证明数学是由逻辑延伸出来，就可以确保数学一致。两人终告失败（原因并非本文重点），不过书中改良自弗雷格（Gottlob Frege）的逻辑系统，促进了数理逻辑发展。其后逻辑学家整理出一套现称为「一阶逻辑」的系统，包含若干逻辑公理和推导规则，由此出发可以推导出不少已知的逻辑定理，是个很好用的系统。判定问题回到希尔伯特，他想完全将数学化约成一个仅有符号的形式系统（这方面罗素及怀海德贡献了不少），只要按照规则，完全不懂数学、不知道符号意义的人也可以推演出「数学定理」，这样就可以撇除人为错误（例如受直觉误导）。他又希望找到一套清晰的判定程序，去确认如何判断一个逻辑公式是否属于逻辑系统的定理，假如成功，下一个目标自然是判断数学命题是否数学定理——这样数学家就不用再苦苦思索那些悬而未决的数学猜想，只要一起运行这个「判定程序」，就可以获得答案，简单直接。不过，希尔伯特于1928年提出的这个「判定问题」，在1935至1936年期间，分别由数学家邱奇及图灵先后得出答案︰不可能。要解决判定问题，首先需要厘清一个概念︰何谓「清晰的判定程序」？当然，有一些条件非常明显，例如程序必须是有限的——仅包含有限条规则、能够在有限时间完成。程序当中的规则也必须极之简单，以符合希尔伯特的要求。举个例，假如我要教一位小学生判定一个数字以否质数，可以利用他懂得「整数」、「除数」、「余数」和「比较大小」等概念，去让他按照程序执行，然后他就会发现7是质数、8不是质数、9不是质数…但希尔伯特所要求的还要更少——执行规则的人只能够辨认符号（不会把不同的符号混淆）、抄写符号、按照规则把符号串转换等，甚至不懂「加减乘除」等基本数学运算，也不会知道数学符号的意思。图灵机终于回到图灵的论文，在〈论可计算数〉中他设想以下一部机器，包含以下部份︰·一条纸带，这条纸带分成一格一格的（好吧听起来的确有点像厕所卫生纸），每格可以印一个符号。第一格的编号为0，然后是1、2、3…没有尽头，以 表示空格。·可以在纸带上左右移动的读写头，它每次能够读取所处位置那一格的内容（同一时间只可读取一格），亦可以改变其内容——改写其他符号或变成空格。·会存在机器目前状态（state）的状态缓存器，每部机器的可能状态数目有限，其中一个称为「开始状态」，就是机器一开始时所处的状态。·储存所有规则的指令集，机器会根据其目前状态以及读写头当时读取的方格内容来执行指令，进行下一步动作。上述4个部份当中，决定机器如何运作的是指令集及状态。为方便说明，以下机器的状态以颜色表示，而符号只有0、1及（空格）。图灵把指令限制在这个形式︰·当处于A状态并读取到符号X时，写入符号Y，移动读写头，并转至B状态。以下是一些例子︰·当处于红色状态并读取到符号0时，写入符号1，读写头左移一格，并转至蓝色状态。·当处于黄色状态并读取到符号1时，写入符号1（即维持原状），读写头留在原处，并维持在红色状态。·当处于蓝色状态并读取到符号0时，清除符号（变成空格），读写头右移一格，并转至黄色状态。如果没有适用的指令时，这部设想中的机器——后世称为图灵机——就会停止运作。一个图灵机模型不同图灵机分别，在于它们拥有不同的可能状态以及指令集——事实上，我们只需要看一部图灵机的指令集，就知道它可以有甚么状态，因此可以说，图灵机的指令集（以及一开始时纸带上的内容）决定了它如何运作。这些看似非常简陋的图灵机其实可以做非常多事情，图灵在论文中举了两个图灵机作例子︰一个可以在纸带上不断印出「01010101….」，另一个可以印出「001011011101111...」。事实上，我们也能设计出会进行加法、减法、乘法、除法、比较两个数字大小…的图灵机（在图灵机中，数字可用符号「1」的数量来表示，例如用「111」代表3、「1111111」代表7，数字与数字之间则用符号「0」去分隔）。通用图灵机图灵的〈论可计算数〉没有在此打住，正如上文所述，一部图灵机的指令集可以抽述了它如何运作，因此图灵就想到把图灵机（的指令集）编码，换言之，用不同的数字就可以表述不同的图灵机——就这样，每个图灵机都获得一个标准编号。下一步，图灵构造了一部特别的图灵机，称为「通用图灵机」。通用图灵机可以「扮演」不同的图灵机——只要输入某部图灵机M的标准编号，它就可以像M一样印出相同的符号序列。如果上面的句子太过抽象，不妨换个（灵异一点的）说法︰有了通用图灵机以后，理论上我们不再需要制造其他图灵机——因为其他图灵机都可以由「硬件」变成「软件」，「附上」通用图灵机来运作。对，那就是为何我们打开手机、计算机上的计算数件，便能够使用计算器的功能——现代计算机某程度上是一部通用图灵机（当然，计算机没有无限长的纸带）。通用图灵机成为现代计算机的理论模型，图灵这篇论文也奠定了计算机科学、可计算性理论等学科的基础。当然，由纸上理论代为现实，中间还有一大段历史发展，图灵亦有参与，在此先行略过。（停机问题也是〈论可计算〉的重要结果，篇幅所限同样略过。）邱奇—图灵论题在图灵之前，数学家——特别是关心数理逻辑的数学家——已经在思考如何严格定义「机械程序」或者「算法」，因为缺乏这个定义的话，界定「形式系统」时会出现一个问题︰怎样的符号变换规则可以接受？哥德尔（Kurt Gdel）在1931年证明其著名的不完备定理时，引入了（原始）递归函数的概念，以便从数学角度讨论形式系统，其后他跟英年早逝的埃尔布朗（Jacques Herbrand）将之发展成广义递归函数。但要直到图灵的论文面世后，哥德尔才认为人们能「精确及毫无疑问充足」地定义形式系统。文首提到比图灵稍早解决判定问题的邱奇，在他1936年的论文中使用了λ演算（λ-calculus）去地义何谓「λ可计算函数」。而对于任何（以自然数为定义域的）函数f(x)，如果存在一部可以顺序印出f(0), f(1), f(2)…的图灵机，那么这个函数就称为「图灵可计算函数」。邱奇和图灵证明了这三种函数——广义递归函数、λ可计算函数及图灵可计算函数——等价，换言之，虽然它们有非常不同的定义，但实际上还是一样。〈论可计算数〉发表以后，也有各种计算模型出现，但没有一个能够超越图灵机——它们所定义的函数，都是可以用图灵机（或λ演算、广义递归函数）去定义。邱奇及图灵认为，任何可以计算的函数，都是λ可计算／图灵可计算函数，这称为「邱奇—图灵论题」。他们把「可以计算的函数」这个直观概念，跟数学上有严格定义的「λ可计算／图灵可计算函数」划上等号，由于论题涉及直观概念，本身无法以数学证明。根据理论计算机科学这80年来的发展，邱奇—图灵论题几乎无人质疑︰即使计算机速度突飞猛进，能够完成各种以往无法想象的任务，现实中我们仍然未能找到一个超越图灵机的计算模型（理论上倒有一些，但不包括现时的量子计算机模型）。未来发展会怎样？不知道，可能他日人工智能的数学家、逻辑学家会发现到一个超越图灵机的计算模型——而我们无法理解？或者明天就有人发现了？（当然我认为这不可能。）没有〈论可计算数〉，我们也许还有「计算机」可用，但那些「计算机」应会截然不同，发展也慢得多。在图灵机面世80年后，我只想介绍一下这个对人类历史有深刻影响的故事。看完本文有什么想说的吗？欢迎大家留言讨论哦~

图灵在计算机发展史上的主要贡献有哪些

它的意义有如下几点:

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

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

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

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

图灵机简介：

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

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

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

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

在图灵计算模型里,字母表里的符号多少应该怎么考虑

有了纸与笔，你掌握了乘法表与进位法，实际去笔算328*975，你不需要更多的考虑，你只需要用笔在纸上机械地操作就可以，这是数学的一个特征。再如简单的一元一次方程求解，其过程可固化为五个步骤：1根据等式性质去分母，2根据乘法分配律去括号，3根据等式性质移项，4根据乘法分配律合并同类项，5系数化为1。机械的操作是都是根据形式决定的，恰当的符号让形式更清晰、易理解。

上世纪三十年代，英国数学家图灵（Alan Mathison Turing，1912.6-1954.6）在对人用笔在纸上进行计算的过程进行了仔细的考察，提出了图灵机的概念。图灵机是抽象计算机的模型，其基本原理并不复杂。

图灵机的机械部分包括：

1输入的纸带（用于输入与输出，关键词：无限长）：

可以设想为一个无限长的纸带，纸带分为一个个单元格，每个单元格上记录某个字符表中的一个字符a。

2读写头

读写头可以在纸带上左右移动，其作用是：

读取当前单元格里的字符，

擦除当前单元格里的字符

将一个字符写入当前单元格

任意时刻读写头只能在一个单元格上操作。

图中的控制器可分解为下面的逻辑部件：

3字母表

字母表包括了输入纸带单元格上可以有的字符，读写头可以写入单元格的字符，比如字符集是{“1”、“0”、“+”、“=”、“︺”}。

4状态集

图灵机在任意时刻都处于一种状态下，所有的状态构成状态集{s0、s1、s2、s3、s4、s5}，这其中包括

开始状态s0：每次运行的开始都处于此状态

停机状态s5：当图灵机进入此状态时，机器就停止运行，此状态下纸带留下的字符就为计算结果

5控制规则

读写头读取当前单元格的字符，结合当前机器的状态，可决定：

一：图灵机的新状态

二：图灵机的响应操作

擦除：擦除当前单元格的内容

写入：在当前单元格写入字符集中的一个字符

移动：向左或向右

图灵机的操作可抽象为：（（当前状态、当前读入）—》（新状态、当前写入、移动方向））。我们构造个简单的例子，这个例子是二进制个位的加法运算。设计七种状态：，

s0：初始状态

s1：被加数=1

s2：被加数=0

s3：被加数、加数=1

s4：被加数、加数不一致

s5：被加数、加数=0

S6: 停机状态

字符表为{“1”、“0”、“+”}，

擦除操作表示清空单元格内容。

可制定的规则如下：

这是个简单的例子。正是所能见到的例子都过于简单，人们反倒不理解图灵机能有什么用。你看到的实际计算机对复杂问题的处理，比如宇宙演化的模拟，天气预报等，其所应用的是同样原理，不同在于字符集、状态集、控制规则的数量级。图灵机的强大还在于可以构造通用图灵机：可以模拟其它图灵机的图灵机。一台解决特定问题的图灵机，其字符集、状态集、控制规则的数量始终是有限的，因此它所有（（当前状态、当前读入）—》（新状态、当前写入、移动方向））可以以某种方式编码，作为另一台图灵机纸带上的特定输入，同时它运行时的状态、位置也在模拟时维护在特定单元格，这样后一台图灵机通过读取上的控制可以按前一台图灵机的算法去运行。通用图灵机的概念也就是后来“可存储程序计算机”的思想。目前已知最小的通用图灵机是是字符表的字符数量为2，状态集的状态数量为3的图灵机，这比上面举例还要简单，理论上今天所有计算机的能力都不能超过这台最小的通用图灵机，差别只在于效率上。

提出图灵机思想的论文题目是“论数字计算在决断难题中的应用”，图灵所要解决的问题首先是数的可计算问题，比如圆周率(π)，是否能计算到它的任意一位。问题的直接背景是希尔伯特第十问题。1900年新世纪开始时，德国数学家希尔伯特在巴黎第二届国际数学家大会上作了《数学问题》的著名讲演，提出了数学理论中23个最困难的问题，后来这个世纪的数学进展与这23个问题解决密切相关。其中的第10个问题也称为判定性问题。原题目是：给定一个系数均为有理整数，包含任意多个未知数的丢番图方程：设计一个过程，通过有限次的计算，能够判定该方程在有理数上是否可解。问题的一般形式是：存在或不存在对任何可定义的数学问题可解的判定方法？从数的可计算去研究是个策略，数的可计算是个技术细节更单纯的问题，同时图灵证明了此问题与逻辑上可判定问题等价。

按照图灵的研究，一个数学问题的可计算等于此问题的图灵机可计算，可计算的数是无限可数，不可计算数无限且不可数，现代集合论的说法：后者的阶高于前者。希尔伯特的判定问题可归为一台通用图灵机不通过实际模拟另一台图灵机，是否可判定另一台图灵机会停机，图灵的答案是否定，这样希尔伯特的判定问题无解的，同时这也说明了图灵机的局限。在图灵完成其论文几个月前，美国数学家阿隆佐·邱奇(Alonzo Church：1903.6–1995.8)提交了论文“关于判定性问题的解释”，同样证明了判定性问题无解。邱奇所采用的方法是基于递归函数与Lambda运算来论证的。

图灵机的基本原理虽然简单，背后涉及的问题足够深刻，很多的讨论一直延续至今，并将持续下去。这些讨论可归结到三个基本的问题：人的大脑是不是一台图灵机？宇宙是不是一台图灵机？在不违背物理规律的情况下，能不能设计出超过通用图灵机的机器？

从本书的主题，图灵机是从刻画了人用笔在纸上的计算过程开始的。图灵机的读写头相当于人的眼睛与手，纸带输入是求解的问题，根据输入以及当前的状态，产生新的状态并匹配适用的规则进行写入与移动操作，这与人用笔在纸上计算时的决策与操作是一致的。图灵机的原子操作是：读取一个字符，删除字符，写入一个字符，单元格已有字符时再写入可视为修改，人类符号应用中媒介物理层面的原子操作同样如此，可能有些不同之处，如删除不一定是清除，而是划线作废，修改是作废后在旁边位置补写正确的符号，这种差异并无实质的意义。

图灵机对计算进行了一般化的抽象：广义的计算就是基于规则的符号机械操作。在此定义下，只要有确定的规则，图灵机都可以执行计算。这超出了数学里的计算概念，事实上现代计算机应用主要也不是数学上算式的求解，所操作的符号也不限于数值符号。还有哪些形式的计算？它们来自哪里？图灵的理论没有描述，今天 这被默认一种开放式的应用，这种应用足够普及且成功。结合前面图灵机延伸出的三个问题，计算虽然起源于数学，但在今天可看到的趋势是：计算概念可以不依赖数学，反过来可以认为数学依赖于计算概念，计算看作是一个独立的范式，或一种哲学。没有改变的是：这仍是对符号的操作。

图灵机的通用机型

对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。我们用 《M》 表示图灵机 M 的编码。我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M 的编码《M》 ，然后模拟 M 的运作，这样的图灵机称为通用图灵机(Universal Turing Machine）。现代电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。但要注意，它只是模拟，因为现实中的计算机的存储都是有限的，所以无法跨越有限状态机的界限。