试析优选论的计算复杂性问题

马秋武, 吴力菡

(1.复旦大学 外文学院， 上海 200433； 2.广西民族大学 外国语学院， 南宁 530006)

优选论(Optimality Theory，简称OT)自20世纪90年代诞生开始就引起国内外研究者的广泛关注。在保留其核心理论框架的前提下，优选论经历了多次技术上的调整以解释更多的音系问题，并被拓展到音系以外的其他领域，如句法、语用等，可见其理论思想具有较强的活力，其操作模式具有开放性，因而至今仍然是语言学界的主流理论之一。但与此同时，20多年来，围绕优选论产生的各种质疑和争论也从未间断过，优选论在理论和应用上一直面临着不少挑战。其中，优选论所具有的独特的操作模式和计算方法引发了近年来在计算音系学领域中对于优选论计算复杂性(computational complexity)问题的热议。所涉及的问题包括：优选论中的生成问题是否属于NP难解问题？学习者如何习得计算量庞大的制约条件等级排列以及底层形式？等等。对此，Eisner(1997)和Isardi(2006a, b)等人试图论证优选论在计算上是不可解的(intractable)从而否定优选论的运行模式。Kornai(2006a, b)，Tesar(1995)，Heinz, et al(2009)，Riggle(2009)，Kager(1999)，Prince and Smolensky(1993/2004)等人则从不同角度对之进行反驳，支持优选论。本文首先介绍有关计算复杂性的相关概念，然后概述来自双方的论点，进而对优选论的其他相关问题进行总结。

一、有关计算性的相关概念

早在20世纪50年代末，Chomsky便将数学思想引入到语言学研究当中，将二者结合起来，形成一种形式语言学理论。这种形式语法具有算法(algorithms)的特点。换言之，语法作为一种生成句子的装置，很像数学中的“算法”过程(陆极致1990:171, 182-183)。

所谓算法指的是一系列解决问题的清晰指令，是一个有限规则的有序集合，对于某类问题的初始输入，它能在有限时间内机械地逐步计算，在有限步骤后计算终止，获得一个输出结果。一个问题可以有多种算法。一个算法的优劣可以用时间复杂度(time-complexity)和空间复杂度(space-complexity)来衡量，分别表示完成计算过程所需的总步数以及所用存贮的单元数(Mitkov 2003:178; Linz 2001:343-344; 堵丁柱等 2002:17; 赵瑞清、孙宗智 1989: 54-57; 张泽增 1989:4)。

时间复杂度关注的是当某个问题的规模扩大后，程序运行所需的时间增长得有多快。这里需要区分多项式(polynomial)时间算法和指数(exponential)时间算法。形如n2的多项式中，表示问题规模或大小(size)的参数n在底数位置；形如2n的指数时间算法中，n在指数位置，随着n的变大，它所需的计算时间以爆炸性的速率迅速增加。例如，在一台每秒做1亿次运算的计算机上，对于时间复杂度分别是n3和3n的算法来说，当n达到60时，它们所需的计算时间分别为2.16×10-3秒和1.3×1011世纪。显然，当n较大时，后者所需的时间是计算机无法承受的。

所谓问题，指的是从输入映射到其结果(即输出)的函数。设f为多项式函数，n为输入的长度，当且仅当该问题存在着能在f(n)步之内完成该函数的图灵机(Turing machine)时，这一问题便“在多项式时间内可计算”(Heins, et al 2009)。多项式时间算法(或称有效果算法)被认为是好的算法，计算机可以执行。有好的算法的问题是易解(tractable)的，属于P类问题，即在确定型图灵机上有多项式时间算法(实际可用的算法)。若一个问题找不到或尚未找到有效算法，则称为难解的(intractable)，属于“非确定多项式算法(non-deterministic polynomial-time algorithm)”，简称为NP类问题。如果所有NP问题都能规约(reduce)到某一种问题，那么这种问题称为NP难解(NP-hard)问题(张泽增 1989:1-38; 张立昂 1996:227-228)。

二、优选论的计算复杂性问题

1.经典优选论的运算模式

优选论把语言形式看成是制约条件交互作用的结果。其语法体系包括三大部分：生成器(Generator)、制约条件集合(The Constraint Set)和评估器(Evaluator)，通常分别简写为GEN，CON，EVAL。它的运算模式如下：生成器为某个输入项生成一系列可能的输出项，即候选项集合(candidate set)；然后，评估器根据CON所提供的制约条件等级体系排列筛选出最优的候选项，即最终的输出项。

