1975 ACM Turing Award Lecture

1975 年度的 ACM Turing Award 在 10 月 20 日於 Minneapolis 舉行的 ACM 年會上，共同頒發給 Allen Newell 與 Herbert A. Simon。圖靈獎委員會主席 Bernard A. Galler 在介紹得獎者時，宣讀了以下頌詞：

「我很榮幸能將 ACM Turing Award 頒發給兩位長期的朋友，Carnegie-Mellon University 的 Allen Newell 教授和 Herbert A. Simon 教授。

在他們二十多年來的共同科學努力中，最初與 RAND Corporation 的 J.C. Shaw 合作，隨後又與 Carnegie-Mellon University 的眾多教職員工和學生同事合作，他們對人工智慧、人類認知心理學以及列表處理做出了基礎性貢獻。

在人工智慧領域，他們貢獻了將該領域確立為一項科學事業、普遍啟發式程式設計的發展，特別是啟發式搜尋、均值-目的分析（means-ends analysis）和歸納方法，並證明了這些機制足以解決有趣的問題。

在心理學領域，他們是人類認知可以用符號系統描述的觀念的主要倡導者，他們發展了用於人類問題解決、語言學習以及在多種任務領域中的歸納行為的詳細理論，並使用體現這些理論的電腦程式來模擬人類行為。

他們顯然是列表處理的發明者，並且對軟體技術和將電腦視為操作符號結構而不僅僅是處理數值資料的系統概念的發展做出了重要貢獻。

授予 Newell 教授和 Simon 教授這項獎項是他們的榮耀，但 ACM 也能將他們的名字添加到我們的得獎者名單中，這也是 ACM 的榮耀，因為他們的存在將增加 ACM Turing Award 的聲望和重要性。」

Allen Newell and Herbert A. Simon

電腦科學是研究圍繞著電腦的現象。本協會的創始者非常清楚這一點，他們稱自己為 Association for Computing Machinery。我們研究的有機體是機器——不僅是硬體，還有經由程式控制的、活生生的機器。

這是第十次圖靈講座。之前登上這個講台的九個人提出了九種不同的電腦科學觀點。我們的有機體，即機器，可以在許多層面和從許多角度來研究。今天能來到這裡，並提出另一種觀點，即滲透在我們獲得獎項的科學工作中的觀點，我們深感榮幸。我們希望談談作為經驗探索的電腦科學。

我們的觀點只是許多觀點中的一個；之前的講座已經清楚地表明了這一點。然而，即使將所有這些講座加起來，它們也未能涵蓋我們科學的全部範疇。這些圖靈獎項並未代表許多基礎性的方面。而且，如果時間終將到來，當然不是現在，當指南針已定位、當電腦科學已從各個方面討論過時，那將是時候重新開始這個循環。每年圖靈講座的講者將必須做出年度衝刺，以趕上科學和技術發展這隻烏龜在穩定前進中所取得的點滴累積進步。每一次戰爭都會創造新的鴻溝並要求新的衝刺。因為在科學中，沒有最後的定論。

電腦科學是一門經驗學科。我們本來會稱其為實驗科學，但就像天文學、經濟學和地質學一樣，它的一些獨特的觀察和經驗形式不符合狹隘的實驗方法刻板印象。儘管如此，它們仍然是實驗。建造的每一台新機器都是一個實驗。實際建造機器向自然提出了一個問題；我們通過觀察機器的運行並利用所有可用的分析和測量手段來分析它，從而傾聽答案。建造的每一個新程式都是一個實驗。它向自然提出了一個問題，而它的行為提供了對該問題的答案。機器和程式都不是黑箱：它們是人工產物，無論是硬體還是軟體，我們都可以打開它們並查看內部。我們可以將它們的結構與它們的行為聯繫起來，並從單一實驗中吸取許多教訓。我們不必建造 100 個定理證明器來統計證明它沒有像預期的那樣克服搜尋的組合爆炸。只需在少數幾次運行後檢查程式，就能揭示缺陷，並讓我們繼續下一次嘗試。

我們建造電腦和程式有許多原因。我們建造它們是為了服務社會，並作為執行社會計算任務的工具。但作為基礎科學家，我們建造機器和程式是一種發現新現象和分析我們已知的現象的方式。社會經常對此感到困惑，認為電腦和程式的建造只應該為了它們的經濟用途（或作為導向這種用途的發展序列中的中間產品）。社會需要理解，圍繞著電腦的現象是深刻而隱晦的，需要大量的實驗來評估其本質。社會需要理解，就像在任何科學中一樣，從這些實驗和理解中獲得的收益會帶來永久獲得新技術的回報；正是這些技術將創造幫助社會實現其目標的工具。

然而，我們在這裡的目的並非向外部世界請求理解，而是檢視我們科學的一個方面：通過經驗探索發展新的基礎理解。最好的方式是透過範例來說明。我們將藉此場合，從我們自己的研究領域選擇範例，敬請見諒。正如即將顯現的，這些範例涉及人工智慧的整個發展，特別是在早期階段。它們不僅僅基於我們個人的貢獻。即使在我們做出了直接貢獻的地方，這也是與他人合作完成的。我們的合作者特別包括 Cliff Shaw，我們在五十年代後期那個令人興奮的時期與他組成了一個三人團隊。但我們也與 Carnegie-Mellon University 的許多同事和學生合作過。

時間僅允許討論兩個例子。第一個是符號系統概念的發展。第二個是啟發式搜尋概念的發展。這兩個概念對於理解資訊如何處理以及智慧如何達成具有深遠的意義。然而，它們並未能完全涵蓋人工智慧的全部範疇，儘管我們認為它們對於展示電腦科學這部分領域的基礎知識性質有所助益。

I. Symbols and Physical Symbol Systems

電腦科學對知識的一個基礎性貢獻，是在相當基礎的層面解釋了符號是什麼。這個解釋是關於自然的科學命題。它是經驗性的，經歷了漫長且漸進的發展。

符號是智能行為的根本，智能行為當然是人工智慧的主要主題。就此而言，它也是所有電腦科學的主要問題。所有資訊都是由電腦為達到某個目的而處理的，我們通過一個系統在其面對任務環境所帶來的變化、困難和複雜性時，實現既定目標的能力來衡量其智能。當所完成的任務範圍有限時，電腦科學在達成智能上的這種普遍投入就會變得模糊不清，因為那樣就可以準確預見環境的全部變化。隨著我們將電腦擴展到更為廣泛、更為複雜、知識更密集的任務時，這種投入就變得更為明顯——當我們試圖讓它們成為我們的代理人，能夠自行處理自然世界的全部偶發情況時。

我們對智能行為所需的系統需求的理解是緩慢形成的。它是複合的，因為沒有任何一個單一的基本事物可以解釋智能的所有表現。沒有一個「智能原理」，就像沒有一個「生命原理」能憑藉其本質傳達生命的精髓一樣。但是，缺乏一個簡單的 deus ex machina 並不意味著智能沒有結構性需求。其中一個要求是儲存和操作符號的能力。為了提出科學問題，我們可以改述 Warren McCulloch [1961] 一篇著名論文的標題：符號是什麼，以至於智能可以使用它；智能是什麼，以至於它可以使用符號？

Laws of Qualitative Structure

