試析優(yōu)選論的計(jì)算復(fù)雜性問題

馬秋武, 吳力菡

(1.復(fù)旦大學(xué) 外文學(xué)院， 上海 200433； 2.廣西民族大學(xué) 外國語學(xué)院， 南寧 530006)

優(yōu)選論(Optimality Theory，簡(jiǎn)稱OT)自20世紀(jì)90年代誕生開始就引起國內(nèi)外研究者的廣泛關(guān)注。在保留其核心理論框架的前提下，優(yōu)選論經(jīng)歷了多次技術(shù)上的調(diào)整以解釋更多的音系問題，并被拓展到音系以外的其他領(lǐng)域，如句法、語用等，可見其理論思想具有較強(qiáng)的活力，其操作模式具有開放性，因而至今仍然是語言學(xué)界的主流理論之一。但與此同時(shí)，20多年來，圍繞優(yōu)選論產(chǎn)生的各種質(zhì)疑和爭(zhēng)論也從未間斷過，優(yōu)選論在理論和應(yīng)用上一直面臨著不少挑戰(zhàn)。其中，優(yōu)選論所具有的獨(dú)特的操作模式和計(jì)算方法引發(fā)了近年來在計(jì)算音系學(xué)領(lǐng)域中對(duì)于優(yōu)選論計(jì)算復(fù)雜性(computational complexity)問題的熱議。所涉及的問題包括：優(yōu)選論中的生成問題是否屬于NP難解問題？學(xué)習(xí)者如何習(xí)得計(jì)算量龐大的制約條件等級(jí)排列以及底層形式？等等。對(duì)此，Eisner(1997)和Isardi(2006a, b)等人試圖論證優(yōu)選論在計(jì)算上是不可解的(intractable)從而否定優(yōu)選論的運(yùn)行模式。Kornai(2006a, b)，Tesar(1995)，Heinz, et al(2009)，Riggle(2009)，Kager(1999)，Prince and Smolensky(1993/2004)等人則從不同角度對(duì)之進(jìn)行反駁，支持優(yōu)選論。本文首先介紹有關(guān)計(jì)算復(fù)雜性的相關(guān)概念，然后概述來自雙方的論點(diǎn)，進(jìn)而對(duì)優(yōu)選論的其他相關(guān)問題進(jìn)行總結(jié)。

一、有關(guān)計(jì)算性的相關(guān)概念

早在20世紀(jì)50年代末，Chomsky便將數(shù)學(xué)思想引入到語言學(xué)研究當(dāng)中，將二者結(jié)合起來，形成一種形式語言學(xué)理論。這種形式語法具有算法(algorithms)的特點(diǎn)。換言之，語法作為一種生成句子的裝置，很像數(shù)學(xué)中的“算法”過程(陸極致1990:171, 182-183)。

所謂算法指的是一系列解決問題的清晰指令，是一個(gè)有限規(guī)則的有序集合，對(duì)于某類問題的初始輸入，它能在有限時(shí)間內(nèi)機(jī)械地逐步計(jì)算，在有限步驟后計(jì)算終止，獲得一個(gè)輸出結(jié)果。一個(gè)問題可以有多種算法。一個(gè)算法的優(yōu)劣可以用時(shí)間復(fù)雜度(time-complexity)和空間復(fù)雜度(space-complexity)來衡量，分別表示完成計(jì)算過程所需的總步數(shù)以及所用存貯的單元數(shù)(Mitkov 2003:178; Linz 2001:343-344; 堵丁柱等 2002:17; 趙瑞清、孫宗智 1989: 54-57; 張澤增 1989:4)。

時(shí)間復(fù)雜度關(guān)注的是當(dāng)某個(gè)問題的規(guī)模擴(kuò)大后，程序運(yùn)行所需的時(shí)間增長(zhǎng)得有多快。這里需要區(qū)分多項(xiàng)式(polynomial)時(shí)間算法和指數(shù)(exponential)時(shí)間算法。形如n2的多項(xiàng)式中，表示問題規(guī)模或大小(size)的參數(shù)n在底數(shù)位置；形如2n的指數(shù)時(shí)間算法中，n在指數(shù)位置，隨著n的變大，它所需的計(jì)算時(shí)間以爆炸性的速率迅速增加。例如，在一臺(tái)每秒做1億次運(yùn)算的計(jì)算機(jī)上，對(duì)于時(shí)間復(fù)雜度分別是n3和3n的算法來說，當(dāng)n達(dá)到60時(shí)，它們所需的計(jì)算時(shí)間分別為2.16×10-3秒和1.3×1011世紀(jì)。顯然，當(dāng)n較大時(shí)，后者所需的時(shí)間是計(jì)算機(jī)無法承受的。