较之传统的基于规则的音系分析方法，优选论在语言类型的问题上表现出了强大的解释力，但其代价是计算的复杂度增加了，难以进行人工计算。有人认为，生成器所具有的自由分析原则(freedom of analysis)会产生无限多的结构，而计算无限数量的候选项需要无限的时间(Kager 1999:25)，这必然会导致不可计算，故优选论不能成为一个合理的言语产出或感知模型。Idsardi(2006a)结合了计算复杂性理论，试图论证经典优选论的生成问题属于NP难解问题。该篇文章引发了对优选论计算性问题的关注和热烈讨论。以下分别介绍Idsardi对优选论不可解的证明以及来自各方支持优选论的论点。

2.优选论计算不可解的论证

Garey and Johnson (1979)提出了证明一个新问题是NP难解的标准方法——若某个已证的NPC问题Π′能被归约为一个新问题Π(能采用新问题的条件和语汇来描述已知的NPC问题)，那么新问题Π便具有在多项式时间内不可解的特性，即NP难解。基于这一方法，Idsardi(2006a)试图将一个已被证明是NPC问题的有向汉密尔顿路径(directed Hamiltonian path)问题归约为优选论的生成问题，以此证明后者是NP难解。

汉密尔顿路径指一个图中每个顶点只经过一次且不重复的路径，即一个有向图G=(V, A)中V

Idsardi选取优选论里常见的制约条件，并采用偶值评估(binary evaluation)方法[注]偶值评估指对于一个制约条件，每个候选项只能满足或违反一次的评估方式，与梯级(gradient)评估方式相对。，将优选论语法建构成汉密尔顿路径的模式。首先，音位总藏(inventory)中的n个元素I={a,b,c,…}可看成是图G的各个顶点v1,v2,…,vn，于是可以构建一个由n个元素构成的输入项/abc…/。然后，作者采用四类制约条件对所有的候选项进行逐层筛选。

第一层为形如*x(xC-I)的制约条件，即某种语言中不允许出现总藏I以外的音位[注]例如，英语里不允许出现闪音或前高元音。，它将原本数量无限的候选项集合缩减为同样数量无限的音位集合I*。第二层制约条件为反删音的MAX和反增音的DEP，共同确保候选项和输入项的语符列具有相同的长度(元素数目)，此时的候选项集合缩减为有限集In，包含nn个候选项。第三层为形如*α2={*a2, *b2, *c2…}禁止并联(self-conjoined)的制约条件，即禁止同一域(domain，此处指同一词)内出现两次相同的音段或音段类型，此时的候选项集合缩减为没有重复音段的长度为n的语符串，是集合I的全排列，包含n!个候选项，这相当于图G中到达各顶点V的所有可能的路径数目，而不论路径中的各边是否属于边集A。第四层为禁止出现特定元素序列的制约条件*αβ(α=vi，β=vj，且vivjA)，相当于禁止出现不属于边集A的边，即确保所选的路径在A内。这一层级还可加入制约条件MPARSE。

这样，Idsardi便将汉密尔顿路径问题归约为优选论的生成问题，从而证明后者难解。他认为，该转化过程显然是多项式时间的：输入有n个元素，是线性时间(linear-time)的；所需的制约条件等级体系最多含有n2+n+3个制约条件(n2个禁止特定序列的制约条件，n个禁止并联的制约条件，以及MAX、DEP和MPARSE这三个制约条件)，因而最多是二次项时间(quadratic-time)的。

除Idsardi(2006a)之外，Eisner(1997)和Wareham(1998)等人也对优选论计算不可解的特性进行了论证。但与此相对，Eisner(2000)论述了基于规则的推导系统在计算上是可解的，属于多项式时间算法，即P类问题, 可以容易地由有限状态自动机(finite state automata)进行处理(Idsardi 2006a；Heins, et al 2009; Vaux and Nevins 2008:6)。

3.争论的焦点

对于Idsardi(2006a)的论证，Kornai(2006a，b)和Heinz, et al(2009)等人从不同角度进行了反驳。争论的焦点主要集中在几个方面：优选论生成问题的表征形式与计算复杂性，问题的规模大小，论证复杂性的方法，等等。

(1)语法的表征形式与计算复杂性