所有科學都描述了其研究系統的本質。這些描述在本質上都是定性的，因為它們設定了詳細知識可以發展的條件。它們的精髓通常可以通過非常簡短、非常普遍的陳述來捕捉。人們可能會認為這些普遍法則由於其有限的具體性，對科學總體貢獻相對較小，如果不是歷史證據表明它們是最重要的結果的話。

The Cell Doctrine in Biology

定性結構法則的一個很好的例子是生物學中的細胞學說，它指出所有生物體的基本構成單元是細胞。細胞有多種多樣的形式，儘管它們都具有一個由原生質包圍的細胞核，整體由細胞膜包裹。但是，這種內部結構在歷史上並非細胞學說規格的一部分；它是隨後通過深入研究發展出來的具體內容。細胞學說幾乎完全可以用我們上面給出的陳述來傳達，再加上一些關於細胞大小的模糊概念。然而，這條法則對生物學的影響是巨大的，而在其逐漸被接受之前該領域損失的動能相當大。

Plate Tectonics in Geology

地質學提供了一個有趣的定性結構法則範例，之所以有趣是因為它在過去十年中獲得了接受，因此其地位的提升仍然記憶猶新。板塊構造理論主張地球表面是由數十個巨大的板塊組成的集合——總共幾十個——這些板塊以地質學的速度相互碰撞、覆蓋、並潛入地球中心，在那裡它們失去了身份。板塊的運動解釋了大陸和海洋的形狀和相對位置，火山和地震活動區域，深海海脊等等。除了速度和大小的一些額外細節外，基本理論已經被指定了。當然，它直到成功解釋了一些細節（例如解釋了西非和南美東北部之間的植物、動物和地層學一致性）並將所有這些細節結合起來才被接受。板塊構造理論是高度定性的。現在它已被接受，整個地球似乎處處都為其提供證據，因為我們以其觀點看待世界。

The Germ Theory of Disease

巴斯德（Pasteur）提出疾病的細菌理論至今不過一個多世紀，這是一條定性結構法則，它在醫學上引起了一場革命。該理論提出，大多數疾病是由微小的單細胞生物在體內存在和繁殖引起的，而傳染則是指這些生物從一個宿主傳播到另一個宿主。該理論闡述的一個重要部分是識別與特定疾病相關的生物，描述它們，並追蹤它們的生命史。該法則存在許多例外——許多疾病並非由細菌引起——這一事實並未減損其重要性。該法則告訴我們尋找一種特定類型的原因；它並不堅持我們總會找到它。

The Doctrine of Atomism

原子論與我們剛剛描述的三個定性結構法則提供了有趣的對比。當它從道爾頓（Dalton）的工作及其關於化學物質按固定比例結合的論證中出現時，這條法則提供了一個典型的定性結構範例：元素由微小、均勻的粒子組成，這些粒子因元素而異。但由於基礎的原子種類非常簡單且種類有限，很快就形成了定量理論，將原始定性假設中的所有一般結構都吸收進來。與細胞、構造板塊和細菌不同，結構的多樣性如此之大，以至於基礎的定性原理仍然清晰可見，並且其對整體理論的貢獻清晰可辨。

Conclusion

定性結構法則在科學中無處不在。我們一些最偉大的科學發現就包含在這些法則之中。正如範例所示，它們常常為整個科學的運作設定了基調。

Physical Symbol Systems

讓我們回到符號的主題，並定義一個物理符號系統 (physical symbol system)。形容詞「物理」表示兩個重要特徵：(1) 這種系統明顯遵循物理定律——它們可以由工程系統使用工程元件來實現；(2) 儘管我們使用「符號」一詞預設了我們預期的解釋，但它不限於人類符號系統。

一個物理符號系統由一組稱為符號 (symbols) 的實體組成，這些符號是物理模式，可以作為另一種類型實體（稱為表達式 (expression) 或符號結構 (symbol structure)）的組成部分。因此，一個符號結構由許多符號的實例 (instances) (或標記 (tokens)) 以某種物理方式相關聯而組成（例如，一個標記緊鄰另一個）。在任何給定時刻，系統將包含這些符號結構的集合。除了這些結構之外，系統還包含一組過程 (processes)，這些過程作用於表達式以產生其他表達式：創造、修改、複製和銷毀的過程。物理符號系統是一台隨著時間產生不斷演變的符號結構集合的機器。這種系統存在於一個比這些符號表達式本身更廣闊的物件世界中。

兩個概念是這種表達式、符號和物件結構的核心：指稱 (designation) 和解釋 (interpretation)。

指稱 (Designation)：一個表達式指稱 (designates) 一個物件，如果在給定表達式的情況下，系統可以影響物件本身或以依賴於物件的方式行動。

在這兩種情況下，都通過表達式獲得了對物件的存取，這是指稱的本質。

解釋 (Interpretation)：如果一個表達式指稱 (designates) 一個過程，並且如果在給定表達式的情況下系統可以執行該過程，則系統可以解釋 (interpret) 這個表達式。

解釋意味著一種特殊形式的依賴性行動：給定一個表達式，系統可以執行指定的過程，也就是說，它可以從指稱它們的表達式中調用並執行自己的過程。

一個在剛才指示的意義上具有指稱和解釋能力的系統，還必須滿足許多額外的要求，包括完整性和閉包性。我們只能簡略提及這些；所有這些都很重要並且具有深遠的後果。

(1) 一個符號可以用來指稱任何表達式。也就是說，給定一個符號，它能指稱什麼表達式並非預先規定。這種任意性只適用於符號本身；符號標記及其相互關係決定了複雜表達式指稱哪個物件。(2) 存在指稱機器所有能力的過程的表達式。(3) 存在用於創建任何表達式以及以任意方式修改任何表達式的過程。(4) 表達式是穩定的；一旦創建，除非明確修改或刪除，否則將持續存在。(5) 系統可以持有的表達式數量基本上是無限的。

我們剛才定義的這種類型的系統對於電腦科學家來說並不陌生。它與通用電腦有很強的家族相似性。如果將一種符號操作語言，例如 LISP，視為定義了一台機器，那麼這種親緣關係就真正變成了兄弟般的關係。我們闡述這樣一個系統的目的並非提出新的東西。恰恰相反：是為了展示現在已知和假設的、滿足這種特徵的系統是什麼樣的。

我們現在可以提出一個普遍的科學假設——符號系統的定性結構法則：

物理符號系統假設 (The Physical Symbol System Hypothesis)：一個物理符號系統擁有實現普遍智能行動所需的必要且充分的方法。

所謂「必要」，我們的意思是，任何展現普遍智能的系統經分析都會證明是一個物理符號系統。所謂「充分」，我們的意思是，任何足夠大的物理符號系統可以被進一步組織起來以展現普遍智能。所謂「普遍智能行動」，我們希望指的範圍與我們在人類行動中看到的智能範圍相同：即在任何實際情況下，都能在一定的速度和複雜性限制內，產生與系統目標相符且適應環境需求的行為。

物理符號系統假設顯然是一條定性結構法則。它指定了一個普遍的系統類別，智能行動的能力將在其中找到。