所謂問題，指的是從輸入映射到其結(jié)果(即輸出)的函數(shù)。設(shè)f為多項(xiàng)式函數(shù)，n為輸入的長(zhǎng)度，當(dāng)且僅當(dāng)該問題存在著能在f(n)步之內(nèi)完成該函數(shù)的圖靈機(jī)(Turing machine)時(shí)，這一問題便“在多項(xiàng)式時(shí)間內(nèi)可計(jì)算”(Heins, et al 2009)。多項(xiàng)式時(shí)間算法(或稱有效果算法)被認(rèn)為是好的算法，計(jì)算機(jī)可以執(zhí)行。有好的算法的問題是易解(tractable)的，屬于P類問題，即在確定型圖靈機(jī)上有多項(xiàng)式時(shí)間算法(實(shí)際可用的算法)。若一個(gè)問題找不到或尚未找到有效算法，則稱為難解的(intractable)，屬于“非確定多項(xiàng)式算法(non-deterministic polynomial-time algorithm)”，簡(jiǎn)稱為NP類問題。如果所有NP問題都能規(guī)約(reduce)到某一種問題，那么這種問題稱為NP難解(NP-hard)問題(張澤增 1989:1-38; 張立昂 1996:227-228)。

二、優(yōu)選論的計(jì)算復(fù)雜性問題

1.經(jīng)典優(yōu)選論的運(yùn)算模式

優(yōu)選論把語言形式看成是制約條件交互作用的結(jié)果。其語法體系包括三大部分：生成器(Generator)、制約條件集合(The Constraint Set)和評(píng)估器(Evaluator)，通常分別簡(jiǎn)寫為GEN，CON，EVAL。它的運(yùn)算模式如下：生成器為某個(gè)輸入項(xiàng)生成一系列可能的輸出項(xiàng)，即候選項(xiàng)集合(candidate set)；然后，評(píng)估器根據(jù)CON所提供的制約條件等級(jí)體系排列篩選出最優(yōu)的候選項(xiàng)，即最終的輸出項(xiàng)。

較之傳統(tǒng)的基于規(guī)則的音系分析方法，優(yōu)選論在語言類型的問題上表現(xiàn)出了強(qiáng)大的解釋力，但其代價(jià)是計(jì)算的復(fù)雜度增加了，難以進(jìn)行人工計(jì)算。有人認(rèn)為，生成器所具有的自由分析原則(freedom of analysis)會(huì)產(chǎn)生無限多的結(jié)構(gòu)，而計(jì)算無限數(shù)量的候選項(xiàng)需要無限的時(shí)間(Kager 1999:25)，這必然會(huì)導(dǎo)致不可計(jì)算，故優(yōu)選論不能成為一個(gè)合理的言語產(chǎn)出或感知模型。Idsardi(2006a)結(jié)合了計(jì)算復(fù)雜性理論，試圖論證經(jīng)典優(yōu)選論的生成問題屬于NP難解問題。該篇文章引發(fā)了對(duì)優(yōu)選論計(jì)算性問題的關(guān)注和熱烈討論。以下分別介紹Idsardi對(duì)優(yōu)選論不可解的證明以及來自各方支持優(yōu)選論的論點(diǎn)。

2.優(yōu)選論計(jì)算不可解的論證

Garey and Johnson (1979)提出了證明一個(gè)新問題是NP難解的標(biāo)準(zhǔn)方法——若某個(gè)已證的NPC問題Π′能被歸約為一個(gè)新問題Π(能采用新問題的條件和語匯來描述已知的NPC問題)，那么新問題Π便具有在多項(xiàng)式時(shí)間內(nèi)不可解的特性，即NP難解。基于這一方法，Idsardi(2006a)試圖將一個(gè)已被證明是NPC問題的有向漢密爾頓路徑(directed Hamiltonian path)問題歸約為優(yōu)選論的生成問題，以此證明后者是NP難解。

漢密爾頓路徑指一個(gè)圖中每個(gè)頂點(diǎn)只經(jīng)過一次且不重復(fù)的路徑，即一個(gè)有向圖G=(V, A)中V

Idsardi選取優(yōu)選論里常見的制約條件，并采用偶值評(píng)估(binary evaluation)方法[注]偶值評(píng)估指對(duì)于一個(gè)制約條件，每個(gè)候選項(xiàng)只能滿足或違反一次的評(píng)估方式，與梯級(jí)(gradient)評(píng)估方式相對(duì)。，將優(yōu)選論語法建構(gòu)成漢密爾頓路徑的模式。首先，音位總藏(inventory)中的n個(gè)元素I={a,b,c,…}可看成是圖G的各個(gè)頂點(diǎn)v1,v2,…,vn，于是可以構(gòu)建一個(gè)由n個(gè)元素構(gòu)成的輸入項(xiàng)/abc…/。然后，作者采用四類制約條件對(duì)所有的候選項(xiàng)進(jìn)行逐層篩選。

