sfx1，，xn来度量，它计算出按照程序f进行计算的步骤。小说站
www.xsz.tw例如，xy的加法程序的矩阵显示了，y步加上1的基本步骤和y步减去1的基本步骤是必要的。因此，sfx，y＝2y。由于r计算函数f可以由若干种程序进行计算，函数g称作函数f的步骤计算函数，如果有一个程序f去计算f，且对于所有的自变量x1，，xn有gx1，，xn＝sfx1，，xn。一个函数的复杂性定义为最好程序的复杂性，最好程序即进行函数计算时花费步骤最少的程序。
显然，闵斯基的寄存机是一种对于莱布尼茨的手摇计算机的直觉概括。但是，历史上另一种等价表述的机器是阿兰图林和埃米尔波斯特在1936年首先提出来的。图林机图5.2a可以执行任何有效的程序，如果该程序是正确编程的。它的构成：
a控制箱，其中置入某个有限程序；
b潜在无限的带子，带子上划分出小方格；。
c计数装置，或将每一结果打印在带子的每一方格中，沿着带子的移动或停机都处于控制箱的命令控制下。
如果图林机使用的符号限制在竖线i和空格，那么可以证明，r计算函数是图林机可计算的，反之亦然。我们必须记住，每一自然数都可以一个x条竖线的序列来表示例如3表示为iii，每一竖线都占据图林带子上的一个方格。空格用来标记空的方格或相应的数字为零。特别是，对于分开代表着数目的坚线序列，空格是必要的。因此，图林机计算一个自变量为x1，，xn的函数f，始于带子上的x1x2xn，停机于x1x2xnfx1，xn。
从逻辑学的观点来看，一台通用计算机是技术上实现了的通用图林机，如美国的约翰冯诸葛曼小组构造的计算机以及德国的康拉德朱斯**构造的计算机。它可以执行任何种类的图林程序。同样，我们可以定义一种通用的寄存机，它可以执行任何种类的寄存程序。实际上，通常设计的冯诺意曼机包括中心处理器程序控制器，记忆装置，算法单元和输人－输出装置。它以长序列方式一步一步地运行。今天的一台冯诺意曼计算机实际是一台通用化的图林机。图林机的效率可以由引进几条带子而增加，它们不必是一维的，每一条带子有一个或多个读写头，但是都要报告给单个控制箱，控制精协调着机器的所有活动图5.2b。因此，这种更有效的机器的每一计算都可以由一台普通的图林机来实施。从复杂系统探究方式来看，一台多带图林机仍然是一种程序控制的计算机，与自组织系统如神经网络有本质上的差异。
除了图林机和寄存机以外，可计算函数还可以用许多其他数学上等价程序来定义。递归函数由函数置换和重复来定义，它始于某种显然是可计算的基本函数例如相继函数nx＝x1。所有这些由图林机、寄存机、递归函数等来定义的可计算性，可以被证明是数学上等价的。显然，每一种这样的精确概念都定义了一种程序，这样的程序是直觉上有效的。
因此，阿朗索丘奇提出了他的著名公设，有效程序这个非形式的直觉概念与图林机那样的等价的精确概念是一致的。丘奇的公设当然是不可能证明的，因为这里是数学上精确的概念与非形式的直觉概念的比较。然而，几种精确的可计算性概念的数学等价在直觉上是丘奇公设的有效确证。结果是，我们可能在不涉及特定的有效程序“算法”如图林机、寄存机、递归函数等时，来谈论可计算性、有效性和计算函数。栗子小说 m.lizi.tw按照丘奇的公设，我们特别可以说，每一可计算程序算法都可以由图林机进行计算。所有的递归函数作为一种机器程序，都可以由通用计算机进行计算。
现在，我们能够定义决策和可计数的有效程序，而莱布尼茨的通用数学纲领就已经提出了这样的要求。自然数的集合特征函数f义为f＝1，如果x是一个元素，否则f＝0。因此，子集定义为有效可决定的，如果其特征函数对于一个数无论是否属于都是有效可计算的或递归的。
集合义为有效递归可计数的，如果存在有效递归程序f可相继地产生出其元素对于所有元素x1，x2，，有形式f1＝x1，f2＝x2，。容易证明，所有递归可决定的集都是递归上可计数的或递归的。但是，存在着这样的集合，它是递归上可计数的，但却不是可决定的。这是第一条线索，它意味着，莱布尼茨的基于通用可决定程序信念的乐观纲领存在着局限性。
对于自然智能和人工智能，有效可计算性范式意味着精神是由程序控制机器表示的。神经结构涉及的是符号数据结构，而精神过程也就是操作算法。历史上，ai的核心是在1956年的达特茅斯会议期间建立起来的。参加会议的约翰麦卡锡、阿兰纽厄尔、赫伯特西蒙以及来自其他不同学科领域的一流研究人员，形成了新的ai科学共同体。他们都受到图林的“机器能否思维”问题的启发，这个问题是图林在著名的计算机器和智能1950一文中提出来的。
在莱布尼茨的通用数学的传统中，人们可能会相信，人的思维可以用某种通用演算来形式化。在其现代的翻版中，人们可能会假定，人的思维可以用某种强有力的形式编程语言来表示。无论如何，形式表达式都是符号序列，是可以用自然数进行编码的。于是，对于对象的断言就相应于关于数字的函数，结论就将从某种有效的计数程序中得出，如此等等。实际上，现代计算机的机器语言就是由数字序列构成的，对于机器的每一状态和程序进行了编码。因此，计算机的操作可以描述为有效的或递归的数字程序。
如果人的思维可以用递归函数来表示，那么按照丘奇公设，它就可用图林程序来表示，而图林程序可以用图林机计算。因此，人的思维也就可以用通用计算机来加以模拟，在此意义上，对于图林提出的问题也就必定要回答“是”。人的思维是可以编码、可用递归程序来表示的，这一前提当然是可疑的。甚至数学思维的过程也可以远比递归函数更为复杂。按照丘奇的公设，递归性或图林可计算性仅仅是可计算性的一种理论限度。
下面我们希望考虑在这种限度之下和之上的复杂性程度问题。在这种限度之下，有许多涉及到一定限度的实际问题，其限度涉及到如何增加算法的速度。特别是在数学问题中，有一些种类的问题，它们的算法求解本来要比解决其他一些问题困难得多。因此，图林机有不同程度的可计算性，计算机科学中的复杂性理论使之精确化。
问题或相应的函数的复杂性分类可以由复杂性程度来标志，这给出了函数的阶，函数描述了依赖于其输入长度的算法或计算程序的计算时间或基本计算步骤的数目。输入的长度可以用十进制的数目来度量。按照计算机的机器语言，可以方便地将十进制数字编码成仅仅用0和1的二进制码，并用二进制字符来定义其长度。栗子小说 m.lizi.tw例如，3的二进制码是11，其长度为2。函数f具有线性的计算时间，如果f的计算时间不大于，其中n是输入长度，c是常数。
两个二进制数的加法显然只具有线性计算时间，例如，对于37＝10中应的二进制计算
011
111
1011
其中需要5个基本计算步骤把两个二进制数加和包括运算。我们提醒读者，加和二进制数字相加的基本步骤是00＝0，01＝1，11＝10，以及运算。可以方便地假定，两个将要相加的数具有同等长度。否则，我们简单地把较短的数加上一系列的零，例如，111和011而不是和11。一般地，如果将要相加的特定的数对的长度为n，则一个数的长度为n2，因此，我们需要不大于n2n2＝n个基本计算步骤，其中包括了运算。
函数f具有二次计算时间，如果对于所有的长度为n的输入和常数c，f的计算时间不大于2。
一个简单的二次计算时间的例子是两二数相乘。例如，对于73二21，相应的二进制计算：
111011
000
111
111
10101
按照前面的约定，我们有n＝6。基本二进制乘法的步数是n2n2＝n24。包括进运算，基本二进制相加的步数是n2n2－n2＝n24－n2。总起来，我们得到n24n24－n2＝n22－n2，它小于n22。
函数f具有多项式计算时间，如果f的计算时间不大于k，假定它是多项式pn的首项。函数f具有指数计算时间，如果f的计算时间不大于。许多实际的和理论的问题都属于这种p复杂性，所有p类函数都是可以用确定论的图林机在多项式时间中加以计算。
数学史上有一些优美的图论问题可以说明复杂性理论的基本概念。1736年，著名的数学家利昂纳德欧拉1707－1783解决了图论中的第一个问题。在东普鲁士的首都柯尼斯堡，所谓的老普里戈尔河和新普里戈尔河在普里戈尔河连接起来了。在18世纪，河上建造了7座桥，把南面s、北面n、东面e与小岛i联系起来图5.3。是否有这样一条路线，即每座桥只走一次而可以返回到最初的
欧拉把问题归结为图论。区域n，s，i，e用图的顶点来代替了，在两个区域之间的桥用相应顶点之间的边来代替图5.3b。
在图论的语言中，欧拉的问题就成为，对于每一顶点，是否存在一条线路，它仅仅通过每一条边一次而最终返回到“欧拉环”。对于任意的图形，欧拉证明：欧拉环存在，当且仅当每一顶点都具有偶数条边“欧拉条件”。对于图5.3a，它并不满足这种条件，因此在这里欧拉问题不可能有解。一般地，存在用欧拉条件来检验任意的图的算法，如果它是欧拉环。算法的输入包括所有顶点1，，n的集合v，所有边的集合e，它是所有顶点对的集合的子集。这种算法的计算时间线性地依赖于图的大小，它由定点数和边数之和来定义。
1859年，数学家威廉姆哈密顿1805－1865引入了一个颇为类似的问题，但比欧拉的问题更复杂。哈密顿考虑的是任意的图，它仅仅意味着有限的顶点的集合，通过边联系起来的一定数目的顶点对。哈密顿问题是：是否有一个通过每一顶点而不是欧拉问题中的通过每一边的封闭环“哈密顿环”。图5.3c示意了有一个哈密顿环的图，其中按照数字顺序通过每一顶点。
不过，与欧拉问题的情形不同，我们并不知道这样的条件：它精确地表明一个图中是否包含哈密顿环。我们仅仅能够定义一种算法，来检验任意的图是否包含有哈密顿环。该算法检验所有的顶点的排列，以确定它们是否形成了一个哈密顿环。由于n个顶点有n种不同的排列，该算法找到某个解的步骤不大于，其中c是常数。容易证明，n阶相应于nn阶。结果是，对于哈密顿问题，一个算法需要指数的计算时间，而欧拉问题的算法求解需要的是线性计算时间。因此，哈密顿问题实际上是计算机无法解决的，甚至对于小的数目n也如此。
大的计算时间的主要原因在于，确定论的计算机只能一步步地对于其中巨大数量的一个个情形进行检验。更方便的是运用非确定论的计算机，它允许在有限的可能数目中随机地选择计算程序，而不是以系列的方式一步步地进行。让我们再一次考虑哈密顿问题。假定一个输人图具有n个顶点u1，，un。一个非确定论的算法以非确定论的、随机的方式选择了一定的顶点顺序vi1，，vin。然后，该算法进行检验：这种顺序是否形成了一个哈密顿环。问题也就是，对于所有的数字jj＝1，，n－1，相继的顶点vij和vij1以及起初的开始顶点vin和vi1是否是由边联系起来的。这种非确定论算法的计算时间线性地依赖于图的大小。
一般地说，np意味着这样类型的函数的复杂性，它们用非确定论图林机进行计算时需要多项式时间。哈密顿问题是一个np问题的例子。另一个np问题是“旅行推销员问题”，除了种种边都有一定的数目规定以外，它与哈密顿问题非常相似。人们要解决的是：对于这一问题的哈密顿环，找出其数字的和的极小值，或更直觉地说，找出其旅行的距离的极小值。
所有的p问题由定义，都是np问题。但是，复杂性理论的关键性问题在于是否有p＝np，或换言之，由非确定论计算机以多项式时间解决的问题，是否也可以由确定论计算机以多项式时间来加以解决。
哈密顿问题和旅行推销员问题，是所谓的np完全问题的例子。这意味着，任何其他的np问题都能够以多项式时间转化成它。结果是，如果一个np完全问题实际上被证明是p问题例如能够构造以多项式时间来解决哈密顿问题的一个确定论算法，那么接着还有是否所有的np问题实际上都是p问题。否则，如果pnp，那么np完全问题就不可能用确定论算法以多项式时间来解决。
显然，复杂性理论表达了图林机或图林类型机的算法能力的程度。它在科学应用和工业应用中具有实际的后果。但是，它是否意味着人的思维的极限呢复杂性理论的基本问题例如n＝np或nnp涉及到算法的速度、计算时间、存贮能力等等的度量。另一个问题是，人们如何开始发现复杂性程度不同的算法。这是计算机科学家的创造性工作，是算法的复杂性理论中不考虑的。
另一方面，哥德尔的著名定理常常被认为限制了计算机和人的思维的数学能力。他的不完全性定理说，对于形式数论的每一协调的公理化扩展，就有一个封闭的不确定的表达式。实际上，他的定理陈述了，在整数的真陈述在其逻辑内不可能得到证明的意义上，任何合理的协调的算术逻辑都是不完整的。甚至如果我们用不可确定的表达式来扩展我们的公理化，那么也会有另一表达式在扩展的形式化中是不可确定的。哥德尔的结果表明，在莱布尼茨和希尔伯特传统中对于完整协调的算术逻辑的形式化追求，是注定要失败的。
而且，哥德尔证明，算术逻辑它可能是不完整的使用可以在其逻辑内表示的方法来使之协调，也是不可能的。在哥德尔的著名结果提出来若干年以后，金藤1909－1945证明了初等数论的协调性，他运用了所谓的eo归纳法，该方法是通常的归纳法对自然数的无限扩展。但是，金藤的扩展的证明法的协调性却还是有疑问的，有待证明。换言之，证明方法的复杂性并不低于被证系统的复杂性。因此，只可能有相对协调的证明，所用证明方法必须得到证明，所用来进行证明的方法又需要得到证明，如此等等。对于人的思维，不存在绝对的可以由形式算法提供的协调性基础。
但是，哥德尔定理对人的思维的限制是有某些基本假设条件的：我们必须把定理的证明作为人的智能的关键。公理仅仅适用于这样的精神模型：它是由其中所有知识都仔细形式化了的机器构成的。而且，哥德尔定理仅仅是对协调机的限制，而模糊性、不协调性和迷惑性都是人的决策的典型特征。如果我们在作出是否要行动的决定之前先要作出长时间的仔细的定理证明，那么我们就不可能有长期的生存。还应该考虑到，图林机具有固定的数据结构，而人的精神则是对新奇经验开放的，并能够从错误中进行学习。因此，哥德尔定理对于机器的限制，就如同对于人的大脑封锁新信息的进入一样。
1936年，丘奇和图林证明了根本没有一种算法能决定一个一阶预测逻辑的表达式是否是同义反复的真理。随之即有，为找到某种数学证明，我们必须具有某些启发性思想。
所以，ai的第一阶段19571962是受启发性编程问题支配的，这意味着在可能的分支树中自动地寻求人的问题求解，其间借助启发性来控制和评价。一个例子是纽厄尔、肖和西蒙的“逻辑理论家”1957，它首次对罗素和怀特海的数学原理中前面的38条定理提供了证明。他的启发性来自一些人在心理学测验中使用的约略估量法。
1962年，这些模拟程序被推广和扩展到所谓的“一般问题求解者”gps，它被假定为人的问题求解的启发性框架。但是gps只可能解决形式化微观世界中的一些无意义的问题。另一个启发性编程的例子是，在博奕下棋、将军中寻求取胜策略。最初的模式识别程序例如词语和符号的词汇表和句法表都是以统计方法为基础的。但是从长远的观点看，这些早期的任何程序，都没有证明一般认知模拟程序中的欣快信念。至少，它的形而上学鼓舞了麦卡锡发明编程语言lisp，它是作为一种功能的编程语言引入的，用于处理可怕的符号表，成为今天基于知识的系统的一种最强大的编程语言。
在一般方法失败以后，ai研究者们传播了一种预设的“语法信息处理”程序。ai的第二阶段1963－1967以专业程序的发展为特点。这样的专业程序，例如有求解简单代数问题的student，进行类似物体的模式识别的analogy，等等。麻省理工学院的马尔文闵斯基是这个时期的头面人物，他放弃了进行心理
...