這是一個經驗假設。我們定義了一類系統；我們想問這個類別是否能解釋我們在現實世界中發現的一系列現象。智能行動在生物世界中無處不在，主要體現在人類行為中。無論是人類執行還是非人類執行，它都是一種我們可以從其效果辨識出來的行為形式。這個假設確實可能是錯誤的。智能行為並非易於產生，以至於任何系統都能隨意展現。實際上，有些人基於哲學或科學理由分析後得出結論認為這個假設是錯誤的。從科學角度來看，只能通過提出關於自然世界的經驗證據來攻擊或捍衛它。

我們現在需要追溯這個假設的發展並審視支持它的證據。

Development of the Symbol System Hypothesis

物理符號系統是通用機器的實例。因此，符號系統假設意味著智能將由通用電腦實現。然而，這個假設遠超出了基於物理決定論的普遍論證，即任何可實現的計算都可以由通用機器實現，前提是它已經被指定。因為它明確斷言智能機器是符號系統，從而對智能系統的本質做出了特定的體系結構斷言。理解這種額外的具體性是如何產生的非常重要。

Formal Logic

這個假設的根源可以追溯到 Frege 以及 Whitehead 和 Russell 將邏輯形式化的計劃：將數學的基本概念性概念納入邏輯，並將證明和演繹的概念建立在穩固的基礎上。這項努力最終形成了數理邏輯——我們熟悉的命題邏輯、一階邏輯和高階邏輯。它發展了一種特有的觀點，通常被稱為「符號遊戲」。邏輯，以及由此納入的所有數學，是一場使用無意義的符號，根據某些純粹句法規則進行的遊戲。所有意義都被清除掉了。人們得到了一個機械的，儘管是允許的（我們現在會說非確定的），關於其可以證明各種事情的系統。因此，最初的進步是通過擺脫所有與意義和人類符號相關的事物來取得的。我們可以稱之為形式符號操作 (formal symbol manipulation) 的階段。

這種普遍態度在資訊理論的發展中得到了很好的體現。人們一次又一次指出，Shannon 定義的系統只對通信和選擇有用，與意義無關。人們對該領域被賦予「資訊理論」如此普遍的名稱表示遺憾，並試圖將其重新命名為「選擇性資訊理論」——當然，毫無用處。

Turing Machines and the Digital Computer

第一台數位電腦和自動機理論的發展，從 Turing 在 30 年代的工作開始，可以一起處理。它們在對重要事物的看法上是一致的。讓我們使用 Turing 自己的模型，因為它很好地展示了這些特徵。

一部 Turing 機由兩個記憶體組成：一條無限長的紙帶和一個有限狀態控制器。紙帶儲存資料，也就是著名的零和一。機器擁有一套非常小的基本操作——在紙帶上的讀、寫和掃描操作。讀操作不是資料操作，而是根據讀頭下的資料提供到控制狀態的條件分支。眾所周知，這個模型包含所有電腦的精髓，就它們能做什麼而言，儘管具有不同記憶體和操作的其他電腦可能會以不同的空間和時間要求執行相同的計算。特別是，Turing 機的模型包含著什麼是不可計算的概念以及通用機器的概念——可以做任何機器能做的事情的電腦。

我們應該驚嘆，在現代電腦誕生之前，我們對資訊處理的兩個最深刻的洞見竟然在三十年代就已達成。這是對 Alan Turing 天才的致敬。這也是對當時數理邏輯發展的致敬，並證明了電腦科學對其的深厚債務。與 Turing 的工作同時出現的還有邏輯學家 Emil Post 和（獨立地）Alonzo Church 的工作。他們從獨立的邏輯系統概念（Post 生產系統和遞歸函數）出發，得出了關於不可判定性和普遍性的相似結果——這些結果很快就被證明意味著這三個系統是等價的。實際上，所有這些試圖定義最廣泛資訊處理系統類別的努力的會聚，為我們確信在這些模型中捕捉到了資訊處理的精髓提供了一些力量。

在這些系統中，表面上都沒有符號作為指稱某物的概念。數據被視為只是零和一的字串——實際上，數據必須是惰性的，這對於將計算簡化為物理過程至關重要。有限狀態控制系統總是作為一個小型控制器來考慮，並且進行邏輯遊戲以查看可以在不破壞機器普遍性的情況下使用多小的狀態系統。據我們所知，從未進行過動態地向有限控制添加新狀態的遊戲——即將控制記憶視為持有系統大部分知識的遊戲。在這個階段完成的是解釋原理的一半——證明機器可以根據描述運行。因此，這是自動形式符號操作 (automatic formal symbol manipulation) 的階段。

The Stored Program Concept

隨著四十年代中期（在 Eniac 之後）第二代電子機器的發展，出現了儲存程式概念 (stored program concept)。這被正確地譽為一個里程碑，無論是概念上還是實踐上。程式現在可以作為資料，並且可以像資料一樣被操作。這種能力當然已經隱含在 Turing 的模型中：描述位於與資料相同的紙帶上。然而，這個想法直到機器獲得足夠的記憶體，使得將實際程式放在某個內部位置變得可行時才得以實現。畢竟，Eniac 只有二十個暫存器。

儲存程式概念體現了解釋原理的後半部分，即系統自身的資料可以被解釋的部分。但它尚未包含指稱 (designation) 的概念——即支撐意義的物理關係。

List Processing

下一個步驟是 1956 年的列表處理 (list processing)。資料結構的內容現在是符號，是我們物理符號系統意義上的符號：具有指稱物、具有所指的模式。列表持有地址，這些地址允許訪問其他列表——因此產生了列表結構的概念。這是一個新的觀點，在列表處理的早期，同事們常常問資料在哪裡——也就是說，哪個列表最終持有系統內容的位元集合——這一點向我們多次證明了這一點。他們覺得很奇怪，根本沒有這樣的位元，只有指稱其他符號結構的符號。

列表處理在電腦科學的發展中同時是三件事。(1) 它是在一台先前被認為結構固定的機器中創建了一個真正的動態記憶體結構。它為我們的操作集增加了除替換和改變內容之外的創建和修改結構的操作。(2) 它是一個關於電腦由一組資料類型和一組與這些資料類型相關的操作組成的基本抽象的早期演示，這樣一個計算系統就應該使用適合於應用的任何資料類型，而與底層機器無關。(3) 列表處理產生了一個指稱 (designation) 模型，從而以我們今天在電腦科學中使用這個概念的方式定義了符號操作 (symbol manipulation)。

正如經常發生的那樣，當時的實踐已經預示了列表處理的所有要素：顯然使用地址來獲得存取，鼓式機器使用鏈式程式（即所謂的一加一地址編址），等等。但是將列表處理作為一種抽象的概念創造了一個新世界，其中指稱 (designation) 和動態符號結構 (dynamic symbolic structure) 是定義性特徵。將早期的列表處理系統嵌入語言（IPLs, LISP）中，常常被批評為阻礙了列表處理技術在程式設計實踐中的傳播；但它是保持抽象統一的載體。

LISP

還有一個步驟值得注意：McCarthy 在 1959-60 年創建 LISP [McCarthy, 1960]。它完成了抽象的行為，將列表結構從具體機器的嵌入中提升出來，創建了一個具有 S-表達式的新形式系統，該系統可以證明與其他通用的計算方案等價。

Conclusion

