图灵机 算法

问题:图灵机与算法之间有什么关系?

答:理论上一个算法就是一个确定的、对任意输入都停机的图灵机。

凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法野解决不了。

图灵机与算法的关系是?

从理论上，从根本上说，一个算法就是一个确定的、对任意输入都停机的图灵机。

凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法野解决不了。

图灵机提出TM的目的?以及TM具有什么性质?

答:（1）对有效的计算过程（即算法）进行形式化的描述，忽略模型的存储容量在内的一些节支问题，只考虑算法的基本特性。

（2）

具有有穷描述，过程必须是有离散的、可以机械执行的步骤组成。

1、具有有穷描述:有穷描述表示的是状态有穷，也就是计算问题的每个动作过程、步骤都应该是有穷可描述的。

2、过程必须是由离散的、可以机械执行的步骤组成:该性质是判定问题是否可解、可计算的关键。

问:提出TM的目的是什么?

答:对有效的计算过程（即算法）进行形式化的描述， 忽略模型的存储容量在内的一些枝节问题， 只考虑算法的基本特征．

问题:提出TM的目的在于什么?

回答:对有效的计算过程进行形式化描述，忽略模型的容量，只考虑算法的基本特征。

问题:图灵提出TM具有哪些性质?

答:（1）具有有穷描述。（2）过程必须是由离散的、可以机械执行的步骤组成。

什么是图灵完备?

在可计算理论中，当一组数据操作的规则（一组指令集，编程语言，或者元胞自动机）满足任意数据按照一定的顺序可以计算出结果，被称为图灵完备（turing complete）。

问:图灵论题是什么?

答:图灵论题:凡是可计算的函数，都可以用图灵机计算

图灵机是什么?功能是什么?

答:图灵机，又称图灵计算、图灵计算机，是由数学家阿兰·麦席森·图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。

作用及功能:替代人们进行数学运算。

问题:图灵机是一种机器么?

回答:不是，图灵机是一种计算模型       图灵机只是一个理论上的计算模型．

问题:图灵机的本质是什么?

答:图灵机本质是在进行字符串的处理，图灵机输入是一个字符串，输出也是一个字符串，如果将图灵机的有限内部状态与读写头的有限动作用字符串表示，那么每条转换规则也可以用一个字符串表示（当前状态，当前符号，动作，新状态）

问题: 图灵机的基本思想

答案:

为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成:

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

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

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

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

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

图灵机的基本思想是什么?

答:图灵机的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，图灵把这样的过程看作下列两种简单的动作:在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置；而在每个阶段，人要决定下一步的动作，依赖于此人当前所关注的纸上某个位置的符号和此人当前思维的状态。

图灵提出图灵机的意义?

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

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

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

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

图灵机   现代计算机 

图灵机的计算模型是怎样的?为什么将它称之为现代通用计算机的原始模型?

答案:“图灵机”想象使用一条无限长度的纸带子，带子上划分成许多格子。如果格里画条线，就代表“1”；空白的格子，则代表“0”。想象这个“计算机”还具有读写功能:既可以从带子上读出信息，也可以往带子上写信息。计算机仅有的运算功能是:每把纸带子向前移动一格，就把“1”变成“0”，或者把“0”变成“1”。“0”和“1”代表着在解决某个特定数学问题中的运算步骤。“图灵机”能够识别运算过程中每一步，并且能够按部就班地执行一系列的运算，直到获得最终答案。

在图灵的想象模型中，我们可以隐约看到现代计算机主要构成（其实就是冯诺依曼理论的主要构成），存储器（相当于存储带），中央处理器（控制器及其状态，并且其字母表可以仅有0和1两个符号），IO系统（相当于存储带的预先输入）。

问题:图灵机的纸带、控制器分别等同于当代计算机的什么部分?

答:图灵机的纸带等同于当代计算机的内存，控制器则等同于当代计算机的CPU。

问题:图灵机与现代计算机的不同之处是?

答:    

它只是理想的计算模型。

相同之处:程序与数据混合在一起，由控制器控制执行

不同之处:内存无限大，没有考虑输入与输出（所有信息都在子带上）

图灵机内存无限大。（因为所有信息都在子带上，而子带可以无限长,无限长的纸带）

问题:图灵机与现代计算机相比较，哪个的内存大?

答:图灵机的内存大。因为用图灵机计算问题，所有信息都是在纸带上的，因此纸带就相当于图灵机的内存，而纸带可以是无限长的，即图灵机的内存是无限大的。