第一層為形如*x(xC-I)的制約條件，即某種語言中不允許出現(xiàn)總藏I以外的音位[注]例如，英語里不允許出現(xiàn)閃音或前高元音。，它將原本數(shù)量無限的候選項(xiàng)集合縮減為同樣數(shù)量無限的音位集合I*。第二層制約條件為反刪音的MAX和反增音的DEP，共同確保候選項(xiàng)和輸入項(xiàng)的語符列具有相同的長(zhǎng)度(元素?cái)?shù)目)，此時(shí)的候選項(xiàng)集合縮減為有限集In，包含nn個(gè)候選項(xiàng)。第三層為形如*α2={*a2, *b2, *c2…}禁止并聯(lián)(self-conjoined)的制約條件，即禁止同一域(domain，此處指同一詞)內(nèi)出現(xiàn)兩次相同的音段或音段類型，此時(shí)的候選項(xiàng)集合縮減為沒有重復(fù)音段的長(zhǎng)度為n的語符串，是集合I的全排列，包含n!個(gè)候選項(xiàng)，這相當(dāng)于圖G中到達(dá)各頂點(diǎn)V的所有可能的路徑數(shù)目，而不論路徑中的各邊是否屬于邊集A。第四層為禁止出現(xiàn)特定元素序列的制約條件*αβ(α=vi，β=vj，且vivjA)，相當(dāng)于禁止出現(xiàn)不屬于邊集A的邊，即確保所選的路徑在A內(nèi)。這一層級(jí)還可加入制約條件MPARSE。

這樣，Idsardi便將漢密爾頓路徑問題歸約為優(yōu)選論的生成問題，從而證明后者難解。他認(rèn)為，該轉(zhuǎn)化過程顯然是多項(xiàng)式時(shí)間的：輸入有n個(gè)元素，是線性時(shí)間(linear-time)的；所需的制約條件等級(jí)體系最多含有n2+n+3個(gè)制約條件(n2個(gè)禁止特定序列的制約條件，n個(gè)禁止并聯(lián)的制約條件，以及MAX、DEP和MPARSE這三個(gè)制約條件)，因而最多是二次項(xiàng)時(shí)間(quadratic-time)的。

除Idsardi(2006a)之外，Eisner(1997)和Wareham(1998)等人也對(duì)優(yōu)選論計(jì)算不可解的特性進(jìn)行了論證。但與此相對(duì)，Eisner(2000)論述了基于規(guī)則的推導(dǎo)系統(tǒng)在計(jì)算上是可解的，屬于多項(xiàng)式時(shí)間算法，即P類問題, 可以容易地由有限狀態(tài)自動(dòng)機(jī)(finite state automata)進(jìn)行處理(Idsardi 2006a；Heins, et al 2009; Vaux and Nevins 2008:6)。

3.爭(zhēng)論的焦點(diǎn)

對(duì)于Idsardi(2006a)的論證，Kornai(2006a，b)和Heinz, et al(2009)等人從不同角度進(jìn)行了反駁。爭(zhēng)論的焦點(diǎn)主要集中在幾個(gè)方面：優(yōu)選論生成問題的表征形式與計(jì)算復(fù)雜性，問題的規(guī)模大小，論證復(fù)雜性的方法，等等。

(1)語法的表征形式與計(jì)算復(fù)雜性

Heins, et al(2009)詳細(xì)論述了優(yōu)選論語法中能獲得有效計(jì)算性的表征形式，并闡述了產(chǎn)生優(yōu)選論復(fù)雜性的根本原因，最終表明，用計(jì)算復(fù)雜性來推翻優(yōu)選論理論的觀點(diǎn)是錯(cuò)誤的。由于一個(gè)問題的輸入可能有多種表達(dá)方式，標(biāo)準(zhǔn)的分析方法需要采用統(tǒng)一的形式。若輸入涉及多個(gè)參數(shù)，那么只有可變參數(shù)能作為輸入項(xiàng)的一部分；已知的參數(shù)不構(gòu)成輸入項(xiàng)，其規(guī)模與復(fù)雜度無關(guān)。因此，語法的表征形式在判斷語法的計(jì)算復(fù)雜度時(shí)具有重要作用，復(fù)雜性在一定程度上取決于表征的規(guī)模。

Heins等認(rèn)為，Eisner(1997)，Idsardi(2006)和Wareham(1998)等人有關(guān)優(yōu)選論難解的結(jié)論都是基于以下兩點(diǎn)才得以成立的：首先，制約條件集合(CON)預(yù)先不固定，相反卻構(gòu)成了輸入的一部分，這與通常所定義的優(yōu)選論是相悖的。其次，他們將優(yōu)選論語法表征為制約條件列表，這是一種非常特殊的表征形式。對(duì)此，Heins指出，倘若CON是確定的，生成過程中便沒有可變參數(shù)，那么計(jì)算則是有效的。即便是在CON沒有確定的情況下，優(yōu)選論計(jì)算難解結(jié)論也只是建立在將語法表征為制約條件列的基礎(chǔ)之上。若采用其他的表征方式，難解結(jié)論便不能成立。