符號操作和具體的指稱符號概念直到五十年代中期才出現，這並不意味著之前的步驟不重要或不那麼重要。完整的概念是計算能力、物理實現性（以及多種技術）、普遍性、過程的符號表示（即可解釋性），以及最終的符號結構和指稱的結合。每個步驟都提供了整體的一個基本部分。

這個鏈條中的第一步，由 Turing 完成，是理論性的，但其他步驟都具有深刻的經驗基礎。我們是由電腦本身的演進引導的。儲存程式原理源於 Eniac 的經驗。列表處理源於建構智能程式的嘗試。它從隨機存取記憶體的出現中獲得啟示，這為地址中的指稱符號提供了清晰的物理實現。LISP 源於列表處理的演進經驗。

The Evidence

我們現在來談談物理符號系統能夠進行智能行動的假設的證據，以及普遍智能行動需要物理符號系統的證據。這個假設是一個經驗性概括，而不是一個定理。我們不知道如何從純邏輯上證明符號系統與智能之間的聯繫。由於缺乏這樣的證明，我們必須審視事實。然而，我們的中心目標並非詳細審查證據，而是利用眼前這個例子來說明電腦科學是一個經驗探究領域的論點。因此，我們將只指出有哪些類型的證據，以及測試過程的總體性質。

物理符號系統的概念基本上在 1950 年代中期形成現有的形式，從那時起，人工智慧作為電腦科學的一個連貫子領域開始發展。此後二十年的工作見證了兩種主要經驗證據的持續累積。第一種是關於物理符號系統足以產生智能的證據，試圖建構和測試具有這種能力的特定系統。第二種證據是關於在展現智能的地方必須具備物理符號系統的必要性。它始於人類，我們最熟悉的智能系統，並試圖發現他的認知活動是否可以用物理符號系統的工作來解釋。還有其他形式的證據，我們稍後會簡要評論，但這兩種是重要的。我們將依次考慮它們。第一種通常稱為人工智慧，第二種稱為資訊處理心理學研究。

Constructing Intelligent Systems

疾病的細菌理論的初步測試基本範式是：識別一種疾病；然後尋找病原體。類似的範式啟發了人工智慧的大部分研究：識別一個需要智能的任務領域；然後為數位電腦建構一個可以在該領域處理任務的程式。首先考察了簡單且結構良好的任務：拼圖和遊戲、排程和資源分配的運籌學問題、簡單的歸納任務。現在已經建構了數十個甚至數百個這類程式，每個程式都能在相應領域表現出一定程度的智能行動。

當然，智能並非全有或全無之事，在特定領域實現更高水準的表現持續取得進展，同時也在擴大這些領域的範圍。例如，早期的西洋棋程式只要能合法地進行遊戲並顯示一些目標性就被認為是成功的；稍後，它們達到了人類初學者的水準；在十到十五年內，它們開始與認真的業餘愛手競爭。進展一直緩慢（總投入的程式設計工作量也很小），但持續不斷，建構-測試的範式按照規則的週期進行——整個研究活動在宏觀層面模仿了許多 AI 程式的基本生成-測試週期。

當然，所發生的事情遠不止於簡單地累積適應特定任務領域的智能系統範例。如果執行這些不同任務的 AI 程式除了是物理符號系統的實例外別無共同點，那將是令人驚訝且缺乏吸引力的。因此，人們對於尋找具有普遍性的機制以及執行各種任務的程式中的共同組件產生了極大的興趣。這種探索將理論從最初的符號系統假設推進到更完整地描述在人工智慧中有效的特定類型符號系統。在本文的第二部分，我們將討論這種第二層具體性假設的一個例子：啟發式搜尋假設。

對普遍性的探索催生了一系列旨在將通用問題解決機制與特定任務領域的要求分離開的程式。General Problem Solver (GPS) 也許是其中第一個；其後代包括 PLANNER 和 CONNIVER 等當代系統。對共同組件的探索導致了目標和計劃的廣義表示方案、構建區別網絡的方法、樹搜尋的控制程序、模式匹配機制以及語言解析系統。目前正在進行實驗，以尋找表示時間和時態、運動、因果關係等的便捷裝置。越來越多地，可以透過模組化的方式從這些基本組件組裝大型智能系統。

我們可以藉由回顧細菌理論的類比來了解目前正在發生的事情。如果說該理論最初的研究浪潮主要在於為每種疾病找到病原體，那麼隨後的努力則轉向了解病原體是什麼——在基本定性法則之上建立一個新的結構層次。在人工智慧領域，最初旨在為各種幾乎隨機選擇的任務建立智能程式的活動，正讓位於更具針對性的研究，旨在理解這些系統的共同機制。

The Modeling of Human Symbolic Behavior

符號系統假設意味著人類的符號行為是由於他具備物理符號系統的特徵而產生的。因此，使用符號系統模擬人類行為的努力結果成為該假設的重要證據的一部分，人工智慧研究與資訊處理心理學研究（通常這樣稱呼）密切合作進行。

在過去的二十年中，尋找以符號系統解釋人類智能行為的方法取得了很大的成功；以至於資訊處理理論成為認知心理學當代的主流觀點。特別是在問題解決、概念獲得和長期記憶領域，符號操作模型現在佔據了主導地位。

資訊處理心理學的研究涉及兩種主要的經驗活動。第一種是對需要智能的任務中的人類行為進行觀察和實驗。第二種，與人工智慧中的平行活動非常相似，是程式設計符號系統以模擬觀察到的人類行為。心理學的觀察和實驗導致了關於被試所使用的符號過程的假設的形成，這些假設是構建程式的重要思想來源。因此，GPS 的許多基本機制思想都源於對人類被試在執行問題解決任務時邊想邊說（thinking aloud）的協議的仔細分析。

電腦科學的經驗性在與心理學的這種聯盟中表現得最為明顯。不僅需要心理學實驗來驗證模擬模型作為人類行為解釋的真實性，而且實驗也產生了設計和建造物理符號系統的新想法。

Other Evidence

我們尚未考慮的符號系統假設的主要證據體現為負面證據 (negative evidence)：即缺乏關於智能活動可能如何完成的特定競爭性假設——無論是由人還是機器完成。大多數建構此類假設的嘗試都發生在心理學領域。在這裡，我們有一個從通常標示為「行為主義」到通常標示為「格式塔理論」的連續性理論。這兩種觀點都不能真正與符號系統假設競爭，原因有二。首先，行為主義和格式塔理論都沒有證明，甚至沒有顯示如何證明，其假定的解釋機制足以解釋複雜任務中的智能行為。其次，這兩種理論都未能達到人工程式所具有的具體性。事實上，替代理論是如此模糊，以至於給予它們資訊處理的解釋並將它們歸入符號系統假設並非難事。

Conclusion

我們試圖使用物理符號系統假設的例子，具體地說明電腦科學是通常意義上的科學事業：它發展科學假設，然後尋求通過經驗探究來驗證這些假設。然而，我們選擇這個特定例子來論證我們的觀點還有第二個原因。物理符號系統假設本身就是一種重要的科學假設，屬於我們之前稱之為「定性結構法則」的類型。它代表了電腦科學的一項重要發現，如果經驗證據能夠證實它（事實上似乎正在發生），將對該領域產生持續的重大影響。

我們現在轉向第二個例子，搜尋在智能中的作用。這個主題，以及我們將檢驗的關於它的特定假設，也在電腦科學，特別是人工智慧中扮演了核心角色。