问题:为什么说图灵机是现代计算机的理论模型?

答:图灵对现代计算机的贡献主要是:建立了图灵机的理论模型，发展了可计算性理论；提出了定义机器智能的图灵测试。 

冯·诺依曼的贡献主要是:确立了现代计算机的基本结构，即冯·诺依曼结构。其特点可以概括为如下几点: 

（1）使用单一的处理部件来完成计算、存储以及通信的工作； 

（2）存储单元是定长的线性组织； 

（3）存储空间的单元是直接寻址的； 

（4）使用机器语言，指令通过操作码来完成简单的操作； 

（5）对计算进行集中的顺序控制。 

现代计算机的划代原则主要是依据计算机所采用的电子器件不同来划分的，这就是人们通常所说的电子管、晶体管、集成电路、超大规模集成电路等四代。

为什么现代计算机不能超过图灵机?

答:图灵机是理论上的抽象机器，运行思路是最基本，最简单的，它的数据查找，操作等动作在理论设计时是不考虑时间的，而现代计算机则做不到。

问:图灵机与现代计算机的关系?

答:   图灵提出图灵机的模型并不是为了同时给出计算机的设计

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

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

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

图灵机与现代计算机的关系:

图灵提出图灵机的模型并不是为了同时给出计算机的设计，首先它证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计算机应有的主要架构；然后图灵机模型引入了读写与算法与程序语言的概念，极大的突破了过去的计算机器的设计理念；很重要的一点是图灵机模型理论是计算学科最核心的理论，因为计算机的极限计算能力就是通用图灵机的计算能力，很多问题可以转化到图灵机这个简单的模型来考虑。

图灵机给我们展示了程序和其输入可以先保存到存储带上，图灵机就按程序一步一步运行直到给出结果，结果也保存在存储带上。另外现代计算机主要构成（其实就是冯诺依曼理论的主要构成），存储器（相当于存储带），中央处理器（控制器及其状态，并且其字母表可以仅有0和1两个符号），IO系统（相当于存储带的预先输入。可以看出它们的关系是密切相关的，紧密联系的。

为什么现代计算机不能超过图灵机?

答:图灵机是理论上的抽象机器，运行思路是最基本，最简单的，它的数据查找，操作等动作在理论设计时是不考虑时间的，而现代计算机则做不到。

问题:图灵机作为现代计算机的理论模型，它与现代计算机相同之处和不同之处

答:

相同之处:程序与数据混合在一起，由控制器控制执行，控制器相当于CPU

不同之处:图灵机内存无限大！并且没有考虑输入与输出！（所有信息都在纸带上，纸带就是内存）。而现代计算机内存是有限的，同时考虑外围输入输出设备，访问辅存的速度快慢是决定现代计算机性能好坏的重要因素，输入输出设备有磁盘，键盘，显示器等

图灵模型

问题:什么是图灵模型?

答:“图灵模型”是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。

图灵机模型的四个要素是什么?

答:输入信息、输出信息、程序（规则）、内部状态。

问:图灵机的基本模型包括什么??

答:一个有穷控制器，一个含有无穷多个带方格的输入带，一个读头。

图灵机的基本模型是什么?

答:它有一条带作为存储装置和一个控制器，控制器带一个 读写头（又叫带头），带的两端是无穷的，被划分成无穷多个小方格，每个小方格内可以存放一个符号。控制器有穷个状态。在计算的每一步，控制器总处于某个状态，读写头扫描一个方格

问:关于图灵机的理解

答:图灵机就是指一种抽象的机器，这种机器有一条无限长的纸带，纸带分成了一个一个的小方格，而每个方格有不同的颜色。有一个机器头在纸带上不断移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。这个在概念上如此简单的机器，理论上却可以计算任何直观可计算的函数。图灵机作为计算机的理论模型，在有关计算理论和计算复杂性的研究方面得到广泛的应用。

问题:图灵机模型的意义是什么?

答:1、图灵机模型理论是计算学科最核心的理论之一。

2、图灵机模型为计算机设计指明了方向。

3、图灵机模型是算法分析和程序语言设计的基础理论。

图灵机

什么是图灵机?

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

图灵机的意义与思想内涵

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

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

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

答案:它有一条带作为存储装置和一个控制器，控制器带一个

读写头（又叫带头），带的两端是无穷的，被划分成无穷多个小方格，每个小方格内可以存放一个符号。控制器有穷个状态。在计算的每一步，控制器总处于某个状态，读写头扫描一个方格。

简述图灵机的工作过程。