優(yōu)選論的生成問題指的是為一個(gè)輸入項(xiàng)通過給定的制約條件等級(jí)排列篩選出最優(yōu)項(xiàng)的問題。它涉及三個(gè)參數(shù)：輸入項(xiàng)string、制約條件集合(CON)和制約條件的等級(jí)排列Ranking。根據(jù)三個(gè)參數(shù)是否已知，Heins等把優(yōu)選論的生成問題劃分成三類：對(duì)于以x為輸入的語法GCON，R(x)，已知CON、R且變量為x的屬于簡(jiǎn)單(simple)生成問題；若已知CON，變量為R和x，則屬于準(zhǔn)全稱(quasi-universal)生成問題；若三個(gè)參數(shù)CON、R和x均為變量，則構(gòu)成全稱(universal)生成問題。一般情況下，優(yōu)選論中的CON是固定且具有普遍性的，因此屬于前兩類生成問題之一；如果CON是后天習(xí)得且因具體語言而異，那么這種開放型的優(yōu)選論則與第三類問題相關(guān)。Heins等認(rèn)為，若制約條件均為有限狀態(tài)，則前兩類生成問題可解；若將CON表征為EVAL，則第三類問題亦可解。Eisner，Idsardi和Wareham三人由于采用自創(chuàng)的語法表征形式，使問題變得不可解。具體來說，簡(jiǎn)單問題中，CON和R均已知，唯有底層形式任意，此時(shí)計(jì)算量在底層形式長(zhǎng)度的線性時(shí)間內(nèi)可以完成。Ellison(1994)試圖構(gòu)建一個(gè)由全排列R表征CON的有限狀態(tài)機(jī)來為此提供證據(jù)。他的有限狀態(tài)機(jī)同時(shí)包含了CON和R。

準(zhǔn)全稱問題是標(biāo)準(zhǔn)的優(yōu)選論生成問題，CON已知，但底層形式和制約條件的排列均是變量。這類問題在線性時(shí)間內(nèi)亦可解。Riggle(2004)為此提供了證據(jù)，他將CON表征為與R無關(guān)的有限狀態(tài)機(jī)。這一機(jī)制可看成是“變相評(píng)估器(meta-EVAL)”，它可以使任意底層和任意排列的篩選過程在線性時(shí)間內(nèi)完成(因?yàn)橹灰o出排列，它就能產(chǎn)生特定的評(píng)估器)。通過CON的因子排列得到的語法均可生成最優(yōu)項(xiàng)，不需重新計(jì)算評(píng)估器。在Idsardi(2006a)的分析中，圖中的每個(gè)點(diǎn)代表一個(gè)音位，點(diǎn)的數(shù)目決定音位數(shù)，這樣，制約條件的數(shù)目便不能確定，于是成為問題的變量，故難解。Wareham(1998)也是將語法建構(gòu)成任意規(guī)模的圖，將制約條件表征為有限狀態(tài)自動(dòng)機(jī)，制約條件交錯(cuò)成圖。他的做法自然需要數(shù)量無限的制約條件，因此圖能達(dá)到任意大?？梢?，Eisner(1997)，Idsardi(2006a)和Wareham(1998)等人所討論的問題都不屬于標(biāo)準(zhǔn)的優(yōu)選論生成問題，而屬于全稱問題。

在全稱問題中，三個(gè)參數(shù)都沒有預(yù)先給定。為優(yōu)選論進(jìn)行編程以及認(rèn)為CON是開放的就涉及此類問題。此時(shí)，計(jì)算復(fù)雜度(部分)取決于語法的表征形式。這里涉及兩種表征方式：一種是Idsardi和Eisner的將語法表征為若干個(gè)制約條件的排列。這樣的表征非常簡(jiǎn)潔，便于篩選，但其計(jì)算的步數(shù)取決于制約條件集合加上輸入的規(guī)模，必須交叉排列大量有限狀態(tài)機(jī)，這一過程具有激增特性，因此造成難解。換言之，這種制約條件列表的表征方式難以預(yù)測(cè)評(píng)估器的規(guī)模，故難以預(yù)測(cè)計(jì)算步數(shù)。另一種表征方式是Ellison(1994)的將語法表征為一個(gè)單獨(dú)的有限狀態(tài)轉(zhuǎn)換器，類似于Riggle的變相評(píng)估器。它將眾多制約條件置于一個(gè)轉(zhuǎn)換器或評(píng)估函數(shù)中，這一操作相當(dāng)于對(duì)制約條件進(jìn)行排列組合，表征的過程實(shí)際上已經(jīng)分擔(dān)了表征后的工作。這種評(píng)估器的表征方式雖然不簡(jiǎn)潔，但它更能預(yù)測(cè)實(shí)際的計(jì)算步數(shù)，其計(jì)算步數(shù)取決于語法的規(guī)模?？梢?，Eisner和Idsardi不可解的結(jié)論只適用于全稱生成問題，且取決于語法的表征形式。他們的結(jié)論并不能說明優(yōu)選論本身具有計(jì)算難解的性質(zhì)，而是反映了將制約條件列的表征轉(zhuǎn)化為評(píng)估器表征的困難。這兩種表征形式是同一個(gè)函數(shù)的不同表達(dá)模式，我們不能說哪一種表征方式是“正確”的，只能說對(duì)于某種具體情況來說，哪一個(gè)方式更有效。那么對(duì)于優(yōu)選論語法的習(xí)得而言，若學(xué)習(xí)者直接處理任意排列的制約條件，則評(píng)估器的計(jì)算量極大，即難解。若學(xué)習(xí)者直接處理評(píng)估器，則不存在難解問題。優(yōu)選論難解的根源在于對(duì)制約條件進(jìn)行結(jié)合的過程，按照Eisner等人的表征方法，即使制約條件呈有限狀態(tài)，全稱問題也是難解的。為保證優(yōu)選論計(jì)算的有效性，Idsardi和Wareham分別提出對(duì)GEN和CON進(jìn)行限制。Heins等則指出，應(yīng)堅(jiān)持經(jīng)典優(yōu)選論，預(yù)先給定制約條件，或在不給定制約條件的情況下，采用類似評(píng)估器的表征形式來表征學(xué)習(xí)理論的算法，避免學(xué)習(xí)者用眾多制約條件來計(jì)算評(píng)估器，這樣便能避免優(yōu)選論的計(jì)算不可解性。