知道物理符號系統為智能行動提供了基礎，並不能告訴我們它們是如何實現這一目標的。我們在電腦科學中定性結構法則的第二個例子解決了後者這個問題，它斷言符號系統通過使用啟發式搜尋的過程來解決問題。這個概括，與前一個一樣，基於經驗證據，並非從其他前提形式推導出來。然而，我們很快就會看到它與符號系統假設確實存在一些邏輯聯繫，也許我們可以期待在未來的某個時候將這種聯繫形式化。在那之前，我們的故事仍將是一個經驗探究的故事。我們將描述已知關於啟發式搜尋的知識，並回顧證明它如何實現智能行動的經驗發現。我們首先陳述這個定性結構法則，即啟發式搜尋假設 (Heuristic Search Hypothesis)。

啟發式搜尋假設 (Heuristic Search Hypothesis)：問題的解由符號結構表示。物理符號系統在問題解決中通過搜尋 (search)——即通過生成並逐步修改符號結構直到產生解結構——來運用其智能。

物理符號系統必須使用啟發式搜尋來解決問題，因為這類系統的處理資源有限；在有限的步數和有限的時間間隔內，它們只能執行有限數量的過程。當然，這不是一個非常強的限制，因為所有通用的 Turing 機都受此限制。然而，我們是以更強烈的意義來理解這個限制：我們是指實際上受限 (practically limited)。我們可以想像一些系統在實踐上不受限制，例如，能夠以每個深度單元進展的恆定速率並行搜尋指數級擴展的樹的節點。我們在這裡不關心這樣的系統，而是關心那些計算資源相對於它們所面臨情況的複雜性來說很稀缺的系統。這種限制不會排除任何實際任務背景下的真實符號系統，無論是電腦還是人類。資源有限的事實允許我們在大多數情況下將符號系統視為一個串行的、一次只處理一個過程的設備；如果在任何短暫的時間間隔內它只能完成少量處理，那麼我們不妨將其視為一次做一件事。因此，「有限資源符號系統」和「串行符號系統」在實踐上是同義的。在時刻與時刻之間分配稀缺資源的問題，如果時刻足夠短，通常可以視為排程一台串行機的問題。

Problem Solving

由於問題解決能力通常被視為系統是否具有智能的主要指標，因此人工智慧的大部分歷史都與嘗試建構和理解問題解決系統有關，這是很自然的。問題解決已經被哲學家和心理學家討論了兩千年，論述中充滿了神秘感。如果你認為符號系統解決問題沒有什麼問題或神秘之處，那麼你就是今日的孩子，你的觀點形成於本世紀中葉之後。柏拉圖（以及根據他的說法，蘇格拉底）甚至發現理解如何提出問題都很困難，更不用說如何解決問題了。讓我提醒你在《美諾篇》中他是如何提出這個難題的：

Meno: And how will you inquire, Socrates, into that which you know not? What will you put forth as the subject of inquiry? And if you find what you want, how will you ever know that this is what you did not know?

為了處理這個難題，柏拉圖發明了他著名的回憶說 (theory of recollection)：當你認為自己在發現或學習某物時，你實際上只是在回憶你在前世已經知道的東西。如果你覺得這個解釋荒謬可笑，今天有一個更簡單的解釋，基於我們對符號系統的理解。一個近似的陳述是：

陳述問題 (To state a problem) 就是指定 (1) 一個符號結構類別的測試 (test)（問題的解），以及 (2) 一個符號結構的生成器 (generator)（潛在的解）。解決問題 (To solve a problem) 就是使用 (2) 生成一個滿足 (1) 測試的結構。

如果我們知道我們想要做什麼（測試），並且如果我們不知道如何立即做到（我們的生成器不能立即產生滿足測試的符號結構），我們就有了問題。符號系統可以陳述和解決問題（有時），因為它可以生成和測試。

如果這就是問題解決的全部內容，為什麼不簡單地立即生成一個滿足測試的表達式呢？這實際上是我們許願和做夢時所做的事情。「如果願望是馬，乞丐就能騎了。」但在夢境之外的世界，這是不可能的。知道一旦建構了某物，我們如何測試它，並不意味著我們知道如何建構它——我們沒有任何能這樣做的生成器。

例如，如何「解決」下贏西洋棋的問題是眾所周知的。存在一個簡單的測試來辨識獲勝局面，即檢查對方王是否被將死。在夢的世界裡，人們只需生成一個策略，使其在對手的所有反策略下都能導致將死。唉，現有的符號系統（人類或機器）都不知道存在這樣的生成器。相反，西洋棋中的好棋是通過生成各種替代方案，並使用近似且常常錯誤的衡量標準進行艱苦評估來尋找的，這些衡量標準被認為表明特定行棋路線通往獲勝局面的可能性。有移動生成器；但沒有獲勝移動生成器。

在能夠為問題生成移動之前，必須存在一個問題空間 (problem space)：一個可以表示問題情境（包括初始情境和目標情境）的符號結構空間。移動生成器是將問題空間中的一個情境修改為另一個情境的過程。物理符號系統的基本特性保證它們可以表示問題空間並且具備移動生成器。它們在任何具體情況下如何綜合與該情況相關的問題空間和移動生成器，這個問題仍然是人工智慧研究的前沿問題。

因此，當符號系統面臨一個問題和一個問題空間時，它的任務是利用其有限的處理資源，一個接一個地生成可能的解決方案，直到找到一個滿足問題定義測試的解決方案。如果系統能夠控制潛在解決方案的生成順序，那麼最好安排這種生成順序，以便實際解決方案有很大可能提早出現。符號系統在多大程度上做到這一點，就展現了多大的智能。對於資源有限的系統來說，智能在於明智地選擇下一步要做什麼。

Search in Problem Solving

在人工智慧研究的最初十年左右，問題解決的研究幾乎等同於搜尋過程的研究。從我們對問題和問題解決的描述中，很容易理解為什麼會這樣。實際上，可以問是否能有別的方式。但在我們嘗試回答這個問題之前，我們必須進一步探討搜尋過程的本質，正如它在那個十年的活動中所揭示的那樣。

Extracting Information from the Problem Space

考慮一組符號結構，其中一小部分是給定問題的解。進一步假設解在整個集合中是隨機分佈的。這意味著不存在任何資訊能夠使任何搜尋生成器比隨機搜尋表現更好。那麼，在解決問題時，任何符號系統都不能比任何其他系統展現更多（或更少）的智能，儘管某個系統可能比另一個系統運氣更好。因此，智能出現的一個條件是解的分佈不完全是隨機的，符號結構的空間至少展現一定程度的秩序和模式。第二個條件是符號結構空間中的模式或多或少可以被偵測到。第三個條件是潛在解的生成器能夠根據它偵測到的模式做出差異化的行為。問題空間中必須有資訊，並且符號系統必須能夠提取和利用這些資訊。讓我們首先看一個非常簡單的例子，其中智能很容易獲得。

考慮解決一個簡單代數方程式的問題：

AX + B = CX + D

測試將解定義為任何形如 X = Z 的表達式，使得 AZ + B = CZ + D。現在，可以將任何能產生數字的過程用作生成器，然後將這些數字代入後一個方程式中進行測試。我們不會稱這是一個智能生成器。