答:图灵机的工作过程可以简单的描述为:读写头从纸带上读出一个方格中的信息，然后根据它内部的状态对程序进行查表（规则表Table），得出一个输出动作，确定向纸带上是写信息还是读写头向前或向后移动到下一个方格。同时，程序还会说明下一刻的内部状态转移到哪里。

问:图灵机定义的核心是什么?

答:图灵机定义的核心是转移函数δ，因为它说明了机器从一步怎样走到下一步。

问题:图灵机的纸带相当于当代计算机的什么部分?

答:图灵机的纸带等同于当代计算机的内存。

图灵机的存储带只能是纸带?

答:错

图灵机中的存储带是逻辑上的定义，不是具体的物理设备，因此存储带可以是纸带也可以是皮带或者其他的带。

问题:给出图灵机由哪4部分组成?

答:控制器，寄存器，存储带，读写头

2. 判断正误:图灵机的控制器与储存器相连。

答:  错。

图灵机有什么特点?

答:存储无穷，时间无限制。Turing机可计算只是理论上可计算，并不是现实可计算。现实可计算:研究计算复杂性。但如果Turing机不可计算 则现实更不可计算。

问题:图灵机可以制作出来吗?

回答:图灵机是一种计算机模型，并不是一类计算机的称呼，因此不可制作出来。

通用计算机

问:什么是通用计算机?

答:不受存储空间和运行时间限制，可以实现所有有效算法的计算机。

问题:通用图灵机的定义?

回答:能够实现对所有图灵机的模拟的图灵机，即能实现所有有效算法的图灵机．

应该存在一个图灵机，能够实现对所有图灵机的模拟，即存在通用图灵机，实现所有有效算法——通用TM

问题:有限状态机与通用图灵机的区别是什么?

答:第一，图灵机既能读又能写；第二，带子是无限长的（可以无限存储，结合读写头既能左移又能右移的特点，当然就可以解决判断输入的0与1个数谁多的问题），而且带子上不但可以写入数据，还可以写入实现某一具体功能的；第三， 进入拒绝和接收状态立即停机。

非确定型图灵机       和     确定型图灵机

问:什么是确定型图灵机?

答:确定型图灵机仅有一个转移函数，转移函数是从一个图灵状态到另一个图灵状态发出的指令。

问题:图灵机的通用机型是怎么样的?

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

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

问题:非确定型图灵机和确定型图灵机的不同之处?

答:非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直至最后停机为止。

问题:确定图灵机和不确定图灵机的区别是什么?

答:其区别在于是否仅有一个转移函数。转移函数是从一个图灵状态到另一个图灵状态发出的指令。

确定型图灵机仅有一个转移函数，而不确定型图灵机则有多个不同的转移函数。

问题:确定型图灵机和不确定型图灵机的区别?

回答:是否仅有一个转移函数。转移函数是从一个图灵状态到另一个图灵状态发出的指令。确定型图灵机仅有一个转移函数，而不确定型图灵机则有多个不同的转移函数。

非确定性图灵机下＂的多项式算法的例子?

假设你丢了一颗巧克力，你首先猜测，”巧克力书桌的抽屉里“，你从现在的位置（如客厅）走到书桌旁，打开抽屉，一看，有两种结果:

没有．继续猜测“可能在你爸的抽屉里”，．．．， 寻找．．． 

有． 

每一次寻找，你可能找不到，也可能找到，你不能确定． 但每一次寻找都可以在短时间内完成。

不确定性图灵机下的P算法，也大致如此．

图灵机做了哪些扩充

问:普适图灵机实现的基本思想是?

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

问题:什么是通用图灵机?

答:存在一个图灵机，能够实现对所有图灵机的模拟，即存在通用图灵机，实现所有有效算法——通用TM

问:为了扩大图灵机使用面，对图灵机做了哪些扩充?

答:1．双向无穷带TM

2．多带TM

3．不确定的TM

4．多维TM

5．其他TM

（它们与基本的TM等价）

问:图灵机的变形有哪些?

答:双向无穷带TM。

多带TM。

不确定的TM。

多维TM

其他TM

它们与基本的TM等价。 

最新发展:树状图灵机、细胞自动机、……

问题:什么是多带TM?

答:多带TM是指允许TM有多个双向无穷带，每个带上有一个相互独立的读头。

答:多带图灵机是简单图灵机的一种推广，由一个有穷控制器、一条输入带、一条输出带和k条工作带组成。每条带上有一个读写头与有穷控制器相连。每条带都被分成一个个的方格，在每个方格上可以写下一个字母，这些字母均取自一个字母表。