Heins, et al(2009)详细论述了优选论语法中能获得有效计算性的表征形式，并阐述了产生优选论复杂性的根本原因，最终表明，用计算复杂性来推翻优选论理论的观点是错误的。由于一个问题的输入可能有多种表达方式，标准的分析方法需要采用统一的形式。若输入涉及多个参数，那么只有可变参数能作为输入项的一部分；已知的参数不构成输入项，其规模与复杂度无关。因此，语法的表征形式在判断语法的计算复杂度时具有重要作用，复杂性在一定程度上取决于表征的规模。

Heins等认为，Eisner(1997)，Idsardi(2006)和Wareham(1998)等人有关优选论难解的结论都是基于以下两点才得以成立的：首先，制约条件集合(CON)预先不固定，相反却构成了输入的一部分，这与通常所定义的优选论是相悖的。其次，他们将优选论语法表征为制约条件列表，这是一种非常特殊的表征形式。对此，Heins指出，倘若CON是确定的，生成过程中便没有可变参数，那么计算则是有效的。即便是在CON没有确定的情况下，优选论计算难解结论也只是建立在将语法表征为制约条件列的基础之上。若采用其他的表征方式，难解结论便不能成立。

优选论的生成问题指的是为一个输入项通过给定的制约条件等级排列筛选出最优项的问题。它涉及三个参数：输入项string、制约条件集合(CON)和制约条件的等级排列Ranking。根据三个参数是否已知，Heins等把优选论的生成问题划分成三类：对于以x为输入的语法GCON，R(x)，已知CON、R且变量为x的属于简单(simple)生成问题；若已知CON，变量为R和x，则属于准全称(quasi-universal)生成问题；若三个参数CON、R和x均为变量，则构成全称(universal)生成问题。一般情况下，优选论中的CON是固定且具有普遍性的，因此属于前两类生成问题之一；如果CON是后天习得且因具体语言而异，那么这种开放型的优选论则与第三类问题相关。Heins等认为，若制约条件均为有限状态，则前两类生成问题可解；若将CON表征为EVAL，则第三类问题亦可解。Eisner，Idsardi和Wareham三人由于采用自创的语法表征形式，使问题变得不可解。具体来说，简单问题中，CON和R均已知，唯有底层形式任意，此时计算量在底层形式长度的线性时间内可以完成。Ellison(1994)试图构建一个由全排列R表征CON的有限状态机来为此提供证据。他的有限状态机同时包含了CON和R。

准全称问题是标准的优选论生成问题，CON已知，但底层形式和制约条件的排列均是变量。这类问题在线性时间内亦可解。Riggle(2004)为此提供了证据，他将CON表征为与R无关的有限状态机。这一机制可看成是“变相评估器(meta-EVAL)”，它可以使任意底层和任意排列的筛选过程在线性时间内完成(因为只要给出排列，它就能产生特定的评估器)。通过CON的因子排列得到的语法均可生成最优项，不需重新计算评估器。在Idsardi(2006a)的分析中，图中的每个点代表一个音位，点的数目决定音位数，这样，制约条件的数目便不能确定，于是成为问题的变量，故难解。Wareham(1998)也是将语法建构成任意规模的图，将制约条件表征为有限状态自动机，制约条件交错成图。他的做法自然需要数量无限的制约条件，因此图能达到任意大。可见，Eisner(1997)，Idsardi(2006a)和Wareham(1998)等人所讨论的问题都不属于标准的优选论生成问题，而属于全称问题。

在全称问题中，三个参数都没有预先给定。为优选论进行编程以及认为CON是开放的就涉及此类问题。此时，计算复杂度(部分)取决于语法的表征形式。这里涉及两种表征方式：一种是Idsardi和Eisner的将语法表征为若干个制约条件的排列。这样的表征非常简洁，便于筛选，但其计算的步数取决于制约条件集合加上输入的规模，必须交叉排列大量有限状态机，这一过程具有激增特性，因此造成难解。换言之，这种制约条件列表的表征方式难以预测评估器的规模，故难以预测计算步数。另一种表征方式是Ellison(1994)的将语法表征为一个单独的有限状态转换器，类似于Riggle的变相评估器。它将众多制约条件置于一个转换器或评估函数中，这一操作相当于对制约条件进行排列组合，表征的过程实际上已经分担了表征后的工作。这种评估器的表征方式虽然不简洁，但它更能预测实际的计算步数，其计算步数取决于语法的规模。可见，Eisner和Idsardi不可解的结论只适用于全称生成问题，且取决于语法的表征形式。他们的结论并不能说明优选论本身具有计算难解的性质，而是反映了将制约条件列的表征转化为评估器表征的困难。这两种表征形式是同一个函数的不同表达模式，我们不能说哪一种表征方式是“正确”的，只能说对于某种具体情况来说，哪一个方式更有效。那么对于优选论语法的习得而言，若学习者直接处理任意排列的制约条件，则评估器的计算量极大，即难解。若学习者直接处理评估器，则不存在难解问题。优选论难解的根源在于对制约条件进行结合的过程，按照Eisner等人的表征方法，即使制约条件呈有限状态，全称问题也是难解的。为保证优选论计算的有效性，Idsardi和Wareham分别提出对GEN和CON进行限制。Heins等则指出，应坚持经典优选论，预先给定制约条件，或在不给定制约条件的情况下，采用类似评估器的表征形式来表征学习理论的算法，避免学习者用众多制约条件来计算评估器，这样便能避免优选论的计算不可解性。