或者，可以使用利用原方程式可以通過等量加減或等量乘除而不改變其解的生成器來修改方程式。當然，我們還可以通過比較原表達式與解的形式，並精確地對方程式進行那些既不改變其解，又能使其達到期望形式的修改，來獲得更多引導生成器的資訊。這樣的生成器可以注意到原方程式右側有一個不需要的 CX，於是從兩邊減去它並重新整理項。然後它可以注意到左側有一個不需要的 B，於是減去它。最後，它可以通過除法擺脫左側不需要的係數 (A - C)。

因此，通過這個現在展現相當智能的程序，生成器產生一系列的符號結構，每個結構都是通過修改前一個結構獲得的；並且這些修改旨在減少當前表達式形式與期望表達式形式之間的差異，同時維持解決方案的其他條件。

這個簡單的例子已經說明了符號系統用於智能問題解決的許多主要機制。首先，每個連續的表達式不是獨立生成的，而是通過修改先前生成的表達式產生的。其次，修改不是隨意的，而是取決於兩種資訊。它們取決於在所有這類代數問題中保持不變並內建在生成器結構本身的資訊：表達式的所有修改都必須不改變方程式的解。它們也取決於在每一步都會改變的資訊：偵測當前表達式與期望表達式之間仍然存在的形式差異。實際上，生成器包含了解決方案必須滿足的一些測試，因此那些不滿足這些測試的表達式永遠不會被生成。使用第一類資訊保證了實際生成的只是所有可能表達式中極小的子集，但又不從這個子集中遺失解決方案表達式。使用第二類資訊通過一系列近似來達到期望的解決方案，運用一種簡單形式的均值-目的分析 (means-ends analysis) 來指導搜尋。

引導搜尋的資訊來自何處並非神秘。我們不必像柏拉圖那樣賦予符號系統一個前世，其中它已經知道了解決方案。一個中等程度的複雜生成器-測試系統無需訴諸轉世即可完成任務。

Search Trees

簡單的代數問題可能看起來像一個不尋常的，甚至是病態的搜尋例子。它肯定不是試錯搜尋，因為雖然有幾次嘗試，但沒有錯誤。我們更習慣於將問題解決搜尋視為生成可能性部分解決方案的茂密分支樹，這些樹在產生解決方案之前可能會增長到數千甚至數百萬個分支。因此，如果生成器從它生成的每個表達式產生 B 個新分支，那麼樹將按照 B^D 的方式增長，其中 D 是其深度。代數問題的樹增長具有其分支度 B 等於一的特殊性。

下西洋棋的程式通常會生成廣闊的搜尋樹，在某些情況下分支數量會達到一百萬個或更多。（雖然這個例子將用於說明我們關於樹搜尋的論點，但我們應該注意，在西洋棋中搜尋的目的不是生成建議的解決方案，而是評估（測試）它們。）一條關於遊戲程式的研究路線主要關注於改進棋盤的表示以及在棋盤上移動的過程，以加速搜尋並使其能夠搜尋更大的樹。這樣做的理由當然是，動態搜尋越深，結束時的評估應該越準確。另一方面，有充分的經驗證據表明，最強的人類棋手，即特級大師，很少探索超過一百個分支的樹。這種經濟性並非來自比西洋棋程式搜尋的深度淺，而是來自於在每個節點上分支非常稀疏和有選擇性。這只有在將更多選擇性內建到生成器本身中，使其能夠只選擇那些極有可能產生關於局面重要相關信息的枝幹的情況下才有可能，而且不會導致評估品質下降。

這段討論得出了一個有些自相矛盾的結論：搜尋——連續生成潛在解決方案結構——是符號系統在問題解決中運用智能的基本方面，但搜尋量 (amount of search) 並非衡量智能量 (amount of intelligence) 的標準。之所以存在問題，並非因為其解決需要大量搜尋，而是因為若未能運用必要的智能，則會需要大量搜尋。當努力解決問題的符號系統對該做什麼足夠了解時，它就直接朝目標前進；但一旦其知識變得不足，當它進入未知領域時，它就面臨著在重新找到方向之前經歷大量搜尋的威脅。

在每個生成問題解決方案的方案中都存在的搜尋樹呈指數爆炸的潛力，提醒我們不要依賴電腦的蠻力——即使是最大最快的電腦——來彌補其生成器的無知和無選擇性。仍然有人周期性地燃起希望，認為可以找到足夠快的電腦，並以足夠巧妙的方式程式設計，通過蠻力搜尋來下好西洋棋。從理論上來看，西洋棋遊戲中沒有已知的事物排除這種可能性。對大小適中的樹進行搜尋管理的經驗研究僅取得了溫和的結果，這使得這個方向不如西洋棋最初被選為人工智慧的合適任務時那樣有希望。我們必須將此視為西洋棋程式研究的重要經驗發現之一。

The Forms of Intelligence

那麼，智能的任務就是避免搜尋的指數爆炸這種潛在的威脅。如何實現這一點？第一個途徑，已經在代數範例以及僅生成「合理」走法供進一步分析的西洋棋程式中有所說明，是將選擇性內建到生成器中：只生成那些有希望成為解決方案或通往解決方案路徑上的結構。這樣做的通常結果是降低分支的速率，而不是完全阻止它。最終的指數爆炸並未避免——除了像代數範例那樣特別高度結構化的情況——只是延遲了。因此，一個智能系統通常需要用其他資訊利用技術來補充其解決方案生成器的選擇性以引導搜尋。

二十年來在各種任務環境中管理樹搜尋的經驗，產生了一套小型通用技術，這套技術是當今每個研究人員在人工智慧領域的裝備。由於這些技術已在如 Nilsson [1971] 的通用著作中有所描述，這裡可以簡要總結一下。

在串行啟發式搜尋中，基本問題永遠是：下一步該做什麼？在樹搜尋中，這個問題又包含兩個組成部分：(1) 我們應該從樹的哪個節點開始搜尋？以及 (2) 我們應該從該節點朝哪個方向搜尋？有助於回答第一個問題的資訊可以解釋為衡量不同節點與目標的相對距離。最佳優先搜尋 (Best-first search) 要求從看起來最接近目標的節點開始下一次搜尋。有助於回答第二個問題的資訊——搜尋哪個方向——通常是通過偵測當前節點結構與解決方案測試所描述的目標結構之間的特定差異來獲得的，並選擇與減少這些特定類型的差異相關的行動。這就是均值-目的分析 (means-ends analysis) 技術，它在 General Problem Solver 的結構中扮演著核心角色。

經驗研究作為 AI 研究中通用思想來源的重要性，可以透過追溯這兩個核心思想——最佳優先搜尋和均值-目的分析——在大量問題解決程式中的歷史來清晰地展示。最佳優先搜尋的雛形在 1955 年的 Logic Theorist 中已經存在，儘管尚未命名。體現均值-目的分析的 General Problem Solver 大約在 1957 年出現——但它將其與改良的深度優先搜尋結合，而不是最佳優先搜尋。西洋棋程式通常出於節省記憶體的原因，傾向於深度優先搜尋，約在 1958 年後補充了強大的 alpha-beta 剪枝程序。這些技術似乎都已被多次重新發明，並且直到 1960 年代中期或後期，才出現關於這些概念在數學理論上如何對問題解決進行一般性的、與任務無關的理論討論。它們從數學理論獲得的形式支撐仍然微乎其微：關於使用 alpha-beta 啟發式可以減少搜尋的一些定理，一些關於最短路徑搜尋的定理（由 Nilsson [1971] 回顧），以及一些關於帶有概率評估函數的最佳優先搜尋的最新定理。