答:多带图灵机由一个有穷控制器、一条输入带、一条输出带和 κ条工作带组成。

    每条带上有一个读写头与有穷控制器相连。每条带都被分成一个个的方格，在每个方格上可以写下一个字母，这些字母均取自一个字母表∑。

问题:多带图灵机工作原理

回答:每条带上有一个读写头与有穷控制器相连。每条带都被分成一个个的方格，在每个方格上可以写下一个字母，这些字母均取自一个字母表∑。有穷控制器在任何时候都处在某个状态q，而q属于某个有穷状态集合 Q。在任何一个时刻，机器总是根据自己目前状态q∈Q以及它的输入带头和工作带头正在扫视κ+1个符号的情况来决定下面三个动作:①下一步应该转向Q中的哪个状态；②应该把当前扫视的κ条工作带和输出带上的符号分别改成什么符号（输入带上符号不改写）；③把这 κ+2个带头各自向左还是向右移一格（也可以不动）。一个图灵机就是从上面两个条件到三个动作的一个具体规定。

问:多带图灵机的是怎样的?

答:多带图灵机模型是计算复杂性理论中常用的一种计算模型，它是简单图灵机的一种扩展。每条带上有一个读写头与有穷控制器相连。每条带都被分成一个个的方格，在每个方格上可以写下一个字母，这些字母均取自一个字母表∑。有穷控制器在任何时候都处在某个状态q，而q属于某个有穷状态集合 Q。在任何一个时刻，机器总是根据自己目前状态q∈Q以及它的输入带头和工作带头正在扫视κ+1个符号的情况来决定下面三个动作:①下一步应该转向Q中的哪个状态；②应该把当前扫视的κ条工作带和输出带上的符号分别改成什么符号（输入带上符号不改写）；③把这 κ+2个带头各自向左还是向右移一格（也可以不动）。一个图灵机就是从上面两个条件到三个动作的一个具体规定。

问:多带图灵机比普通图灵机的计算能力强吗?

答:多带图灵机与普通图灵机是等价的。

问:多道图灵机与多带图灵机的主要区别是什么?

答:多道图灵机与多带图灵机的主要区别是:多带图灵机的每条带上都有一个相互独立的读写头，而多道图灵机只有一个读写头。

问:TM接受的语言叫做递归可枚举语言，那么可枚举递归语言的定义是?

答:如果存在图灵机M，有语言L＝L（M），并且对每一个输入串x，M都停机，则称L为递归语言．同时，存在函数可以枚举所有成员，即可以以某种顺序列举出语言，那么则L是可枚举递归的．

状态

问:图灵机是怎样进行计算的?

答:①当输入被接受时， 图灵机将停止， 没有下一个动作；

②当因未定义转换函数， 图灵机无法计算下去时， 将拒绝执行；

③如果不进入任何接受或拒绝状态， 继续执行下去， 永不停止。

④在TM接受的语言中，包含那些不能使TM停机的输入。

问:图灵机的状态集中一定会有什么状态?

答:开始状态、接受状态以及拒绝状态。

判断题:图灵机是图灵用的计算机。

答:错。

问题:图灵提出的图灵机应该具有什么性质?

答:2个性质:

1．具有有穷描述

2．过程必须是由离散的、可以机械执行的步骤组成

问:读写头只用于输入和输出，对吗

答:错

问题:图灵机的读写头只有读写数据的功能吗?

答:不是，还有可计算的功能。

问题:图灵机是我读写头有什么功能?

答:输入、输出、计算。

问:在TM接受的语言中，可以包含那些不能使TM停机的输入吗?

答:可以。

问题:对于一个输入，图灵机有哪些方式不接受它?

答:有两种方式，一种是进入拒绝状态而拒绝它，另一种是进入循环。

图灵停机问题说明了计算的什么性质?

答:有穷性

问:图灵机有哪两种停机状态?

答:一种是处于接受状态的停机，另一种是处于拒绝状态的停机。

图灵机的当前状态是哪些状态时就会停机?

答:接受状态或拒绝状态。

问:图灵机的形式化表示是什么?

答:M＝｛Q，Σ，Γ，δ，q0，qaccept，qreject｝

Q状态集合，Σ输入字符集合，Γ存储带，δ程序表，q0开始状态，qaccept接受状态，qreject拒绝状态

问:图灵机形式化的7元素｛Q，Σ，Γ，δ，q0，qaccept，qreject｝分别是什么?

