数学作为科学的语言

在数学的宝库中除了强大的计算能力以及其论证具有高度逻辑精确性之外，它还拥有灵活和通用的“语言”手段，藉此以构造出最形形色色的本质上是基础科学概念的足够清晰的模型来。正是通过这样的途径才产生了数理经济学、数理语言学、数学通信论以及其它许多具有相似含意名称的学科。以这样的观点来观察的数学正扮演着一个特殊角色——科学语言角色。伟大的伽里略就是这样去理解数学的，早在约四个世纪前他在一封信中写道：“哲学是写在对无一遗漏的每一个人都敞开着的一本宏伟的书里的。但只有学会懂得写这本书所用的语言和符号的人才有可能去理解它。它是用数学语言写的，它的符号是数学图形。”

有趣的是，就是数学的各个门类，时而也会遇到要“数学化”。在该学科的发展过程中将会到来这样的时刻，即当某些用于其中概念的精确度开始变得不足以解决某些发生于与我们有关问题的时候，这时就必须得建立起这些概念的较前更为精确的模型来。在数学中这类事件经常会伴随着：已定型观念的剧变、巨大的发现、激烈的争论、原则上是新的且通常是意想不到的观点的产生。

有关算法的不精确观念

当时（本世纪三十年代前）数学中的算法通常是被理解为确定由初始数据导出所求结果过程的准确指令的，同时要求决定运算过程的指令可以从不同的初始数据开始运算，初始数据在一定范围内变动——即具有大量性；2）处理初始数据的过程由有限个离散的步骤组成且完全是确定的——确定性；3）算法沿着可以得到所求结果的方向进行，在适当的初始数据条件下经有穷步后总能得到结果——有效性。这三个特征——大量性、确定性和有效性——是算法特有的，且决定了其在数学中所起的作用。

算法的一个很好的例子是十进位系统的自然数“竖行”加法规则。加数是由符号：0，1，2，3，4，5，6，7，8，9以任意方式组成的有限“链”（譬如341，82373等）。

规则本身可以下述指令形式确定。首先写下第一个加数（设为82373），在它下面这样写第二个加数（设为341）——先把二个加数的低位彼此对齐。然后，如果某一加数短于另一个，则在较短的那个左边补写零，直到双方链长相等为止（这样341就需写成00341）。此后从低位开始应用加法表并遵照进位规则自右向左依次逐位相加。当最高位也都被加起来时，过程就停止。按此规则所得之和即为所求（也就是82714，它写在这二个加数之下并用一条水平细线将它们隔开）。此指令的大量性、确定性和有效性都是满足的。

算法不是只用数字材料才可进行运算的。初始材料可具有更一般的特性。如我们可把自然数看作由0，l，…，9符号组成的链，但取其它——譬如俄文或拉丁文字母表中的字母，甚至某些数学符号也能替代这些数字符号。我们可用它们构成任意（但有限1）的链，并研究作用于这些链的算法。

这些链通常被称为“字”。同时把组成字的符号本身a₁，a₂，…，a_n称作字母，由字母组成的表叫做字母表。为了方便还引进空字一不包含任何一个字母的字，通常用希腊字母Λ表示之。

自然，与我们所研究的相类似的指令不只是在数学中才能遇到。与它们相似的尚有城市间电话自动机使用规则、不同种类的条令、药方等规则。

当然，在本节开头对算法作出的描述是缺乏数学的精确性的。它不是该字原义上的数学定义。但毕竟根据它往往还是能断定出，对解决某个问题来说是有算法的，且它所具的内容又有些什么。

为什么需要有精确的算法概念

不算太久前，在数学中“算法”这一术语是被理解为：存在“大量问题”，即从属于其值可以是为用于某种算法的初始材料的某个变量、参数的“个别”问题类。要求确定能解决该大量问题的算法，即它根据每个参数值可找出适合于它的个别问题的解答。

如果找到了这样的算法，它能用一个统一的办法来解决大量问题，当然是有很大价值的。因为今后该问题类中的任何个别问题都可用自动化加以解决。

现举一例，试寻求对任二个自然数m和n均能找出其最大公约数目НОД（m，n）的算法。这里大量问题“找出НОД（m，n）”与参数佛m和n有关，解决这问题所要找的算法就是著名的欧几里得算法，它如下述。如果m=n，则可取m为НОД（m，n）。如果则可构造出这样的自然数递减序列，其第一项为m与n数中较大的一个，第二项是其中较小的一个，第三项是第一项除以第二项后所得的余数，第四项是第二项除以第三项后的余数，如此继续，直到整除而无余数为止。这时最后一次除法的除数即为НОД（m，n）。[如求НОД（5767，4453），可得递减序列5767，4453，1314，511，292，219，73。这时73即为所求]。