"Weak" and "Strong" Methods

我們一直在討論的技術，是專注於控制而非防止指數擴展。因此，它們被恰當地稱為「弱方法」——當符號系統的知識或問題空間中實際包含的結構量不足以完全避免搜尋時使用的方法。將一個高度結構化的情況（例如可以表述為線性規劃問題）與組合問題（例如旅行商問題或排程問題）等結構較少的情況對比，是很有啟發性的。（這裡的「結構較少」是指關於問題空間結構的相關理論不足或不存在。）

在解決線性規劃問題時，可能需要大量的計算，但搜尋不會分支。每一步都是通往解決方案的路徑上的一步。在解決組合問題或證明定理時，樹搜尋很少能避免，成功取決於我們一直在描述的那類啟發式搜尋方法。

並非所有 AI 問題解決研究的流派都遵循我們概述的道路。定理證明系統的工作提供了一個不同觀點的例子。在這裡，從數學和邏輯中引入的思想對研究方向產生了強烈影響。例如，當無法證明完整性屬性時（有點諷刺，因為大多數有趣的數學系統已知是不可判定的），人們抵制使用啟發式方法。由於最佳優先搜尋啟發式或許多類型的選擇性生成器很少能證明其完整性，因此這個要求具有相當的抑制作用。當定理證明程式不斷被其搜尋樹的組合爆炸所癱瘓時，人們開始考慮選擇性啟發式方法，這些方法在許多情況下證明是通用問題解決程式中所使用的啟發式方法的類比。例如，支援集啟發式（set-of-support heuristic）是一種回溯的形式，已應用於歸結定理證明環境。

A Summary of the Experience

我們現在已經描述了我們的第二條定性結構法則的作用，該法則斷言物理符號系統通過啟發式搜尋解決問題。除此之外，我們還研究了啟發式搜尋的一些輔助特性，特別是它總是面臨的搜尋樹指數爆炸的威脅，以及它用來避免這種威脅的一些方法。關於啟發式搜尋作為問題解決機制的有效性，人們意見不一——意見取決於所考慮的任務領域以及採用的充分性標準。通過降低期望水平可以保證成功——或者通過設定高期望水平來導致失敗。證據可以總結如下。很少有程式能在「專家」專業水平上解決問題。Samuel 的跳棋程式和 Feigenbaum 與 Lederberg 的 DENDRAL 也許是最好的已知例外，但也可以指出許多針對諸如排程和整數規劃等運籌學問題領域的啟發式搜尋程式。在許多領域，程式表現出稱職業餘愛好者的水平：西洋棋、一些定理證明領域、許多類型的遊戲和謎題。對於具有複雜知覺「前端」的程式，人類水平尚未接近達到：視覺場景識別器、語音理解器、必須在真實空間和時間中操作的機器人。儘管如此，已經取得了令人印象深刻的進展，並且關於這些困難任務累積了大量的經驗。

我們對於目前呈現的特定性能模式沒有深入的理論解釋。然而，在經驗基礎上，我們可以得出兩個結論。首先，從關於人類在西洋棋等任務中的專家表現所學到的知識來看，任何能夠匹敵這種表現的系統，在其記憶中，很可能必須能夠訪問非常大量的語義信息儲存。其次，人類在具有大量感知組成部分的任務中的某些優勢，可以歸因於人類眼睛和耳朵特殊用途的內建並行處理結構。

無論如何，性能的品質必然取決於問題領域和用於解決問題的符號系統的特性。對於我們感興趣的大多數實際領域，領域結構證明不夠簡單，無法（迄今為止）產生關於複雜性的定理，也無法告訴我們，除了經驗上，真實世界問題相對於我們的符號系統解決它們的能力有多大。這種情況可能會改變，但在改變之前，我們必須依賴經驗探索，使用我們知道如何構建的最好的問題解決器，作為獲取關於問題難度的大小和特徵的知識的主要來源。即使在像線性規劃這樣高度結構化的領域，理論在強化支持最強大的解決算法的啟發式方面，也遠比在提供對複雜性的深入分析方面更有用。

我們對智能的分析，將其等同於提取和使用關於問題空間結構資訊的能力，以便問題解決方案能夠盡可能快速和直接地生成。那麼，提高符號系統問題解決能力的新方向，就可以等同於提取和使用資訊的新方法。至少可以識別出三種這樣的方法。

Nonlocal Use of Information

首先，一些研究者注意到，在樹搜尋過程中收集到的資訊通常只被局部 (locally) 使用，以幫助在產生資訊的特定節點做出決策。通過對一個棋局的子樹進行動態分析獲得的關於該棋局的資訊，通常只用於評估該棋局，而不評估可能包含許多相同特徵的其他棋局。因此，相同的事實必須在搜尋樹的不同節點重複發現。簡單地將資訊從其產生環境中取出並普遍使用並不能解決問題，因為該資訊可能只在有限的環境範圍內有效。近年來，已經進行了一些探索性努力，將資訊從其產生環境傳輸到其他適當的環境。雖然現在評估這個想法的力量，甚至確切如何實現它還為時過早，但它展現出相當大的前景。Berliner [1975] 一直在進行的一項重要研究路線，是使用因果分析來確定特定資訊有效的範圍。因此，如果西洋棋局面的弱點可以追溯到造成它的走法，那麼在從同一走法衍生的其他局面中，可以預期同樣的弱點。

HEARSAY 語音理解系統採取了另一種使資訊全局可用的方法。該系統通過在多個不同層次（語音、詞彙、句法和語義）進行並行搜尋來嘗試識別語音字串。當這些搜尋中的每一個提供並評估假設時，它將獲得的資訊提供給一個共享的「黑板」（blackboard），所有來源都可以讀取。這個共享資訊可以用於，例如，消除假設，甚至整類假設，否則其中一個過程必須搜尋。因此，提高我們非局部使用樹搜尋資訊的能力，有望提升問題解決系統的智能。

Semantic Recognition Systems

提高智能的第二種積極可能性是為符號系統提供關於其正在處理的任務領域的豐富語義資訊。例如，對西洋棋大師技能的經驗研究表明，大師技能的主要來源是儲存的資訊，這些資訊使他能夠識別西洋棋盤上的大量特定特徵和特徵模式，以及使用這種識別來建議與識別出的特徵相關的行動的資訊。當然，這個普遍的想法幾乎從一開始就被納入西洋棋程式中。新穎之處在於意識到要達到大師級別的遊戲可能需要儲存的模式和相關資訊的數量：大約 50,000 個。替換搜尋而採用識別的可能性之所以出現，是因為一個特定的，尤其是罕見的模式，如果與問題空間的結構緊密相連，可以包含大量資訊。當這種結構是「不規則」的，並且無法用簡單的數學描述時，那麼了解大量相關模式可能是智能行為的關鍵。這在任何特定任務領域是否如此，是一個更容易通過經驗調查而非理論來解決的問題。我們使用豐富語義資訊和模式識別能力來訪問這些資訊的符號系統的經驗仍然非常有限。上面的討論特指與識別系統相關的語義資訊。當然，還有一個龐大的人工智慧研究領域，關於語義資訊處理和語義記憶的組織，這超出了本文討論的主題範圍。