(2)问题的规模与计算复杂性

对于Idsardi(2006a)的论证，Kornai(2006a)针对其中第三层制约条件提出质疑。他指出，音系中只存在着少数无界(unbounded)域，而制约条件*α2都是应用于有界(bounded)域的，如Grassman定律和Lyman定律。即便是对于音步这样的无界结构来说，它所受的异化效果(禁止并联)也只能作用于数量有限且为数很少的总藏当中，如特征几何(feature geometry)的节点，而特征几何体系本身也无法包含无限多的元素。既然不存在任意规模的总藏，就无法建构任意规模的有向图，那么复杂性的讨论就不存在太大的意义了。优选论涉及的是有限规模的确定型问题，并非无限规模的问题。

Idsardi(2006b)又对Kornai(2006a)提出的问题进行反驳。他将禁止并联的制约条件表述为*[…α…α…d]，并以Ito and Mester(2003)的分析作为证据(包括Grassman定律和Lyman定律)，举例论证了不能并联的元素α不可能是Kornai(2006a)所说的特征几何节点，而是Idsardi(2006a)所说的音位。同时，这类制约条件的适用域应包括韵律词、语素、词干、音系短语等无界域。另外，虽然语言中的音段总藏是有限的，但这不代表音段数目就少。例如，有学者已经发现存在着音段数目达到100的语言，而100！的排列是难以计算的。随后，Kornai(2006b)又针对Idsardi(2006b)的论点进行回应，总结了决定问题规模的三个因素分别为n，p，2c。其中，n表示制约条件适用域的规模，p为总藏的规模，c为禁止并联的制约条件的数目。Kornai指出，语言中存在着这样一个趋势：若音位总藏的数目p大，那么词长会减小；若n值较小，那么即使p值很大，汉密尔顿路径的归约也只取决于n。Kornai将Idsardi的思路概括为：由于优选论不具备小总藏和较少的并行异化过程这两个条件，于是造成其计算不可解，因此，优选论不足以描述自然语言的音系特点。对于最后一点，Kornai认为，到目前为止，没有证据也不可能有证据表明机器运算这些任务是指数时间的，这是因为自然语言的音系是建立在严格有限且总藏很小的组合成分(特征和音位)之上的。假设有36个偶值特征，在保持每个特征都对立的情况下，语言中应当出现690亿(236)个音位，但即便这一数值很大，严格说它也是有限的。对于Idsardi (2006a)所提及的某个有100个音位的语言，100！也并不是不可计算的。我们还发现，实际语言中的音位总藏数量远远小于理论的可能值。另外，语言中大量的同化和异化过程并不是并行的，这两个现象一直没有得到满意的解释。但有一点是确定的：实际的语法分析中从未发现有任何难以计算的音系理论，换言之，在自然语言中判定某个语符列是否合乎语法这一判定问题(decision problem)属于容易问题。虽然习得所需的机制这一问题有待解决，但可以肯定的是，生成机制和识别机制是可计算的。事实上，Kager(1999:26)对于优选论生成问题的规模与可计算的关系早有论述。他认为，候选项的数量无限并不意味着逻辑上的不可解。例如，方程式3n2-3=45虽然存在着无限多可能的候选项(如所有整数)，但若按照某种算法进行计算，则会得到唯一解。因此，判定优选论在计算上是否可解并不是基于对候选项数目是否有限的观察，因为即便是具有有限的候选项数目也不能保证问题可解。

(3)证明计算复杂性的方法

Kornai(2006b)认为，Idsardi的结论显示的是计算复杂度理论的局限，而非优选论的理论缺陷，优选论语法的评估过程并不是NP难解问题。这是因为，应用经典复杂度理论的必要条件是无限的数据，Idsardi所采用的渐进分析法只适用于任意大规模的数据。音系中的单位和制约条件的数目都是有限的，不符合渐进分析的应用条件。

据此，Kornai(2009)基于前人的研究结果，提出采用柯氏复杂性(Kolmogorov complexity)来进行分析，因为它可以用来解决有限集的问题。柯氏复杂度指能输出某个字符串的最短的计算机程序的长度，复杂度取决于程序的长度。一个有限语法的复杂度与该语法生成的集合是否有限并不相关，而应基于该语法系统的规模。语法系统的规模取决于它的两个构件的大小：词库(lexicon)和型式(pattern)。前者包括词根和词干的音系内容以及变音符等不可缩减的信息，后者指规则或制约条件，即通常所说的语法。二者处在同一个自动机内，互相制约以获得平衡，若词库增大，则型式减少，反之亦然。它们在语言习得中充当着不同的角色：对于词库，习得者须从头到尾进行记忆；对于规则或制约条件，习得者可参考天生具有的普遍规则。型式在各种语言中重复应用，这使得它们的复杂性分由各种语言来共同承担。换言之，由于存在着普遍语法，每个语言只需承担一小部分的复杂度。于是，Kornai从计算机存储空间的角度对词库和型式所需的最小容量进行估算。结果发现，一部二至三万词的词典(含语素、句法和语义信息)仅占据1兆字节(mb)的空间。即使词库包含语音细节和语义信息，它也不超过4mb，其中音系和语素信息所占的空间不到10%。对于型式，目前最大且最为系统而精简的语法——帕尼尼(Pānini)的梵语语法所包含的3，959条规则约占50kb(千字节)，即5万字节的空间，略大于其词库所占空间的1/3。而在现代拼写法所支持的上百种语言中，只有少数语言的语法所占的空间超过其词库空间的10%。尽管型式的容量比词库小，但由于词库中的信息不可再压缩，每个理论都需要进行相同的处理，因此在比较各种理论时，型式的复杂性更为重要。

那么，如何度量型式的复杂度？优选论包含大量的普遍语法(UG)信息，它预先指定所有制约条件的模式，通过调整制约条件的参数并给定其排列来产生任何具体语法。例如，通过确定特征及其适用域来调整一个同化或异化制约条件的参数，这一过程只需几十位(bits)数。确定N个制约条件的排列需要Nlog(N)位数。显然，优选论能有效地对语法进行压缩：定义几十个制约条件及其排列不超过1kb，而这一系统使自动机产生数以万计的状态并通过千百种转换来执行。生成语法聚焦于UG，这是因为唯有包含高度普遍性内容的理论能够解释为何种语言习得是容易且快速的。从柯氏复杂度的角度来看，UG可以有效地对数据进行压缩，是数据压缩的中心机制。Kornai总结，Idsardi(2006a)所提出的优选论由于其计算时间呈指数级而应被推翻的论断是站不住脚的，因为音系不具有任意大规模的成分。但这并不是说，优选论在不断引入各种复杂的分析技术[包括层级结构(stratal organization)、和应(sympathy)理论、候选项链理论(candidate chains)等]之后，还能处于计算可解的状态。一般来说，人们在碰到实际数据的计算困难后才去探求指数增长问题，但Idsardi等人则是通过探讨人造问题来创造困难。目前没有证据能证明优选论的计算难解。Kornai采用柯氏复杂度的方法，估算出生成语法的词库仅占4mb，其中纯粹的形态或音系信息不超过400kb，所占据的存储空间非常小。

三、评 论

由以上分析可以看出，对Idsardi观点的反驳主要是从几方面展开的：Kornai(2006a)认为Idsardi的观点是基于对制约条件集合和候选项所持的不合理的设定；Heinz, et al(2009)认为，优选论模型中的一些非极端的生成问题并没有表现出计算不可解的性质。前者从优选论语法的表征入手，后者从空间复杂度的角度进行分析。在此之前，支持优选论的更为常见的论据包括：优选论的理论框架是纯粹基于表征的，是描述和解释语言能力的模型，并不用于解释语言运用的具体情况，如Kager(1999)。优选论的创始人Prince和Smolensky (1993/2004)也从判断语法优劣的标准展开论述。

1.如何评判好的语法