希尔伯特于1900年8月8日在巴黎召开的第二届国际数学家会议上所作的著名报告《数学问题》中提出了希尔伯特第十问题，其表述为：“已知带任意未知数和带整系数的刁番图方程。试求得一方法，藉此可在经有穷步骤后确定，该方程是否有整数解”。

读者应明了，刁番图方程或不定方程，其形式为P（x₁…x_r）=0，其左边是从属于变量x₁，…x_r的整系数多项式。如方程x₁+x₂+1=0和x₁²+x₂²+1=0等。且只求其整数解。自然这样的解也许就没有——如列举中的第二个方程（因为不管X₁、X₂是怎么样的整数，x₁²、x₂²总是大于或等于零的，所以x₁²+x₂²+1就绝不可能=0）。没有解的方程称为不可解的。因此在希尔伯特第十问题中要求找到这样的算法，它能机械地识别出刁番图方程是可解还是不可解的。

许多杰出的数学家为寻找所求算法而竭尽了全力。但虽经多年的努力，稍可欣慰的只不过是找到了一些刁番图方程的特殊类型，对它们来说问题倒是可解的。然而一般性的算法却是无人能求得。

类似的情况也出现在一系列变得越来越迫切的有关代数、拓扑、数理逻辑以及另一些数学学科的算法问题上。如当时被称为数理逻辑可解性问题就是一例。该问题是要拟定出一个方法，它对专门的逻辑语言（谞词演算语言）的任一个公式都能道出，基于其自身的构成该公式是否为真。尽管经专家们的极大努力，这样的方法却始终没能找到。

于是就逐渐增强了这样的信念，即所求的算法一般说来可能并不存在。但用数学的精密论证来加强这个信念是没有任何可能的，因为还缺乏对算法的精确定义。一系列当时在数理逻辑领域以及在数学基础中萌发出来的最新思想对算法一般概念的本质进行研究_起到了推动作用。

算法理论的产生

危机是以对数学来说很突然也很不寻常的方式得到解决的。美国数学家丘奇（Church）、克林（Kleene）、波斯特（Post）与英国数学家图灵彼此独立地并几乎同时（在1936年）得出结论，有关算法的不清晰的模糊的观念可以（不失其一般性）以完全相适应的方式进行精确化、标准化。换言之，算法概念可由精确的数学定义得出了。

因此，这些作者们创立了清晰的能以数学方式来研究的算法概念模型。说实在，这样的模型甚至有好几个——所有作者从不同途径出发得到了在形式上不同的各种模型。但很快就弄明白，所有这些精确化——无论是丘奇的λ - 演算（λ-конврсие），或是克林的原始递归函数，或是波斯特的有穷组合过程，或是图灵机——它们在某种精确的涵义下都是相互等价的，它们之间纯粹只是外观上的不同。

丘奇是提出并论证能正确地反映我们对算法的直观观念本质所需精确化原理的第一人。这个原理被命名为“丘奇论题”。从那时候起算法理论就以精密的数学学科面目而问之于世了，并以自身深刻的成果以及在其它数学领域内的应用而日益丰富起来。

图灵算法

我们要介绍一下图灵机，由于其作用原理特别简单，因而特别适合于初学者。

现有某字母表A，它由字母a₁，…，a_n组成。字母表非空的字将以专门的分成许多方格的带子把它们记录下来。在某一格中记下字的第一个字母，第二格记字的第二个字母，以此类推，直到把字的字母记完为止。为了方便，我们把空格说成是：在这一格中填了个“空白符号”，用a₀表示之。

图灵机就是由一条带子、读写头等组成。带子分成许多小方格，方格上可记录各种符号，图灵机可处于有限个状态中的某一个状态，其中特别划分出二个——起始态和终止态。状态数与字母表A中的字母多少无关并可逐机变更。在每一瞬间机器“运算”到输入其中的带的一个方格上并读出记录于此格中的符号。当处于非终止态时，它根据所处状态和在该瞬间它读出的符号将会作出向带中被观察的方格上记下某个新符号（可能与旧的相同或是空的）的步骤，并转入到一个新的状态（也可能与旧的一致或终止），或是停在原处，或是向左或向右移动一格。如果此时带走出机器的“视野”，那么在相应的末端将加贴一个空格。当处于终止态时，机器就不再作出任何步骤了。

着重指出，机器顺序进行的步骤完全由其当时的状态及其当时在带上被读出的符号所决定，因此该机器所有可能的步骤称为它的“基本反应”——可以把它们编制成带二种类别的表格：行为符号类（每个符号，包括空的，均入于此）；列为非终止态类（每个非终止态均入于此）。行和列的交叉方格，以某种形式记录下在该情况下机器要进行的步骤（此信息，有如上述，包括三个单元：顺序符号、顺序状态、带的移动）。机器的行为完全由指定的表——其程序所决定。因此我们有权说机器实际上就是表（程序）。