Selecting Appropriate Representations

第三條探究路線關注的是通過選擇一個適當的問題空間 (problem space) 來減少或避免搜尋的可能性。一個戲劇性地說明這種可能性的標準例子是殘缺棋盤問題 (mutilated checkerboard problem)。一個標準的 64 格棋盤可以完全用 32 個 1X2 的矩形棋子覆蓋，每個棋子恰好覆蓋兩個方格。現在，假設我們從棋盤的兩個對角線對角切掉方格，剩下總共 62 個方格。這個殘缺的棋盤能否完全用 31 個棋子覆蓋？用（字面意義上的）神級耐心，可以通過嘗試所有可能的排列來證明無法實現這樣的覆蓋。對於耐心較少但更聰明的人來說，替代方案是觀察到棋盤的兩個對角線對角方格顏色相同。因此，殘缺的棋盤比另一種顏色少兩個方格。但是每個棋子覆蓋一個顏色的一個方格和另一種顏色的一個方格，並且任何一套棋子都必須覆蓋相同數量的每種顏色的方格。因此，沒有解決方案。符號系統如何發現這個簡單的歸納論證，作為對不可能通過搜尋所有可能的覆蓋來解決問題的徒勞嘗試的替代方案？我們會給找到解決方案的系統很高的智能評分。

然而，或許在提出這個問題時，我們並未擺脫搜尋過程。我們只是將搜尋從可能的問題解決方案空間轉移到了可能的表示 (representations) 空間。無論如何，從一種表示轉移到另一種表示，以及發現和評估表示的整個過程，在問題解決研究領域中仍是很大程度上未被探索的領域。管理表示的定性結構法則仍有待發現。尋找這些法則幾乎肯定會在未來十年受到相當多的關注。

Conclusion

這就是我們關於符號系統和智能的論述。從柏拉圖的《美諾篇》到現在，這是一條漫長的道路，但或許令人鼓舞的是，這條道路上的大部分進展是在二十世紀之交後取得的，其中很大一部分是在本世紀中葉之後取得的。思想仍然是完全無形和難以言喻的，直到現代形式邏輯將其解釋為對形式符號的操作。在電腦教導我們符號如何被機器處理之前，它似乎仍然主要棲息在柏拉圖式理念的天堂中，或同樣模糊的人類靈魂空間中。我們今天紀念的 A.M. Turing 在這些從現代邏輯到電腦的發展中，在本世紀中葉的十字路口做出了他巨大的貢獻。

Physical Symbol Systems

對邏輯和電腦的研究向我們揭示，智能存在於物理符號系統中。這是電腦科學最基本的定性結構法則。

符號系統是模式和過程的集合，後者能夠產生、銷毀和修改前者。模式最重要的特性是它們可以指稱物件、過程或其他模式，並且當它們指稱過程時，它們可以被解釋。解釋意味著執行被指稱的過程。我們所熟知的兩個最重要的符號系統類別是人類和電腦。

正如前面所指出的，我們目前對符號系統的理解是通過一系列階段發展起來的。形式邏輯讓我們熟悉了符號，在句法上將其視為思維的原材料，以及根據精心定義的形式過程來操作它們的想法。Turing 機使符號的句法處理真正機器化，並肯定了嚴格定義的符號系統的潛在普遍性。電腦的儲存程式概念重申了符號的可解釋性，這在 Turing 機中已經隱含。列表處理將符號的指稱能力推到前沿，並以允許獨立於底層物理機器固定結構的方式定義了符號處理。到 1956 年，所有這些概念以及實現它們的硬體都已具備。對符號系統智能的研究，即人工智慧的主題，得以開始。

AI 的第二條定性結構法則指出，符號系統通過生成潛在解決方案並測試它們來解決問題，換句話說，通過搜尋 (searching)。解決方案通常是通過創建符號表達式並順序修改它們直到它們滿足解決方案的條件來尋找的。因此，符號系統通過搜尋來解決問題。由於它們資源有限，搜尋不能一次完成，而必須是順序的。它留下的結果是從起點到目標的一條單一路徑，或者如果需要修正和回溯，則是一整棵這樣的路徑樹。

當符號系統被純粹的混沌包圍時，它們不可能顯得智能。它們通過從問題領域中提取資訊並利用這些資訊來引導它們的搜尋，避免走錯路和繞道。該問題領域必須包含資訊，即一定程度的秩序和結構，才能使方法奏效。Meno 的悖論通過觀察資訊可能被記憶下來，但新的資訊也可以從符號指稱的領域中提取出來來解決。在這兩種情況下，資訊的最終來源都是任務領域。

The Empirical Base

人工智慧研究關注的是符號系統必須如何組織才能表現出智能。二十年的工作累積了相當多的知識，足以填滿幾本書（事實上已經填滿了），其中大部分以相當具體的經驗形式呈現，關於特定類別符號系統在特定任務領域的行為。然而，從這些經驗中，也出現了一些跨越任務領域和系統的概括，關於智能及其實現方法的普遍特徵。

我們今天早上試圖陳述其中一些概括。它們大多是定性的，而不是數學的。它們更多地具有地質學或進化生物學的風味，而非理論物理學的風味。它們足夠強大，足以使我們今天能夠設計和建造適用於相當廣泛任務領域的中等智能系統，並對人類智能在許多情況下如何運作獲得相當深入的理解。

What Next?

在我們今天的敘述中，我們提到了尚未解決的問題以及已解決的問題——兩者都有很多。我們認為在過去四分之一世紀中圍繞這個領域的那種探索的興奮感沒有減弱。在接下來的類似時期內，進展的速度將由兩個資源限制決定。一個是可用的計算能力。第二個，可能更重要的，是被吸引到這個領域作為他們可以應對的最具挑戰性的研究領域的有才華的年輕電腦科學家數量。

A.M. Turing 在他那篇著名的《計算機器與智能》的結尾寫道：

"We can only see a short distance ahead, but we can see plenty there that needs to be done."

Turing 在 1950 年看到許多需要做的事情已經完成，但議程仍然像以往一樣滿。也許我們對他上面的簡單陳述讀得過多，但我們喜歡認為 Turing 在其中認識到了所有電腦科學家本能知道的基本真理。對於所有物理符號系統來說，由於我們被限定在對問題環境進行串行搜尋，關鍵問題永遠是：下一步該做什麼？ (What to do next?)

References Berliner, H. [1975]. Chess as problem solving: the development of a tactics analyzer. Ph.D. diss., Computer Sci. Dep., Carnegie-Mellon U. (unpublished). McCarthy, J. [1960]. Recursive functions of symbolic expressions and their computation by machine. Comm. ACM 3, 4 (April 1960), 184-195. McCulloch, W.S. [1961]. What is a number, that a man may know it, and a man, that he may know a number. General Semantics Bulletin Nos. 26 and 27 (1961), 7-18. Nilsson, N.J. [1971]. Problem Solving Methods in Artificial Intelligence. McGraw-Hill, New York. Turing, A.M. [1950]. Computing machinery and intelligence. Mind 59 (Oct. 1950), 433-460.