(2)問題的規(guī)模與計(jì)算復(fù)雜性

對(duì)于Idsardi(2006a)的論證，Kornai(2006a)針對(duì)其中第三層制約條件提出質(zhì)疑。他指出，音系中只存在著少數(shù)無界(unbounded)域，而制約條件*α2都是應(yīng)用于有界(bounded)域的，如Grassman定律和Lyman定律。即便是對(duì)于音步這樣的無界結(jié)構(gòu)來說，它所受的異化效果(禁止并聯(lián))也只能作用于數(shù)量有限且為數(shù)很少的總藏當(dāng)中，如特征幾何(feature geometry)的節(jié)點(diǎn)，而特征幾何體系本身也無法包含無限多的元素。既然不存在任意規(guī)模的總藏，就無法建構(gòu)任意規(guī)模的有向圖，那么復(fù)雜性的討論就不存在太大的意義了。優(yōu)選論涉及的是有限規(guī)模的確定型問題，并非無限規(guī)模的問題。

Idsardi(2006b)又對(duì)Kornai(2006a)提出的問題進(jìn)行反駁。他將禁止并聯(lián)的制約條件表述為*[…α…α…d]，并以Ito and Mester(2003)的分析作為證據(jù)(包括Grassman定律和Lyman定律)，舉例論證了不能并聯(lián)的元素α不可能是Kornai(2006a)所說的特征幾何節(jié)點(diǎn)，而是Idsardi(2006a)所說的音位。同時(shí)，這類制約條件的適用域應(yīng)包括韻律詞、語素、詞干、音系短語等無界域。另外，雖然語言中的音段總藏是有限的，但這不代表音段數(shù)目就少。例如，有學(xué)者已經(jīng)發(fā)現(xiàn)存在著音段數(shù)目達(dá)到100的語言，而100！的排列是難以計(jì)算的。隨后，Kornai(2006b)又針對(duì)Idsardi(2006b)的論點(diǎn)進(jìn)行回應(yīng)，總結(jié)了決定問題規(guī)模的三個(gè)因素分別為n，p，2c。其中，n表示制約條件適用域的規(guī)模，p為總藏的規(guī)模，c為禁止并聯(lián)的制約條件的數(shù)目。Kornai指出，語言中存在著這樣一個(gè)趨勢(shì)：若音位總藏的數(shù)目p大，那么詞長(zhǎng)會(huì)減??；若n值較小，那么即使p值很大，漢密爾頓路徑的歸約也只取決于n。Kornai將Idsardi的思路概括為：由于優(yōu)選論不具備小總藏和較少的并行異化過程這兩個(gè)條件，于是造成其計(jì)算不可解，因此，優(yōu)選論不足以描述自然語言的音系特點(diǎn)。對(duì)于最后一點(diǎn)，Kornai認(rèn)為，到目前為止，沒有證據(jù)也不可能有證據(jù)表明機(jī)器運(yùn)算這些任務(wù)是指數(shù)時(shí)間的，這是因?yàn)樽匀徽Z言的音系是建立在嚴(yán)格有限且總藏很小的組合成分(特征和音位)之上的。假設(shè)有36個(gè)偶值特征，在保持每個(gè)特征都對(duì)立的情況下，語言中應(yīng)當(dāng)出現(xiàn)690億(236)個(gè)音位，但即便這一數(shù)值很大，嚴(yán)格說它也是有限的。對(duì)于Idsardi (2006a)所提及的某個(gè)有100個(gè)音位的語言，100！也并不是不可計(jì)算的。我們還發(fā)現(xiàn)，實(shí)際語言中的音位總藏?cái)?shù)量遠(yuǎn)遠(yuǎn)小于理論的可能值。另外，語言中大量的同化和異化過程并不是并行的，這兩個(gè)現(xiàn)象一直沒有得到滿意的解釋。但有一點(diǎn)是確定的：實(shí)際的語法分析中從未發(fā)現(xiàn)有任何難以計(jì)算的音系理論，換言之，在自然語言中判定某個(gè)語符列是否合乎語法這一判定問題(decision problem)屬于容易問題。雖然習(xí)得所需的機(jī)制這一問題有待解決，但可以肯定的是，生成機(jī)制和識(shí)別機(jī)制是可計(jì)算的。事實(shí)上，Kager(1999:26)對(duì)于優(yōu)選論生成問題的規(guī)模與可計(jì)算的關(guān)系早有論述。他認(rèn)為，候選項(xiàng)的數(shù)量無限并不意味著邏輯上的不可解。例如，方程式3n2-3=45雖然存在著無限多可能的候選項(xiàng)(如所有整數(shù))，但若按照某種算法進(jìn)行計(jì)算，則會(huì)得到唯一解。因此，判定優(yōu)選論在計(jì)算上是否可解并不是基于對(duì)候選項(xiàng)數(shù)目是否有限的觀察，因?yàn)榧幢闶蔷哂杏邢薜暮蜻x項(xiàng)數(shù)目也不能保證問題可解。

