复杂性中的思维物质-第21章
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
加法意味着如下的结果：在计算开始时，消去机制程序由设置TM和RM到零来完成。然后，第1个数用SH设置在SM中。摇把C向右转动，就把这个数字送入了RM。换言之，在RM中把数字加到了零上。现在，第2个数字输入到SM，并通过向右转从而加到RM的内容中。两个数字的和可以在RM上读出。在向右摇动两次曲柄以后，TM显示出2。乘法仅仅是意味着反复相同数字的反复加法。乘积b·a是数字a加到自己身上b次。
莱布尼茨甚至设计了仅仅有两个数字0和1的二进制数字系统的机械计算机，二进制是他早些年发现的。他描述了一个机制，可以把十进制翻译成相应的二进制，并且反之亦然。由于现代的电子计算机只有两种状态1（电脉冲）和0（没有电脉冲），莱布尼茨的确成为计算机科学的先驱之一。
莱布尼茨的机器遇到了许多技术上的问题，因为那时的材料和技术工艺都难以满足要求。然而，他的设计是通用数学的一般研究纲领的一部分，通用数学机的意图是要通过计算程序（“算法”）并通过机械计算机来模拟人的思维。莱布尼茨提出了他的通用数学的两个基本学科。
ars iudicandi允许每一种科学问题，在编码成为数字符号以后，都可由适当的算术算法来解决。ars inveniendi允许科学家去寻找和计算出科学问题的可能解。莱布尼茨的通用数学看来已经预见了我们这个世纪著名的希尔伯特纲领，此纲领号召对数学知识进行形式化和公理化。实际上，莱布尼茨发展起来了一些程序，对语言进行形式化和编码。他深深地坚信，存在着用机械装置解决世界上所有问题的通用算法。
结果，他主张自然系统如细胞、植物、动物甚至人类都是复杂性程度不同的计算机。莱布尼茨在他的《论形而上学》（1686）中强调，活系统的因果解释的机械描述并不与在科学中有巨大启发价值的目的论观点相抵触，（22）。他在《单子论》中（18），引入了一种个体实体（单子）作为基本的自动机，它以状态（“感觉”）的（连续）系列为特征。基本的自动机构成了集合体，其程度不同的复杂性以不同的关联性为标志，并可以解释为复合的自动机。在他的《神正论》（200）中，莱布尼茨讨论了活系统中的等级结构和从属关系：
……事物的关联和秩序引起了，每种动物和每种植物的身体都包含了其他动物和其他植物，或其他活的有机体：结果是存在着从属关系，一种身体，一种实体都服务于另一种。
活系统的统一性是由其组织形式来保证的，对此莱布尼茨采纳了亚里士多德的观点，称之为“隐德来希”。但是莱布尼茨仅仅是借用了一种老的形而上学术语，以引出他自己的新概念。对于莱布尼茨来说，只有在从属关系和等级程度高低不同的意义上，一个系统才有一定程度的统一性。一个其中所有的实体之间有同等关联的集合体，就没有等级秩序，比起初级的细胞有机体，它的结构性就较差，而在植物、动物和人类中，我们都可以观察到一种不断增长的从属关系。
对于莱布尼茨来说，目的性术语具有启发性价值，尽管大自然原则上可以用机械因果性来解释。但是，把莱布尼茨说成是一位生命力论的信徒是一个基本的错误和误解。主要的区别在于，对于莱布尼茨来说，解释活系统决不需要新的原理或生命力。在一定程度的复杂性中，目的论术语仅仅是启发性地适用于描述自然系统。但是，与自然系统不同，人造的机械自动机是由人在有限步骤中构造出来的。只有无限分析才能够揭示出自然自动机的复杂性，它是与世界上的每一单个自动机（“实体”）相关联的。显然，莱布尼茨设计了一种复杂系统理论，但是仍然是处于经典力学框架中，仍然是一种可决定的通用算法的信念。
在19世纪，英国的数学家和经济学家查尔斯·巴贝奇不仅仅构造了第一台程序控制的计算机（“分析机”），而且还研究了它的经济和社会后果。他的名著《论机械和制造的经济》（On theEconomy of Machinery and Manufactures，1841）的先声是亚当·斯密的经济规律思想，这与牛顿的力学规律是并行不悖的（对照6．2节）。在《国富论》中，斯密把钢针的工业生产描述为一个算法程序，预见了亨利·福特的工业中程控批量生产的思想。
5．2从图林机到基于知识的系统
弗雷格和罗素的现代形式逻辑以及希尔伯特和哥德尔的数学证明理论，主要受到了莱布尼茨通用数学纲领的影响。手摇计算机（图5．1）是对于5．1节所述莱布尼茨机的抽象，可以方便地推广到马尔文·闵斯基的所谓寄存机。它使人们在现代计算机科学中可以定义一般的可计算性概念。
一台手摇计算机只有两个寄存器TM和RM，只能输入相当小的自然数。一台理想的寄存器具有有限个寄存器，它们都可以贮存任意有限个数量。寄存器用自然数i＝1，2，3，……标记。寄存器i的内容用（i）来标记。作为一个例子，装置（4）：＝1意味着，寄存器4的内容为1。如果其内容为0则寄存器是空的。
在手摇计算机中，加法或减法仅仅由两个寄存器（SM）和（RM）来实现，（SM）＋（RM）或（SM）－（RM）都将存入寄存器RM。在寄存机中，减法－的结果应为0，如果大于。这种修改的减法标记为－。一般地，理想寄存机的程序是用如下的基本步骤作为建筑块来定义的：
①向（i）中加人1并把结果置人寄存器i，即（i）：（i）＋1；
②从（i）中减去1并把结果置人寄存器i，即（i）：＝（i）－1；
这两个基本步骤可以运用如下的概念进行合成：
③如果P和Q都是明确定义的程序，那么P→Q也是明确定义的程序。P→Q意味着，机器必须在执行程序P之后执行程序Q。
④程序的重复，这对于乘法是必要的，例如，重复相加受到如下问题的控制：一定的寄存器是否是空的。
这种反馈可以示意如下：
如果P是明确定义的程序，执行P直到寄存器i中的内容变成零。
程序的每一基本操作①和②都计为一步计算。一个简单的例子是如下的加法程序：
机器的每一状态都表示为如下的矩阵，它不断地把（j）的内容y加到寄存器（i）的内容X中，同时使得（j）的内容逐步减少到零。x＋y加和的结果显示在寄存器中：
一台具有程序F的寄存机定义为，计算出n个自变量的函数值f，即对于寄存器1，…，n中任意的自变量x1，…，xn（对于所有其他寄存器均为零），执行程序F，在有限步骤后停止，此时寄存器1，…，n中函数的自变量和寄存器n＋1中的函数值为f（x1，…，xn）
按照相应的矩阵进行运算。函数f称作由寄存机RM可计算的（RM－可计算性），如果由程序F计算f。
一定程序F计算一个函数f所需的步骤数，由该程序所决定，并取决于函数的自变量。程序F的复杂性用函数SF（x1，…，xn）来度量，它计算出按照程序F进行计算的步骤。例如，x＋y的加法程序的矩阵显示了，y步加上1的基本步骤和y步减去1的基本步骤是必要的。因此，SF（x，y）＝2y。由于RM可计算函数f可以由若干种程序进行计算，函数g称作函数f的步骤计算函数，如果有一个程序F去计算f，且对于所有的自变量x1，…，xn有g（x1，…，xn）＝SF（x1，…，xn）。一个函数的复杂性定义为最好程序的复杂性，最好程序即进行函数计算时花费步骤最少的程序。
显然，闵斯基的寄存机是一种对于莱布尼茨的手摇计算机的直觉概括。但是，历史上另一种等价表述的机器是阿兰·图林和埃米尔·波斯特在1936年首先提出来的。图林机（图5．2a）可以执行任何有效的程序，如果该程序是正确编程的。它的构成：
a）控制箱，其中置入某个有限程序；
b）潜在无限的带子，带子上划分出小方格；。
c）计数装置，或将每一结果打印在带子的每一方格中，沿着带子的移动或停机都处于控制箱的命令控制下。
如果图林机使用的符号限制在竖线I和空格*，那么可以证明，RM可计算函数是图林机可计算的，反之亦然。我们必须记住，每一自然数都可以一个x条竖线的序列来表示（例如3表示为III），每一竖线都占据图林带子上的一个方格。空格*用来标记空的方格（或相应的数字为零）。特别是，对于分开代表着数目的坚线序列，空格是必要的。因此，图林机计算一个自变量为x1，…，xn的函数f，始于带子上的…*x1*x2*…*xn，停机于…*x1*x2*…*xn*f（x1，…xn）*…。
从逻辑学的观点来看，一台通用计算机是技术上实现了的通用图林机，——如美国的约翰·冯·诸葛曼小组构造的计算机以及德国的康拉德·朱斯独立构造的计算机。它可以执行任何种类的图林程序。同样，我们可以定义一种通用的寄存机，它可以执行任何种类的寄存程序。实际上，通常设计的冯·诺意曼机包括中心处理器（程序控制器），记忆装置，算法单元和输人－输出装置。它以长序列方式一步一步地运行。今天的一台冯·诺意曼计算机实际是一台通用化的图林机。图林机的效率可以由引进几条带子而增加，它们不必是一维的，每一条带子有一个或多个读写头，但是都要报告给单个控制箱，控制精协调着机器的所有活动（图5．2b）。因此，这种更有效的机器的每一计算都可以由一台普通的图林机来实施。从复杂系统探究方式来看，一台多带图林机仍然是一种程序控制的计算机，与自组织系统如神经网络有本质上的差异。
除了图林机和寄存机以外，可计算函数还可以用许多其他数学上等价程序来定义。递归函数由函数置换和重复来定义，它始于某种显然是可计算的基本函数（例如相继函数n（x）＝x＋1）。所有这些由图林机、寄存机、递归函数等来定义的可计算性，可以被证明是数学上等价的。显然，每一种这样的精确概念都定义了一种程序，这样的程序是直觉上有效的。
因此，阿朗索·丘奇提出了他的著名公设，有效程序这个非形式的直觉概念与图林机那样的等价的精确概念是一致的。丘奇的公设当然是不可能证明的，因为这里是数学上精确的概念与非形式的直觉概念的比较。然而，几种精确的可计算性概念的数学等价在直觉上是丘奇公设的有效确证。结果是，我们可能在不涉及特定的有效程序（“算法”）如图林机、寄存机、递归函数等时，来谈论可计算性、有效性和计算函数。按照丘奇的公设，我们特别可以说，每一可计算程序（算法）都可以由图林机进行计算。所有的递归函数作为一种机器程序，都可以由通用计算机进行计算。
现在，我们能够定义决策和可计数的有效程序，而莱布尼茨的通用数学纲领就已经提出了这样的要求。自然数的集合M的特征函数fM定义为fM（x）＝1，如果x是M的一个元素，否则fM（x）＝0。因此，子集M被定义为有效可决定的，如果其特征函数对于一个数无论是否属于M，都是有效可计算的（或递归的）。
集合M定义为有效（递归）可计数的，如果存在有效（递归）程序f可相继地产生出其元素（对于M中所有元素x1，x2，…，有形式f（1）＝x1，f（2）＝x2，……）。容易证明，所有递归（可决定的）集都是递归上可计数的（或递归的）。但是，存在着这样的集合，它是递归上可计数的，但却不是可决定的。这是第一条线索，它意味着，莱布尼茨的基于通用可决定程序信念的乐观纲领存在着局限性。
对于自然智能和人工智能，有效可计算性范式意味着精神是由程序控制机器表示的。神经结构涉及的是符号数据结构，而精神过程也就是操作算法。历史上，AI的核心是在1956年的达特茅斯会议期间建立起来的。参加会议的约翰·麦卡锡、阿兰·纽厄尔、赫伯特·西蒙以及来自其他不同学科领域的一流研究人员，形成了新的AI科学共同体。他们都受到图林的“机器能否思维？”问题的启发，这个问题是图林在著名的《计算机器和智能》（1950）一文中提出来的。
在莱布尼茨的通用数学的传统中，人们可能会相信，人的思维可以用某种通用演算来形式化。在其现代的翻版中，人们可能会假定，人的思维可以用某种强有力的形式编程语言来表示。无论如何，形式表达式都是符号序列，是可以用自然数进行编码的。于是，对于对象的断言就相应于关于数字的函数，结论就将从某种有效的计数程序中得出，如此等等。实际上，现代计算机的机器语言就是由数字序列构成的，对于机器的每一状态和程序进行了编码。因此，计算机的操作可以描述为有效的或递归的数字程序。
如果人的思维可以用递归函数来表示，那么按照丘奇公设，它就可用图林程序来表示，而图林程序可以用图林机计算。因此，人的思维也就可以用通用计算机来加以模拟，在此意义上，对于图林提出的问题也就必定要回答“是”。人的思维是可以编码、可用递归程序来表示的，这一前提当然是可疑的。甚至数学思维的过程也可以远比递归函数更为复杂。按照丘奇的公设，递归性或图林可计算性仅仅是可计算性的一种理论限度。
下面我们希望考虑在这种限度之下和之上的复杂性程度问题。在这种限度之下，有许多涉及到一定限度的实际问题，其限度涉及到如何增加算法的速度。特别是在数学问题中，有一些种类的问题，它们的算法求解本来要比解决其他一些问题困难得多。因此，图林机有不同程度的可计算性，计算机科学中的复杂性理论使之精确化。
问题（或相应的函数）的复杂性分类可以由复杂性程度来标志，这给出了函数的阶，函数描述了依赖于其输入长度的算法（或计算程序）的计算时间（或基本计算步骤的数目）。输入的长度可以用十进制的数目来度量。按照计算机的机器语言，可以方便地将十进制数字编码成仅仅用0和1的二进制码，并用二进制字符来定义其长度。例如，3的二进制码是11，其长度为2。函数f具有线性的计算时间，如果f的计算时间不大于c·n，其中n是输入长度，c是常数。
两个（二进制）数的加法显然只具有线性计算时间，例如，对于3＋7＝10中应的二进制计算
0 1 1
1 1 1
__________________
1 0 1 1
其中需要5个基本计算步骤把两个二进制数加和（包括运算）。我们提醒读者，加和二进制数字相加的基本步骤是0＋0＝0，0＋1＝1，1＋1＝10，以及运算。可以方便地假定，两个将要相加的数具有同等长度。否则，我们简单地把较短的数加上一系列的零，例如，111和011而不是和11。一般地，如果将要相加的特定的数对的长度为n，则一个数的长度为n/2，因此，我们需要不大于n/2＋n/2＝n个基本计算步骤，其中包括了运算。
函数f具有二次计算时间，如果对于所有的长度为n的输入和常数c，f的计算时间不大于c·n2。
一个简单的二次计算时间的�
