论算法的逻辑特征及其方法论意义，本文主要内容关键词为：方法论论文,算法论文,逻辑论文,特征论文,意义论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：B812 文章标识码：A 文章编号：1671-7406(2002)06-0106-05
算法是数学和计算机科学的一个基本概念，而逻辑学是这两门学科的共同理论基础之一，因此，可以从逻辑学的角度对“算法”这一概念进行分析研究，更进一步揭示其深刻的逻辑特征。从理论的深层次上来看，算法概念确实涉及一些基本的逻辑问题。
一、算法的含义
“算法”这一概念来自拉丁文单词Algoritmi，是9世纪阿拉伯数学家阿尔·霍列士米首先提出来的，它最初的含义是指十进制计数法和十进制四则运算的法则。
算法概念象集合、对应、自然数、关系等概念一样，也是逻辑学和数学的一个基本概念，不可能用更简单的概念来给它正式下定义，而只能象其他数学基本范围一样，直接从科学经验中抽象出来。
所谓算法，是指当我们要从最初的可变资料（信息）中导出所要求的答案（结论）时，需确定的一个计算过程，这个计算过程由一组准确有序的操作指令构成。对“计算”这一概念要从广义上来理解，不应把它理解为仅仅是数字的计算。广义的计算是一种符号和信息的变换过程，例如代数学中的各种符号运算、信息处理中的信息符号的变换（如编码、译码等）、把一种语言翻译成另一种语言等等。在这些变换过程中，都存在着必须遵循的算法。
算法在科学研究中具有普遍意义。解决科学问题需要一定的方法，但“方法”这一概念含义广泛而不具体，而算法与一般方法相比，则更具体、更精确，因为它是能行的、可操作的。能解决某个科学上的问题，实质上就是意味着掌握了或找到了某种算法。从逻辑的角度来看，所谓“问题”是一种任务，它要求寻找某种具有某些属性或满足某些条件的对象，这种对象就称为问题的解。如果能寻找到这样的对象（或证明这样的对象是存在的），问题是可解的；反之，如果不能寻找到这样的对象（或证明这样的对象不存在），问题就是不可解的。确定一个问题的不可解性，在科学研究中、在人类的认识史上，是具有重要意义的，它可以避免人们为此付出无谓的代价。某一问题的可解性意味着能够找到一个适当的算法，而某一问题的不可解性则意味着不可能找到一个适当的算法。在科学史上，很多研究工作的任务和目的，就是要寻找解决某个问题的算法。数学和逻辑学的研究中产生的许多课题，其目的就在于要寻找这样或那样的构造性方法，即算法。探索这样的方法以及证明在原则上不存在这样的方法，是科学认识发展的一种强大的动力。例如，19世纪集合论概念的产生，就是由于当时人们意识到不可能依靠直接计算（狭义计算）解决任何数学问题而必须寻找新的方法（算法），来处理一些数学对象和数学问题。
二、算法的基本逻辑特征
一个算法是一个能行的操作过程，这个过程有一套清楚准确的规则和指令组成，这些规则和指令规定了操作的要求和操作的步骤，经过有限的步骤使问题能得到解决。算法具有以下基本逻辑特征。
1.确定性
算法的规则和指令的含义要求确切和人人能理解，不能具有二义性，其中不能包含可以任意解释的地方，即要保证每一个规则和指令只有一种唯一的解释。由于算法中的规则和指令的这种确切性，算法过程就是被决定了的（或具有决定性），即算法过程的每一步骤都单值地（单一地）被上一个步骤所决定，同时又单值地规定了它的下一个步骤。算法的决定性保证一个人有可能将一个算法告知另一个人，而后者即使没有前者参加也能执行这个算法。正是由于这种决定性，才可能将一个算法交给机器去执行。算法这一概念的提出，对电子计算机的产生具有重要的意义。电子计算机与以前所有计算工具的本质区别在于它能够摆脱人为的暂时干预，自动连续地进行各种操作，而这种自动功能是基于冯·诺依曼所提出的“程序存贮”这一计算机的基本工作原理的，这一基本工作原理又是基于算法的决定性的。没有算法的决定性，就不可能编制程序和存贮程序。编制程序就是把一个算法转换成计算机能识别和执行的有序指令集合。“程序存贮”实际上就是人把算法告诉计算机。
2.对象性
每一个算法都要从一定的可变异的初始资料（可加工的初始信息）出发，或者说，每一个算法都必须以一定的可变异的初始资料作为操作对象。每一个算法都有自己的资料总体，即它适用于一定性质、一定范围的资料。算法与它适用的资料总体不是相互分离的，算法本身的性质、内容决定了它所适用的资料范围。当某个具体对象被作为一个算法的初始资料时，就叫做把这一算法应用于这个对象。如果一个算法应用于某个对象而得出了一定的结果，则称这一算法适应适用于这个对象。没有适用对象的算法是没有意义的，因为这样的算法无法开始执行，因而也就不能得到任何结果。
3.可执行性（可操作性）
算法的每一步操作都是可以被执行的。如果出现不能执行的操作（指令），算法过程就会中止。例如，A÷B这一算术操作，当B=0时无法执行（这在计算机程序中称为“零除错误”），同样，SQR(x)（对x进行开平方运算）这一操作，当x为负数时无法执行。在逻辑推理中，由“A是B，并且C是D”推不出结论，即对这两个前提无法进行推理操作，因为根据三段论推理的要求，从没有共同中项的两个性质判断推不出结论；由(A→B)∧B也推不出结论，因为它不符合推理规则。正确的逻辑推理是具有可执行性（可操作性）的。一个算法不具备可操作性，就不能解决任何问题。
4.有穷性
算法必须在经过有限步骤的操作后，就能得到一个结果，也就是说，不能要求经过无限的操作步骤才能取得结果（这实际上也无法得到结果）。例如，不能要求计算机以无限的步骤去计算出圆周率π的精确值。要求用人工的方法经过无限步骤完成一个算法的操作，更是没有意义。一个逻辑推理过程的推理步骤，如果是无限的，则不可能得出一个确定的结果。应该注意，不能把算法的这一特点理解为必须确切了解经过多少步骤才可以取得结果，一个算法可以不知道要多少步骤才能取得结果，但是必须是有限步骤的、是能够终止的。算法的有穷性在判定问题中表现得尤其重要，在图灵抽象计算机中它表现为“停机”。不能“停机”的问题是不可判定的。一阶逻辑的不可判定性，主要并不是不能找到一个判定算法，而是这样的算法不具有有穷性，它不能结束，在判定时不能“停机”。这是由于一阶逻辑的对象域是无限的。
5.结果性
算法具有获得未知结果的趋向性，也就是说，一个算法必须能够取得一定结果，这是算法的目的所要求的。但是，对这一特点不能理解为必须取得人们所期望的结果。如果要求算法的结果与人们所期望的结果一致，算法本身就成为不必要的了，因为这时结果是已经知道的了，而算法的意义则是在于要探索未知的结果。例如，我们在求一元二次方程时，期望得到实数解，可是有时所给定的方程无实数解，这时，所谓算法的结果性，就是指出此方程无实数解。
6.通用性（一般性）
一个算法必须能够求得一类问题的解而不只是一个特殊的、具体问题的解。例如，一个算法只能计算3+5的和，就没有通用性；如能计算任意两个自然数的和，就有一定的通用性；如能计算任意几个自然数的和，则可看成是具有通用性，因为几个自然数求和成为一类问题。一个算法是一个计算过程（并不必定是数值计算），是一个明确的能行指令集，用它可以找到给定的一类问题中的任何一个子问题的解答，这个算法在这类问题中就是通用的。
7.兼容性（等价性）
解决同一个问题可以有不同的算法。算法的兼容性是指一个算法与另一个算法等价。等价算法必须同时满足两个条件：(1)具有相同的初始资料（值域）、适用范围（定义域）和结果（输出值域）；(2)在适用范围内的任何输入，都产生相同的输出（结果）。或者概括地说，两个算法应用于相同的初始对象并得到相同的结果，这两个算法就是等价的（兼容的）。
三、算法论的主要研究内容
1.算法论
算法论就是以算法作为研究对象的理论，准确地说，它是研究构造性的理论。算法一般是指对能行性过程在一个形式系统中做出的具体描述。因此，一个能行过程常常用一个算法来表示。对过程的结束与否不作规定，从而只着眼于该过程计算本身或该过程的各次中间结果的，叫做演算；如果规定过程在什么情况下应该结束，从而根据结束时的状态得到该计算过程的结果的，则叫做算法。算法中如果规定了每次唯一的操作方式及操作结果，从而从头到尾的过程唯一地确定的便叫做一义算法或确定性算法，否则，便叫做多义算法或不确定性算法。起初人们用一般递归函数或图灵机器来描述能行过程，后来苏联学者马尔科夫提出使用算法来刻划能行过程，他提出正规算法的概念，并且证明正规算法的概念与递归函数的概念是等价的。事实上，递归函数论可以看作一种演算而图灵机器可以看作一种算法。后来，稍经变换又由乔姆斯基把演算（他叫做文法）概念用于形式语言中，在形式语言的研究中起了主要作用。
2.算法的实现：潜在性与实际性
一个算法可以分解成一系列独立的步骤，而每一步都必须确切、简单明了，具有可执行性，因而它具有实际实现的可能性。但有时，为获得结果所需要的基本步数可能如此之大，以至可以认为，要得到结果在实际上（一定条件下）是不可能的。因此，一个算法就存在实际可实现性和不可实现性两种可能。当然，实际可实现性与不可实现性的界限是相对的，它会随着人的认识能力和计算工具、计算手段的发展而改变。在算法理论的研究中，不考虑算法的这种“实际的可实现性”，而认为任何算法只要是有限步骤的、可执行的，都是可实现的。这种可实现性称为潜在的可实现性，它超出了实际可实现性的现实界限。电子计算机运算速度的不断提高，使这种界限不断被突破。昨天还是潜在可实现的，今天已成为实际可实现的了。所以，算法论的研究与计算机的实际操作能力是密切相联系的。要让机器去解决某个问题。没有事先编制的可实现的解题算法是不可能的。编制这样的算法具有非常重要的意义，例如机器翻译问题主要是编制翻译算法。算法论与计算机科学相结合，就是要研究怎样使算法的潜在可实现性向实际可实现转化。对宁可计算函数，也存在两种情况，即理论的可计算性和实际的可计算性。“理论的可计算性”就是潜在的可实现性。研究可计算函数的主要目的，就是要使它的理论可计算性转化为实际的可可计算性（用机器或人工来实现）。
3.算法与可构造对象
“潜在的可实现性”这一概念很重要，它不仅在考察算法过程时是需要的，而且在考察参与这些过程的对象本身（如“初始资料”和“结果”）时也是需要的。在算法的潜在可实现性的范围内可以加以构造和考察的对象称为可构造对象。例如，形式系统中的演算所包含的表达式（即合式公式）就是可构造对象，这就使算法论工具也可以运用于形式系统。任何一个算法都是可构造对象，因为一个算法是一个有序指令集，这些指令可以用某种符号组合形式写下来，这就是一种可构造性。可构造对象组成各种集合，而每一个这样的可构造对象集都是用构造属于它的对象的方法形成的，这样的方法就是算法。因此，算法是可构造对象的产生工具，一个可构造对象集总是与一个算法对应的。举一个简单的例子：已知算法f(1)=2,f(n)=2f(n-1)-1，根据这一算法，我们可以构造出这样一个对象集2,3,5,9,17,33,……。又例如，在信息处理中，输入信息就是可变（可加工）初始资料，对信息的处理方法就是算法，而输出信息就是算法根据输入资料构造出来的对象。如果没有算法，即使有输入信息，也得不到输出信息。算法好象一个加工器，它对输入信息进行加工而产生输出信息。所以，算法在信息科学中具有重要意义。研究信息处理的方法，实质上就是要寻找加工信息的算法。
4.算法与抽象对象
对象有现实对象和抽象对象两类。现实对象就是客观世界中存在的各种各样的具体事物，而抽象对象只存在于观念中。科学研究特别是象数学、逻辑学这样高度抽象的科学研究，主要是与抽象对象打交道，或者说它们的研究对象主要是抽象对象。
抽象对象是基于同一性的抽象概念的。在某些场合下，我们可以将两个对象说成是同样的。“同样性”的条件是根据每个场合的特定情况确定的。可构造对象是由某些非常简单的基本部分组成的，所以，两个可构造对象，只要它们由同样的基本部分组成，并且这些基本部分的配置次序也相同，就被认为是同样的。同一的抽象性使得人们可以把同样的对象看作是统一个对象。同一的抽象性导致了“抽象对象”的概念，这就是把两个“同样的”具体对象看作同一个抽象对象的两个代表。每一个应用于同样对象的算法，也产生同样的对象。因此，每一个算法都指明了抽象抽象对象可构造对象的变换过程。算法的这一属性（以及它的决定性）决定了它的重复性或可再现性，即当一种算法作为抽象可构造对象的算法而形成以后，就可以重复应用于适合该算法的任何具体可构造对象。逻辑学中的合式公式就是一种抽象对象，它是一定的规则（算法）产生出来的。一个数学表达式也是一个抽象对象，它也是由一定的算法（数学演算规则）产生出来的。
5.算法与可计算函数、可判定集和可枚举集
在算法概念的基础上，效理逻辑和基础数学中产生了一些相应的基本概念，如可计算函数、可判定集、可枚举集。
可计算函数：一个函数称为可计算函数，就是指存在一个计算该函数的算法，它满足两个条件：(1)这个算法适用于函数定义域中的任何一个对象，并且所得出的结果是函数以此对象为自变量时的函数值；(2)这个算法不适用于函数定义域之外的任何对象。
可判定集：可构造对象集中的某个子集（即由该集的某些对象所组成的集）称为可判定集（相对于它的母集而言），是指存在一个可以判定该集的算法，这个算法适用于该母集的每一个对象，并且所得出的结果就是关于对象是否属于被考察的集这一问题的答案，也就是说，该母集中的每一个对象是否属于被考察的子集，是完全可以确定的。
可枚举集：一个非空集称为可枚举集，是指存在一个能够枚举这个集的算法，它满足两个条件：(1)该算法适用于任何一个自然数，而所得出的结果属于被考察的集；(2)被考察集中的每一个元素都可以作为将该算法应用于某个自然数的结果而得到。
同一个可计算函数（或同一个可判定集、同一个可枚举集）可以用不同的算法来计算（判定、枚举）。从定义可知，可计算函数的自变量和值、可判定集或可枚举集的元素，都是可构造的。
6.算法概念的精确化
使算法概念精确化的研究工作，最先是由波斯特和图灵在1936年前后开始的，他们各自独立地提出了相似的抽象计算机的定义，这种抽象计算机的用途就是实现一个算法过程。这种抽象计算机是在电子计算机产生之前提出来的，但它却表现出了电子计算机的许多特征。要使算法概念精确化，一般的思路是，描述某个具体的算法类，使得任何一个算法都能用这一算法类的某个等价的算法来实现。
算法概念的精确化是基于以下这些基本思想基础之上的：算法过程可以分解成为一些单独的、足够基本的步骤；每一步骤都是算法过程的一个状态与另一个状态的交替环节；初始资料也就是初始状态，它没有前趋状态，只有后继状态；从任何一个状态到下一个状态的过渡都是根据被认为是足够基本的所谓直接加工规则进行的；某些状态被规定为结束状态（根据足够基本的结束规则），而从结束状态就可以引出最终结果（也是根据足够基本的规则）。把算法应用于某个对象时，算法过程的进展可能有三种方式：(1)每一个状态都被下一个状态所代替，而过程永不终止（图灵机中称为“不能停机”）；(2)在某一步上出现了一个既不适用于直接加工规则也不适用于结束规则的状态，于是发生无结果中断；(3)在某一步骤上所出现的状态，被认明为结束状态，于是发生有结果的中断，也就获得了算法的最终结果。一个有效的算法仅仅适用于其算法过程按照第三种方式进行的那些对象。算法概念的精确化，实质上在于规定直接加工规则、结束规则和最终结果引出规则的某种具体形式，同事也就规定了可构造对象集，而且将上述规则应用于该集的每个对象都是有意义的。
在对算法概念精确化时，产生了这样一个基本假设：对于任何一个算法，都可以在利用精确化描述的相应的算法类中指出一个与之等价的算法。算法的等价性就是指两个算法适用于同样的对象并且导致同样的结果。这个基本假设包含着算法的任意性或多样性的概念。对一种算法的不同形式的精确化，被研究证明是能够等价的。在计算机科学中，算法的精确化就是编制相应的程序。对于解决某一个问题的某一个算法，可以用同一种程序语言编出不同的程序，也可以用不同的程序语言编出不同的程序，而运行这些不同的程序所得到的结果是相同的。
在逻辑学中，有效推理过程精确化的最初形式，就是19世纪德国数学家和逻辑学家弗雷格提出的带有推理规则的形式化的逻辑系统。后来英国逻辑学家怀特海和罗素又建立了足够有效的形式化演算系统，借助于这种形式化演算系统，可以确定任何一个可计算函数。1943年，哥德尔用形式化演算系统的推理规则确定出可计算函数。在波斯特和图灵的研究工作的基础上，就可以根据它们提出的算法概念的精确化方法来确定可计算函数。可计算函数的确定依赖于算法的精确化，而算法的精确化又依赖于逻辑系统的形式化和精确化。
四、算法论与逻辑学
1.可判定集、可枚举集与定义方法
逻辑学中有两种基本的定义方法，即“属加种差定和“归纳定义”。这两种定义方法与可判定集和可枚举集有密切联系。
用“属加种差”方法下定义时，要先确定某一类对象所属的总体对象集（即属），再指出这类对象区别于同类中其他对象的特征（种差），以便从这个总体对象集中区分出被定义的一类对象。如果认为这一定义是可构造的，即对象是可构造的，并且属元素的种差存在与否在算法上是可以辨认的，则被定义的集是可判定的，并且每一个可判定集都可以这样来确定。由此可见，可判定集与通过属加种差方法被构造性地定义的集是等同的。
归纳定义由两部分组成：(1)奠基部分（或称初始验证），验证被定义的部分对象具有某种属性；(2)归纳部分，它表示如果某种对象属于被定义的类，则与它们有一定关系的其他对象也属于被定义的集。如果定义是构造性的，即被定义对象是可构造的，并且在奠基部分中出现的初始对象是有限的，而归纳部分所包含的、从已定义对象到新对象的转换规则是一种算法，那么就可以获得一个按归纳法构造性地定义的集。这样的集，是有效产生的集。这样的归纳定义实际上是给出了一个有效的产生过程，在这个过程展开的各个阶段上，发生着或产生着所定义的对象。任何一个形式系统或演算中的全部可证公式组成的集就是有效产生的集，这个集是这样产生的：公理按定义被宜称为是可证的，进而指出，如果某些公式是可证的，则由这些公式按照推理规则推出的那些公式也是可证的。可见，一切可证公式的证明过程都是有效的产生过程，同样，一切可反驳公式的反驳过程也是有效的产生过程。一个算法规定了一个有效的产生过程。逻辑学的证明、有效推理都是有效的产生过程，而推理规则集就是算法。
有效产生过程和算法是密切联系的。通过算法的有效产生过程可以进行归纳定义。有了有效产生过程的概念，就可以给可计算函数下定义，反之，任何可计算函数都可以通过有效产生过程来确定。从逻辑学的观点来看，算法过程和产生过程是相联系的，它们都以构造性概念为基础，两者的差别在于，算法过程是报据对一定操作方式的要求而展开，而有效产生过程则根据可能性展开。算法过程的每一阶段都是单值地即必然地规定了它的下一个阶段，而有效产生过程在展开时，每一阶段之后出现的是下一阶段的很多可能性，可以根据要求在这些可能性中选择一个。
2.算法与形式演算系统的不完备性
对有效产生过程适当精确化之后就得到一个算法，从而每一个可有效产生的集都是可枚举的，反之亦然。根据这一情况，以及可枚举集与可判定集之间的关系，可以得出结论：凡是可以用属加种差进行构造性定义的，也可以进行构造性归纳定义，但反之则不然。因此，有这样的对象类，对它可以下构造性归纳定义，却不能下属加种差的构造性定义，而该对象类的补集则不能下有效归纳定义。每一个构造性的产生过程都可以看怍适当演算中获得可证公式的过程。所以，具有上述描写的性质的对象类，可以在某一演算中作为全部可证公式而建立起来。已经证明，凡是内容足够充实的演算系统（例如谓词演算或算术的形式化系统）都会发生这一情况。因为如果演算是内容足够充实的，则其中就可以表达任何一个有效产生过程。这种演算的全部可证公式类是不可判定的，这就是说，能辨别演算的公式是否可证的算法是不存在的，在这个意义上可以说，演算是不可判定的。由于演算的全部可证公式类是不可判定的，所以与它相补的全部不可证公式类是不可枚举的，因而不能通过任何有效产生过程获得，尤其不可能构造这样一种演算，其中反驳并且仅仅反驳原来演算中的一切不可证公式。所有这些不可证公式都不可能用原来演算本身的手段来加以反驳，这就是说，原来的演算中存在着所谓不可判定的公式（即既不可证也不可反驳的公式）。这些推论可能仅仅涉及这样的公式，在对演算作含义解释时它们表达的是有意义的（即或者真或者假的）判断，在这样的公式中也可以发现不可证公式，在这个意义上可以说，形式系统是不完备的。总之，上述所作的推论具有一般性，所以，每一个内容足够充实的演算都具有不完备性。
演算的不可判定性概念依赖于算法概念，所以不可判定性问题要在算法论的基础上来研究。演算的不完备性这个基本的逻辑问题，可以借助于算法论的理论来解决。演算的不完备性表明，原则上不可能将逻辑推理过程完全形式化，关于这一结论，哥德尔在1931年给出了严格的证明。一些逻辑学家还提出建立构造性逻辑的思想，在构造性逻辑中，把每一个命题都解释为一个问题，但是对问题这一概念又要求具体化，而这种具体化只有在算法论的基础才能实现。与这种构造性思想有密切联系的是古典数学的概念和命题的构造性问题。这些问题也只有在算法论的基础上才能得到解决。由于数学分析基本概念的构造化，出现了一个新的数学分支——构造性数学分析。在实现构造化时使用的基本手段之一，就是把被研究的对象转换成它们的名称，而名称总是可构造对象，可构造对象又必须通过一定的算法产生（构造）出来。这些事实表明，应用算法论研究逻辑问题和基础数学（它的许多问题实质上是数学问题）问题，是有广阔前景的。
3.算法与判定问题
判定问题是逻辑学研究的重要问题之一。所谓判定问题，按直观、朴素的说法，就是去判定一个事物是否具有某种性质。判定问题的精确定义是：给定一个集合A和一个性质P，去寻找一个算法，它能告知对于集合A中的任意元素a，是否具有性质P；后者能证明不可能找到这样的算法。如果算法存在，则称此问题为可判定；如果能证明不存在这样的算法，则称此问题为不可判定。所以，对某个集的判定问题，就是要建立判定集的算法问题。在判定问题中特别重要的是为形式演算的可证公式类提出的判定问题。在现代逻辑中研究的判定问题，主要是针对形式系统的，也就是说要研究逻辑演算系统和表达在逻辑演算中的理论（主要是一阶理论）的判定问题。把命题逻辑、谓词逻辑和具有数学形式的理论处理成形式系统，其目的是为了精确地刻划逻辑和理论内容，以便掌握更多的知识。某一演算的全部可证公式类的判定问题也称为演算本身的判定问题。判定问题的研究是建立在算法概念的基础之上的。
收稿日期：2002-09-15