(3)證明計(jì)算復(fù)雜性的方法

Kornai(2006b)認(rèn)為，Idsardi的結(jié)論顯示的是計(jì)算復(fù)雜度理論的局限，而非優(yōu)選論的理論缺陷，優(yōu)選論語法的評(píng)估過程并不是NP難解問題。這是因?yàn)?，?yīng)用經(jīng)典復(fù)雜度理論的必要條件是無限的數(shù)據(jù)，Idsardi所采用的漸進(jìn)分析法只適用于任意大規(guī)模的數(shù)據(jù)。音系中的單位和制約條件的數(shù)目都是有限的，不符合漸進(jìn)分析的應(yīng)用條件。

據(jù)此，Kornai(2009)基于前人的研究結(jié)果，提出采用柯氏復(fù)雜性(Kolmogorov complexity)來進(jìn)行分析，因?yàn)樗梢杂脕斫鉀Q有限集的問題?？率蠌?fù)雜度指能輸出某個(gè)字符串的最短的計(jì)算機(jī)程序的長(zhǎng)度，復(fù)雜度取決于程序的長(zhǎng)度。一個(gè)有限語法的復(fù)雜度與該語法生成的集合是否有限并不相關(guān)，而應(yīng)基于該語法系統(tǒng)的規(guī)模。語法系統(tǒng)的規(guī)模取決于它的兩個(gè)構(gòu)件的大?。涸~庫(lexicon)和型式(pattern)。前者包括詞根和詞干的音系內(nèi)容以及變音符等不可縮減的信息，后者指規(guī)則或制約條件，即通常所說的語法。二者處在同一個(gè)自動(dòng)機(jī)內(nèi)，互相制約以獲得平衡，若詞庫增大，則型式減少，反之亦然。它們?cè)谡Z言習(xí)得中充當(dāng)著不同的角色：對(duì)于詞庫，習(xí)得者須從頭到尾進(jìn)行記憶；對(duì)于規(guī)則或制約條件，習(xí)得者可參考天生具有的普遍規(guī)則。型式在各種語言中重復(fù)應(yīng)用，這使得它們的復(fù)雜性分由各種語言來共同承擔(dān)。換言之，由于存在著普遍語法，每個(gè)語言只需承擔(dān)一小部分的復(fù)雜度。于是，Kornai從計(jì)算機(jī)存儲(chǔ)空間的角度對(duì)詞庫和型式所需的最小容量進(jìn)行估算。結(jié)果發(fā)現(xiàn)，一部二至三萬詞的詞典(含語素、句法和語義信息)僅占據(jù)1兆字節(jié)(mb)的空間。即使詞庫包含語音細(xì)節(jié)和語義信息，它也不超過4mb，其中音系和語素信息所占的空間不到10%。對(duì)于型式，目前最大且最為系統(tǒng)而精簡(jiǎn)的語法——帕尼尼(Pānini)的梵語語法所包含的3，959條規(guī)則約占50kb(千字節(jié))，即5萬字節(jié)的空間，略大于其詞庫所占空間的1/3。而在現(xiàn)代拼寫法所支持的上百種語言中，只有少數(shù)語言的語法所占的空間超過其詞庫空間的10%。盡管型式的容量比詞庫小，但由于詞庫中的信息不可再壓縮，每個(gè)理論都需要進(jìn)行相同的處理，因此在比較各種理論時(shí)，型式的復(fù)雜性更為重要。