语法是对句子结构进行描述的函数。早在20世纪50年代，Chomsky就提出，评判一部语法好坏的标准在于它的解释充分性和描述充分性。根据这一论断，Prince和Smolensky (1993/2004:233)认为，不应提出这一基本标准之外的诸如“计算可行性”这样任意的条件来衡量语法的好坏。在满足描述力和解释力的前提下，研究者可以对语法的形式进行创新。

大多数形式语法理论都区分语言能力(competence)和语言运用(performance)，尤其是生成语法理论。因此，如果一部语法能够解释自然语言中可观察到的系统性以及说话人的语法判断(语言能力)，那么这便是一部具有充分性/好的语法。相对而言，解释人脑中语言知识的具体执行过程(语言运用)并不是形式语法理论所追求的目标，而是语言学各分支如心理语言学、神经语言学和计算语言学等所关注的课题。总之，语法理论模型不等同于其具体的计算执行过程(Kager 1999: 26)。

2.计算复杂性与人脑对自然语言的处理能力

将复杂度理论用于研究自然语言的语法已经有20多年的历史，但学界仍然存在着认为各种形式主义在计算上不可解的不少论点。例如，Barton(1986)指出，双层音系-形态模型(two-level phonology and morphology，简称TWOL)在计算上难解，而人们在执行音系和形态分析时仅在有限时间内便可完成，可见TWOL不能描述人类在音系和形态上的能力。然而，这一模型20多年来一直保持着领先地位，并未受到难解问题的影响。同样，Idsardi(2006a, b)指出，优选论的计算不可解，但人们执行语言能力的过程只是在有限时间内完成，故优选论不能描述人类的语言能力。Barton和Idsardi采用了相同的论证思路：首先将计算模型与某个语言现象的机制相结合；然后将此机制用于归约NP难解问题，以证明该音系理论属于难解问题；最后说明计算难解显然与人类的语言处理能力相矛盾。这些理论所表现出的计算复杂性要远在人们处理能力之上(人类处理能力似乎呈线性或亚线性)，但它们都能以有效方式被人脑当中的语法分析器(parsers)成功地得以执行(Prince和Smonlensky 2004: 233)。

事实上，Barton本人也预知了自己分析中存在的问题：计算理论只针对任意规模的句子和词库进行应用，而自然语言只处理有限规模的问题，那么复杂性理论是否有意义？复杂度理论所确定的逻辑运算量与心理学实验所测量的人们执行任务时所感到的困难程度之间的关系究竟如何？这些问题目前尚不明确(Kornai 2006b)。

3.实际的计算操作结果

对优选论不可计算最有力的反驳来自已经获得的计算操作情况。首先，从筛选机制上看，评估器对无限数量的候选项是按组进行淘汰的，而非逐一排除。Karttunen(1998)的研究结果也表明，为输入项选择最优输出项的计算过程完全可以在有限状态演算中完成，并受到违反制约条件的次数的限定；这种限定并不会引起有限状态系统在实际计算过程中的困难，因为我们仅需考虑其中一小部分制约条件被违反的情况(Kager 1999: 26-27)。另外，计算有效性与具体的算法设计紧密相关。目前所设计的用于计算最优表层形式的模型包括Ellison(1994)、Eisner(1997)、Albro(1998, 2005)的权重有限状态机(weighted finite state machines)、Tesar(1996)的上下文自由语法(context-free grammars)、Karttunen(1998)的有限状态转换器(initiate-state transducers)等等。研究者仍在不断设计新的算法，计算性的结果也会随之发生改变(Prince和Smonlensky 1993/2004: 233; Albro 2005: 17-19)。

四、结 语

在计算机诞生之初，Chomsky就试图用高度抽象的形式语言来描写自然语言，并将其应用于计算机程序语言当中。这就表明，他尝试将自然语言和计算机语言统一于同一个形式框架之内。“形式语法的研究直接为语言的计算机处理准备了条件”(陆极致1990:183)。 “以计算的过程作为大脑处理语言的过程的观点在音系学家中已经得到普遍认同”(赵忠德，鲜明 2009)。国内有关优选论计算性的争论仍在继续，厘清该问题可以使我们更加深入地了解优选论，探讨其发展方向，同时有助于我们进一步认识语法可学性、二语习得的本质等问题(马秋武2003, 2008:265, 79)。

研究计算性问题可以使我们能更加深入地了解优选论，探讨它的发展方向。优选论计算性的问题仍在探讨之中，期望本文对该问题的梳理能为相关理论研究做出一定的贡献。