图灵机算法

❶ 用图灵机描述计算机复杂度，其含义是图灵机算法的复杂度还是判断图灵机的算法的复杂度

图灵机程序的复杂度是由外部的输入和输出来决定图灵机内部的算法需要的时间和空间的复杂度。图灵机的时间复杂性T(n)是它处理所有长度为n的输入所需要的最大计算步数。如果对于某个长度为n的输入，图灵机不停机，则T(n)对这个值无定义。图灵机的空间复杂性S（n）是它处理所有长度为n的输入时，在k带上所使用过的方格数的总和。如果某个读写头无限的向右移动而不停机，s(n)也无定义。

❷ 什么是图灵机和图灵测试

阿兰·麦席森·图灵（Alan Mathison Turing，1912.6.23—1954.6.7），英国数学家、逻辑学家，被称为人工智能之父。 1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的着名密码系统Enigma，帮助盟军取得了二战的胜利。 阿兰·麦席森·图灵，1912年生于英国伦敦，1954年死于英国的曼彻斯特，他是计算机逻辑的奠基者，许多人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的有限状态自动机也就是图灵机的概念，对于人工智能，它提出了重要的衡量标准“图灵测试”，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有区别了。他杰出的贡献使他成为计算机界的第一人，现在人们为了纪念这位伟大的科学家将计算机界的最高奖定名为“图灵奖”。上中学时，他在科学方面的才能就已经显示出来，这种才能仅仅限于非文科的学科上，他的导师希望这位聪明的孩子也能够在历史和文学上有所成就，但是都没有太大的建树。少年图灵感兴趣的是数学等学科。在加拿大他开始了他的职业数学生涯，在大学期间这位学生似乎对前人现成的理论并不感兴趣，什么东西都要自己来一次。大学毕业后，他前往美国普林斯顿大学也正是在那里，他制造出了以后称之为图灵机的东西。图灵机被公认为现代计算机的原型，这台机器可以读入一系列的零和一，这些数字代表了解决某一问题所需要的步骤，按这个步骤走下去，就可以解决某一特定的问题。这种观念在当时是具有革命性意义的，因为即使在50年代的时候，大部分的计算机还只能解决某一特定问题，不是通用的，而图灵机从理论上却是通用机。在图灵看来，这台机器只用保留一些最简单的指令，一个复杂的工作只用把它分解为这几个最简单的操作就可以实现了，在当时他能够具有这样的思想确实是很了不起的。他相信有一个算法可以解决大部分问题，而困难的部分则是如何确定最简单的指令集，怎么样的指令集才是最少的，而且又能顶用，还有一个难点是如何将复杂问题分解为这些指令的问题。 1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为“论数字计算在决断难题中的应用”。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出着名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。“图灵机”与“冯·诺伊曼机”齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。

❸ 图灵机的工作原理

普适图灵机的概念。虽然其细节是复杂的，但是它背后的原则并不十分复杂。它的基本思想是把任意一台图灵机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来取代，这样得到



001L1100R101RR1111R111R1110R

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



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

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

。

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

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

❹ 什么是图灵机

图灵机

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

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

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

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

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

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

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

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

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

自动机
automata

对信号序列进行逻辑处理的装置。在自动控制领域内，是指离散数字系统的动态数学模型，可定义为一种逻辑结构，一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中，分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。在语言学中则把自动机作为语言识别器，用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型，用来研究神经生理活动和思维规律，探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型，研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数，研究各种算法。现代自动机的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
自动机与一般机器的重要区别在于自动机具有固定的内在状态，即具有记忆能力和识别判断能力或决策能力，这正是现代信息处理系统的共同特点。因此，自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。自动机可按其变量集和函数的特性分类，也可按其抽象结构和联结方式分类。主要有：有限自动机和无限自动机、线性自动机和非线性自动机、确定型自动机和不确定型自动机、同步自动机和异步自动机、级联自动机和细胞自动机等。
参考资料：http://www.swarmagents.com/javaclass/ca.htm

❺ 图灵机是什么东西啊

其实呢，图灵机的来历忒单纯。以前一个叫图灵的闲人养了只无所事事的小母鸡。图灵成天忙着跑马拉松，懒得照顾它，就装了条在鸡看来无限长分格的传送带，定时传送食物和水。而鸡闲来无聊，便走来走去，在带子上摆放物事，权作耍子。郁闷时在格子里放根树枝。兴奋了在某个格子里下个蛋。想起了还可以把蛋换成树枝，或者把树枝换成蛋。不高兴了在传送带上扔颗石头，于是传送带就卡住了。某天小母鸡不小心把一株野生大麻当鸡骨草吞了，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，和ality。Universality我们才说了。而ality是说数据和程序本是如来佛祖座前绞在一块儿的两根灯芯。比如用树枝和蛋表示的图灵鸡，你说它是程序呢，还是数据？理论界的元老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 recible）如果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种。

❻ 人工智能通识-科普-图灵机之可计算性

所有数学问题都可以用计算机来解决吗？

如 上一篇繁忙的海狸Busy beaver 中所展示的，海狸是否会陷入无法停机的无限循环？这个看似简单的数学问题就无法完全用计算机来彻底解决，或者说它是不可计算的。

可计算性是指某个数学问题是否可以用计算机 在有限步骤内彻底解决 。

首先必须是数学问题，而不能是 给我做个汉堡包 这种需要真实的实体变化的问题。

其次必须是有限步骤，如果这个问题的算法远远超过计算机目前可能拥有的计算能力，那么也应该视为不可计算的。

研究问题的可计算性质可以避免浪费时间在无底的坑里面做无意挣扎。

可计算性是针对问题而言的，问题又主要是以下两类：

另外还有 搜索问题Search Problem (在对象Y中是否能够找到符合要求的结构x)和 最优化问题Optimization Problem (多个解决方案中哪一个更优）。

图灵机是一种抽象的计算模型，理论上可以实现无限多种算法，类似的计算模型（功能模型Functional models）还有以下几个，他们都被认为是 图灵等价或图灵完整Turing completeness 的：

如上所示，递归理论起源于20世纪30年代，由库尔特·哥德尔KurtGödel，阿隆佐·邱奇Alonzo Church，罗莎·培特RózsaPéter，阿兰·图灵Alan Turing，斯蒂芬·克莱尼Stephen Kleene和埃米尔·珀斯特Emil Post等人提出。

早在1936年就邱奇和图灵就受到哥德尔的不完备性定理的启发，算法程序不可能正确的判断任意数学问题的真假。后来这个理论就被称为Church-Turing论文，定义了可计算概念的含义：可由算法计算的函数都是可计算函数。

可计算性的提出，也意味着科学家们对不可计算问题的认可，证明了数学中确实存在无法有效解决的问题。

此外还有描述可计算程度的相对可计算性Relative computability 和图灵度Turing degrees。

END

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

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

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

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

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

(7)图灵机算法扩展阅读

图灵机的意义：

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

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

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

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

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

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

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

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

它的意义有如下几点:

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

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

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

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

图灵机简介：

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

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

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

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

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

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

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

(9)图灵机算法扩展阅读：

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

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

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

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