答:1．Q 是状态集合；

2．Σ 是输入字母表，其中不包含特殊的空白符 □；

3．Γ 是带字母表，其中 □∈Γ且Σ∈Γ ；

4． δ:Q×「→Q×Γ×｛L，R｝是转移函数，其中L，R 表示读写头是向左移还是向右移；

5．q0∈Q是起始状态；

6． qaccept是接受状态。

7．qreject是拒绝状态，且。qreject≠qaccept

问题:图灵机为什么会接受那些不能停机的输入?

答案:图灵机接受的输入是有限长度的输入，但是有限长度的输入也有可能使得图灵机不能停机。

问题:什么时候TM停机?

回答:只有在工作过程中能进入终止状态（之一），则可以判断被接受并停机。

问题:什么是停机问题?

答:图灵机都解决不了的问题称为停机问题。

图灵机处于什么状态会停机?

答:图灵机当前状态是接受或者拒绝状态时就会停机

问题:什么是停机?

答:停机指图灵机内部达到一个结果状态、指令表上没有的状态或符号对偶，从而导致计算终止。

问题:图灵机什么时候接受停机?

答:只有在工作过程中能进入终止状态（之一），则可判断被接受并停机。

问题:图灵机的停机问题的本质是什么?

答:停机问题的本质是:给定一个图灵机 T，和一个任意语言集合 S， 是否 T 会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可列的，S 也是可停机的。

判断题:TM接受那些不能使TM停机的输入

答案:正确

问:请说说你对“在TM接受的语言中，包含那些不能使TM停机的输入。”“只要在工作过程中能进入终止状态（之一），则可以判断被接受并停机。”两句话的理解?

答:TM接受的语言包括使TM接受停机、拒绝停机、和不能使TM停机的输入语句，所以，在TM接受的语言中，包含那些不能使TM停机的输入。第二句话“则可以判断被接受并停机”中的“被接受”是指TM接受的语言，而不是指被TM接受的输入语句。

问题:为什么图灵机会不停机?

回答:因为图灵赋予图灵机两个无限:

（1）图灵机能在输入字符串上左右移动，步骤无限，时间无限；

（2）图灵机有一条无限长的带子，供读写头在上面活动，空间无限。

图灵机的一个移动将完成的三个动作是:

（1）改变有穷控制器的状态；

（2）在当前所读符号所在的带方格中印刷一个符号；

（3）将读头向右或者向左移一格。

例子:q1 1—＞q2 0 R

用例子来说明图灵机一次移动完成三个动作的过程:

首先是改变有穷控制器的状态:状态从q1—＞q2；

然后是在当前所读符号所在的带方格中印刷一个符号:当前读到的符号为＇1＇，然后在该符号的位置上印刷符号＇0＇，即＇1＇—＞＇0＇；

最后是将读头向右移一格。

问题:图灵提出的图灵机应该具有什么性质?

答:2个性质:

1．具有有穷描述

2．过程必须是由离散的、可以机械执行的步骤组成

问:图灵机上为什么要有空白字符?

答:因为图灵机的纸带是无限长的，而图灵机的带上一开始默认都是空白字符，即空白字符代表着该位置没有数据，是结束的标志。

问题:图灵机根据什么在程序中查找指令?

答:当前状态、当前字符

问题:k带TM在一次移动中完成哪几个动作? 

答:k带TM在一次移动中完成如下三个动作 :

⑴ 改变当前状态；

⑵ 各个读头在自己所注视的带方格上印刷一个希望的符号；

⑶ 各个读头向各自希望的方向移动一个带方格。

拓展

问题:图灵为什么要设计图灵机?

答案:希望有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。

问题:图灵的设想是什么?

答:设想:能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有数学问题。

问题:世界上第一台电脑ENIAC和现在常见的电脑相比较，哪个计算速率更快?

答案:现在的普通电脑计算速率比ENIAC快。

问题:第一台机械计算机是谁发明的?它的工作原理是怎么样的?

答:1642年，法国哲学家和数学家帕斯卡（Blaise Pascal）发明了世界上第一台加减法计算机。它是利用齿轮传动原理制成的机械式计算机，通过手摇方式操作运算。他称“这种算术机器所进行的工作，比动物的行为更接近人类的思维”。这一思想对以后计算机的发展产生了重大的影响。

问题:冯诺依曼是计算机之父，但为什么提到计算机，人们首先想到的是图灵?

答:冯诺依曼是计算机之父，图灵是智能计算机之父，是第一个提出智能计算机概念的人。而智能计算机较于人类来说更为重要。