那么，如何度量型式的復(fù)雜度？?jī)?yōu)選論包含大量的普遍語法(UG)信息，它預(yù)先指定所有制約條件的模式，通過調(diào)整制約條件的參數(shù)并給定其排列來產(chǎn)生任何具體語法。例如，通過確定特征及其適用域來調(diào)整一個(gè)同化或異化制約條件的參數(shù)，這一過程只需幾十位(bits)數(shù)。確定N個(gè)制約條件的排列需要Nlog(N)位數(shù)。顯然，優(yōu)選論能有效地對(duì)語法進(jìn)行壓縮：定義幾十個(gè)制約條件及其排列不超過1kb，而這一系統(tǒng)使自動(dòng)機(jī)產(chǎn)生數(shù)以萬計(jì)的狀態(tài)并通過千百種轉(zhuǎn)換來執(zhí)行。生成語法聚焦于UG，這是因?yàn)槲ㄓ邪叨绕毡樾詢?nèi)容的理論能夠解釋為何種語言習(xí)得是容易且快速的。從柯氏復(fù)雜度的角度來看，UG可以有效地對(duì)數(shù)據(jù)進(jìn)行壓縮，是數(shù)據(jù)壓縮的中心機(jī)制。Kornai總結(jié)，Idsardi(2006a)所提出的優(yōu)選論由于其計(jì)算時(shí)間呈指數(shù)級(jí)而應(yīng)被推翻的論斷是站不住腳的，因?yàn)橐粝挡痪哂腥我獯笠?guī)模的成分。但這并不是說，優(yōu)選論在不斷引入各種復(fù)雜的分析技術(shù)[包括層級(jí)結(jié)構(gòu)(stratal organization)、和應(yīng)(sympathy)理論、候選項(xiàng)鏈理論(candidate chains)等]之后，還能處于計(jì)算可解的狀態(tài)。一般來說，人們?cè)谂龅綄?shí)際數(shù)據(jù)的計(jì)算困難后才去探求指數(shù)增長(zhǎng)問題，但I(xiàn)dsardi等人則是通過探討人造問題來創(chuàng)造困難。目前沒有證據(jù)能證明優(yōu)選論的計(jì)算難解。Kornai采用柯氏復(fù)雜度的方法，估算出生成語法的詞庫僅占4mb，其中純粹的形態(tài)或音系信息不超過400kb，所占據(jù)的存儲(chǔ)空間非常小。

三、評(píng) 論

由以上分析可以看出，對(duì)Idsardi觀點(diǎn)的反駁主要是從幾方面展開的：Kornai(2006a)認(rèn)為Idsardi的觀點(diǎn)是基于對(duì)制約條件集合和候選項(xiàng)所持的不合理的設(shè)定；Heinz, et al(2009)認(rèn)為，優(yōu)選論模型中的一些非極端的生成問題并沒有表現(xiàn)出計(jì)算不可解的性質(zhì)。前者從優(yōu)選論語法的表征入手，后者從空間復(fù)雜度的角度進(jìn)行分析。在此之前，支持優(yōu)選論的更為常見的論據(jù)包括：優(yōu)選論的理論框架是純粹基于表征的，是描述和解釋語言能力的模型，并不用于解釋語言運(yùn)用的具體情況，如Kager(1999)。優(yōu)選論的創(chuàng)始人Prince和Smolensky (1993/2004)也從判斷語法優(yōu)劣的標(biāo)準(zhǔn)展開論述。

1.如何評(píng)判好的語法

語法是對(duì)句子結(jié)構(gòu)進(jìn)行描述的函數(shù)。早在20世紀(jì)50年代，Chomsky就提出，評(píng)判一部語法好壞的標(biāo)準(zhǔn)在于它的解釋充分性和描述充分性。根據(jù)這一論斷，Prince和Smolensky (1993/2004:233)認(rèn)為，不應(yīng)提出這一基本標(biāo)準(zhǔn)之外的諸如“計(jì)算可行性”這樣任意的條件來衡量語法的好壞。在滿足描述力和解釋力的前提下，研究者可以對(duì)語法的形式進(jìn)行創(chuàng)新。

大多數(shù)形式語法理論都區(qū)分語言能力(competence)和語言運(yùn)用(performance)，尤其是生成語法理論。因此，如果一部語法能夠解釋自然語言中可觀察到的系統(tǒng)性以及說話人的語法判斷(語言能力)，那么這便是一部具有充分性/好的語法。相對(duì)而言，解釋人腦中語言知識(shí)的具體執(zhí)行過程(語言運(yùn)用)并不是形式語法理論所追求的目標(biāo)，而是語言學(xué)各分支如心理語言學(xué)、神經(jīng)語言學(xué)和計(jì)算語言學(xué)等所關(guān)注的課題?？傊Z法理論模型不等同于其具體的計(jì)算執(zhí)行過程(Kager 1999: 26)。

2.計(jì)算復(fù)雜性與人腦對(duì)自然語言的處理能力