现在我们将确定，该机器M是怎样把字母表A中所给字P进行处理的。我们取一定长度的带并在其上记下这字。然后在机器“视野”范围内确定带的第一个格并使机器处于起始态。此后它依照其本身程序开始实施步骤一展开了M作用于字P的过程。如果经有限步骤后此过程中断（机器转至终止态），则读出记录在接受机单元内的符号。如果符号是空的，则把空字作为M对字P的作用结果[记为M（P）=Λ]。如果它不空，则以该读出符号为核心取其二端所有标记了的（包括该读出符号在内的非空白的）格子的最大连续段的符号串组成字Q。此字就是在该情况下所求结果[记为：M（P）=Q]。如果M对P的作用过程为无穷延续，则可认为M（P）值是不定的。

这样任何图灵机均提供了某种具有精确描述类型的算法（图灵算法）。对此算法来说字母表A中的字为初始材料和作用的所有可能结果。

图灵算法复杂性的重要测度为乘积m（n+1），这里m - 机器非终止态数，n - 机器在其中作用的字母表的字母数。此乘积决定了为算法程序存储所需的储存器容积。引入这个度量，我们就可以试图证明有关的定理，即为解决某个问题可以找到具有一定复杂程度的算法、而比这复杂度小的算法是决不会找到的。因此某个问题解决的艰巨性可根据图灵算法对该问题作用的步骤数加以测定。

现要问：这种类型算法的一般性程度究竟如何？须知很多具有明显方式的算法从形式看是完全不同于图灵算法的。然而详细的构成分析指出，任何一种算法在用字对其初始材料和作用的可能结果经过适当编码后均可以等价的图灵算法进行计算（即得到同样的结果）。这就是相应于图灵算法的丘奇论题的表述。

我们能否以精确的数学定理的形式来证明这个论题呢？不能，因为在其表述中有不精确的模糊的如所谓“一般性算法”的观念出现。然而我们可以举出大量的能增强丘奇论题可信性的论据。虽然它们不满足数学严密性的标准，但却有着非常令人信服，几乎是不容置疑的事实。其中作为图灵机其实只是以抽象形式效仿按照事先拟定好了计划而进行运算的数学计算家的工作的这一实例是最有说服力的。

当前未必有哪位数学家还会怀疑起丘奇论题的正确性来。但作为证明的手段，它自然是不能利用的。因此它主要是被用作为一种重要的启发式手段。

不可解的算法问题

算法概念的精确性很快就带来了效果，1936年当年丘奇就以数学定理的形式证明了数理逻辑的可解性问题，即任何可解决该问题的精确化了的算法（如图灵算法）是不存在的。结合丘奇论题，我们可取得该结果的更为广泛的连非数学家都感兴趣的解释：解决此可解性问题的任何算法一般是不可能有的。实际上，若真有这样的算法存在，则根据丘奇论题，就可找到能解决此问题的图灵算法，但由上述丘奇的结果这是不可能的。

1947年苏联数学家马尔高夫和美国数学家波斯特同时并彼此独立地确定了半群字问题的不可解性。解决这个问题（其实是确定其不可解性）需要创立把一些问题归结为另一些的极为精细的研究方法并可进一步证明一系列其它算法问题的不可解性。鉴于解决这一问题马尔高夫创立了正规算法理论。

1952年苏联数学家诺维高夫证明了群的字问题的不可解性。1958年马尔高夫证明了另一著名算法问题——多面体同胚问题的不可解性。最后在1970年时年只有22岁的列宁格勒数学家麦基耶赛维契证明了著名的希尔伯特第十问题的不可解性：解决该问题的算法同样也是不可能有的。

发现在数学算法问题中存在不可解这一事实对专家们是一个严重的警告。今后，欲解决这类问题的数学家总得先弄清楚，它是否一般不可解。

自然，算法精确概念的意义对数学来说远不尽于此。特别是在由马尔高夫创立的数学结构的构成性程序中，它起到了由它们能建立起其它数学概念的这些基本“砖块”之一的作用。

算法概念在逻辑和语言学、心理学当然也在计算科学中得到应用。它在数理经济中，在管理、人工智能、机器翻译中，在应用数学中也经常会遇到。

本文只是简单地向读者叙述，在数学中事件是怎样以不大——就像当时感觉到那样——并静悄悄地在发生着，而后却又以其明亮的光辉照耀着本学科以及与它相邻近的知识领域。

[科学与生活（俄），1985年No.1]