问题:在计算机领域里，图灵的贡献和成就?

答:图灵是计算机之父，现代计算机设计思想的创始人，人工智能领域的开拓者。图灵提出了图灵机模型，还发表论文 “计算机和智能 ”，提出图灵测试。计算机领域的最高奖项就是以图灵的名字命名。

问:图灵对人工智能做出的贡献?

答:1949年，图灵成为曼切斯特大学（University of Manchester ）计算实

验室的副院长，致力研发运行Manchester Mark 1型号储存程序式计算机所需的软件。1950年他发表论文《计算机器与智能》（ Computing Machinery and Intelligence），为后来的人工智能科学提供了开创性的构思。提出著名的“图灵测试”，指出如果第三者无法辨别人类与人工智能机器反应的差别， 则可以论断该机器具备人工智能。

图灵机和人工智能有什么关系?

我们现在用的电脑就是图灵机，人工智能是我们希望能用电脑来实现的效果。也就让电脑能像人与人一样用最自然的方式交流。这样我们就可以用语言让人工智能机器人去完成一切以前要人才能完成的体力劳动。

问题:人工智能的研究领域有哪些?

答:该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。

问:计算机领域的最高奖是什么奖?

答:是图灵奖。

问题:什么是图灵奖?

答:图灵奖（A．M． Turing Award，又译“杜林奖”），由美国计算机协会（ACM）于1966年设立，又叫“A．M． 图灵奖”，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。由于图灵奖对获奖条件要求极高，评奖程序又是极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。

什么是图灵机的格局?

答:图灵机在计算时机器所处的状态、纸带上已被写上符号的所有格子及当前读写头的位置所构成的整体称为图灵机的格局。

问题:什么是图灵手机?

答:图灵手机是世界第一款液态金属智能手机，其机身采用独家的Liquidmorphium液态金属合金，其硬度超过钛合金和钢。除了坚固的机身外，该机表面还使用了Binnacle Ocean Master纳米涂层处理，支持IPx8防水，可浸泡在约10米的水中。

功能方面，图灵手机主打个人隐私和安全，其采用了专门的端到端受保护的通讯网络，可隔绝外界网络威胁，用户可使用图灵手机交换敏感信息，比如保密资料、银行密码等，无需担心中间被拦截。此外，该机提供了指纹识别（位于机身侧面），采用磁力吸附式充电器。

什么是图灵机器人?

答:图灵机器人平台是一个免费的API开放平台，基于自然语言处理、知识库和云计算等技术，为广大开发者、合作伙伴提供的一系列智能语义处理能力（包括语义理解、智能问答、知识库对接、生活服务技能等）的服务平台。能被运用到智能手机，智能电视，智能车载，智能移动端，网站客服等多领域，实现自然语言的智能交互。还能“一键式”接入微信公众平台，实现智能聊天机器人，智能客服机器人等服务。

问题:图灵机器人是什么?

答:图灵机器人是中文语境下智能度最高的机器人大脑，是全球领先的中文语义与认知计算平台。图灵机器人对中文语义的理解准确率高达90％，可为智能化软硬件产品提供中文语义分析、自然语言对话、深度问答等人工智能技术服务。

问:什么是图灵测试?

答:图灵测试是由现代计算机科学之父英国人阿兰·图灵1950年提出的。图灵测试会在测试人在与被测试者（一个人和一台机器）隔开的情况下，通过一些装置（如键盘）向被测试者随意提问。问过一些问题后，如果被测试者超过30％的答复不能使测试人确认出哪个是人、哪个是机器的回答，那么这台机器就通过了测试，并被认为具有人类智能。

图灵测试是什么?

答:图灵测试的方法是，被测试人，和一个是声称自己有人类智力的机器。测试时，测试人与被测试人是分开的，测试人只有通过一些装置（如键盘）向被测试人问一些问题，这些问题随便是什么问题都可以。问过一些问题后，如果测试人能够正确地分出谁是人谁是机器，那机器就没有通过图灵测试，如果测试人没有分出谁是机器谁是人，那这个机器就是有人类智能的。

什么是生命游戏模型?

答:生命游戏 （Came of Life）是J． H． Conway在20世纪60年代末设计的一种单人玩的计算机游戏。该模型属于一种元胞自动机，J·H·Conway还证明，这个元胞自动机具有通用图灵机的计算能力，与图灵机等价，也就是说给定适当的初始条件，生命游戏模型能够模拟任何一种计算机。