將復(fù)雜度理論用于研究自然語言的語法已經(jīng)有20多年的歷史，但學(xué)界仍然存在著認(rèn)為各種形式主義在計(jì)算上不可解的不少論點(diǎn)。例如，Barton(1986)指出，雙層音系-形態(tài)模型(two-level phonology and morphology，簡(jiǎn)稱TWOL)在計(jì)算上難解，而人們?cè)趫?zhí)行音系和形態(tài)分析時(shí)僅在有限時(shí)間內(nèi)便可完成，可見TWOL不能描述人類在音系和形態(tài)上的能力。然而，這一模型20多年來一直保持著領(lǐng)先地位，并未受到難解問題的影響。同樣，Idsardi(2006a, b)指出，優(yōu)選論的計(jì)算不可解，但人們執(zhí)行語言能力的過程只是在有限時(shí)間內(nèi)完成，故優(yōu)選論不能描述人類的語言能力。Barton和Idsardi采用了相同的論證思路：首先將計(jì)算模型與某個(gè)語言現(xiàn)象的機(jī)制相結(jié)合；然后將此機(jī)制用于歸約NP難解問題，以證明該音系理論屬于難解問題；最后說明計(jì)算難解顯然與人類的語言處理能力相矛盾。這些理論所表現(xiàn)出的計(jì)算復(fù)雜性要遠(yuǎn)在人們處理能力之上(人類處理能力似乎呈線性或亞線性)，但它們都能以有效方式被人腦當(dāng)中的語法分析器(parsers)成功地得以執(zhí)行(Prince和Smonlensky 2004: 233)。

事實(shí)上，Barton本人也預(yù)知了自己分析中存在的問題：計(jì)算理論只針對(duì)任意規(guī)模的句子和詞庫進(jìn)行應(yīng)用，而自然語言只處理有限規(guī)模的問題，那么復(fù)雜性理論是否有意義？復(fù)雜度理論所確定的邏輯運(yùn)算量與心理學(xué)實(shí)驗(yàn)所測(cè)量的人們執(zhí)行任務(wù)時(shí)所感到的困難程度之間的關(guān)系究竟如何？這些問題目前尚不明確(Kornai 2006b)。

3.實(shí)際的計(jì)算操作結(jié)果

對(duì)優(yōu)選論不可計(jì)算最有力的反駁來自已經(jīng)獲得的計(jì)算操作情況。首先，從篩選機(jī)制上看，評(píng)估器對(duì)無限數(shù)量的候選項(xiàng)是按組進(jìn)行淘汰的，而非逐一排除。Karttunen(1998)的研究結(jié)果也表明，為輸入項(xiàng)選擇最優(yōu)輸出項(xiàng)的計(jì)算過程完全可以在有限狀態(tài)演算中完成，并受到違反制約條件的次數(shù)的限定；這種限定并不會(huì)引起有限狀態(tài)系統(tǒng)在實(shí)際計(jì)算過程中的困難，因?yàn)槲覀儍H需考慮其中一小部分制約條件被違反的情況(Kager 1999: 26-27)。另外，計(jì)算有效性與具體的算法設(shè)計(jì)緊密相關(guān)。目前所設(shè)計(jì)的用于計(jì)算最優(yōu)表層形式的模型包括Ellison(1994)、Eisner(1997)、Albro(1998, 2005)的權(quán)重有限狀態(tài)機(jī)(weighted finite state machines)、Tesar(1996)的上下文自由語法(context-free grammars)、Karttunen(1998)的有限狀態(tài)轉(zhuǎn)換器(initiate-state transducers)等等。研究者仍在不斷設(shè)計(jì)新的算法，計(jì)算性的結(jié)果也會(huì)隨之發(fā)生改變(Prince和Smonlensky 1993/2004: 233; Albro 2005: 17-19)。

四、結(jié) 語

在計(jì)算機(jī)誕生之初，Chomsky就試圖用高度抽象的形式語言來描寫自然語言，并將其應(yīng)用于計(jì)算機(jī)程序語言當(dāng)中。這就表明，他嘗試將自然語言和計(jì)算機(jī)語言統(tǒng)一于同一個(gè)形式框架之內(nèi)?！靶问秸Z法的研究直接為語言的計(jì)算機(jī)處理準(zhǔn)備了條件”(陸極致1990:183)。 “以計(jì)算的過程作為大腦處理語言的過程的觀點(diǎn)在音系學(xué)家中已經(jīng)得到普遍認(rèn)同”(趙忠德，鮮明 2009)。國內(nèi)有關(guān)優(yōu)選論計(jì)算性的爭(zhēng)論仍在繼續(xù)，厘清該問題可以使我們更加深入地了解優(yōu)選論，探討其發(fā)展方向，同時(shí)有助于我們進(jìn)一步認(rèn)識(shí)語法可學(xué)性、二語習(xí)得的本質(zhì)等問題(馬秋武2003, 2008:265, 79)。

研究計(jì)算性問題可以使我們能更加深入地了解優(yōu)選論，探討它的發(fā)展方向。優(yōu)選論計(jì)算性的問題仍在探討之中，期望本文對(duì)該問題的梳理能為相關(guān)理論研究做出一定的貢獻(xiàn)。