開斷能力試驗

[拼音]：zidongji lilun

[英文]：automata theory

研究自動機的分析與綜合問題的數學理論，是控制論的一個重要分支。在自動機理論中，自動機都是指抽象自動機，即能變換和處理資訊的離散系統的動態數學模型。因為自動機理論早期的研究工作與數理邏輯有關，所以數學家把它看作是數學的一個分支。因為自動機可作為計算機和計算過程的數學模型，所以計算機專家把它看作是理論電腦科學的一個分支。自動機理論由抽象理論、結構理論和自組織理論三個部分組成。

發展簡史

1936年英國數學家A.M.圖靈提出一種抽象自動機，稱為圖靈機，用來定義可計算函式類，開創了自動機的抽象理論。1935～1938年蘇聯數學家В．И．舍斯塔科夫和美國應用數學家C.E.夏農分別獨立地應用布林代數來分析和綜合繼電器接點電路，建立開關網路理論，又稱邏輯自動機理論，開創了自動機的結構理論。1943年美國神經生理學家W.S.麥卡洛克和數學家W.皮茨在《關於神經活動中思維的邏輯演算》一文中，提出自動機的自組織理論。1945年美國數學家 J.von諾伊曼設計出儲存程式式通用電子數字計算機EDVAC,並研製成功，世稱諾伊曼機。諾伊曼機成為現代通用電子數字計算機的主要模式,1948年J.von諾伊曼對各種人造自動機和天然自動機進行比較，提出建立自動機的一般理論來概括它們的共同規律，並提出自繁殖和自修復等自組織理論。1948年美國數學家N.維納在《控制論》一書中對現代自動機作了詳細的分析，指出自動機的功能是變換和處理資訊，靈敏自動機的理論是一個統計的理論。這就為自動機理論奠定了基礎。1956年C.E.夏農和J.麥卡錫合編的著名論文集《自動機研究》一書出版。

50～60年代自動機理論得到迅速的發展。先後提出有限自動機(S.C.克林,1951；E.F.穆爾,1956)、無限自動機(M.明斯基,1967)、概率自動機(C.E.夏農,1956;T.L.布思,1965)、模糊自動機(E.S.桑托斯,1968；傅京孫，田中，1969)、細胞自動機（E.F.古德,1968）等多種抽象自動機；建立了形式語言與自動機的對應關係（N.喬姆斯基,1959,1964）；創立了自動機的綜合理論（B.M.格羅什科夫，1961）、半群理論（K.克勞恩和J.L.羅茲，1965）和可靠性理論（J.von諾伊曼,1952）。70年代後，由於大規模積體電路和平行計算機發展的需要，細胞自動機得到了迅速的發展（A.林登邁耶，1976）。由於模式識別、人工智慧和大系統理論發展的需要，模糊自動機越來越引起人們的注意。許多學者企圖建立自動機的統一理論，因此自動機的代數理論也有較大的進展，開始研究範疇上的自動機。

抽象理論

在自動機的抽象理論中不考慮自動機本身的結構及其輸入和輸出訊號的具體形式，把自動機作為一種數學系統，研究它的一般數學性質。抽象理論僅研究自動機在輸入訊號作用下發生的狀態變化及此時產生的輸出訊號。自動機的抽象理論從數學上看就是一種可能性預先受到限制的演算法理論，即機器演算法理論，它是現代程式設計理論的基礎。

1936年圖靈提出用圖靈機來定義可計算函式類開創了抽象理論的研究。60年代形成的自動機的半群理論,後來發展起來的自動機的代數理論，以及範疇上的自動機理論，是抽象理論的重要內容。50年代末提出的把自動機作為語言識別器，建立形式語言與自動機的對應關係，通過自動機得出相應文法的識別程式，從而實現面向文法的編譯，產生編譯程式的編譯程式。把自動機作為計算過程的模型，可以用來研究演算法、程式和計算複雜性理論。這些也都屬於抽象理論的範疇。抽象理論的主要發展方向是建立自動機的統一理論。

結構理論

自動機的結構理論是自動機抽象理論的進一步發展。結構理論研究的重點是自動機的綜合、由元自動機構造自動機的方法以及對輸入和輸出通道傳遞的元訊號進行編碼的方法。

由於設計新型電子計算機的迫切需要，數字自動機的結構理論得到迅速的發展。通用電子數字計算機可以看作更廣泛的數字自動機中的一類。數字自動機的結構理論涉及布林代數、命題演算、謂詞演算和資訊理論的有關問題。數字自動機的結構理論與數字自動機的綜合問題直接有關，包括抽象綜合、組合綜合、結構綜合、部件綜合和可靠性綜合。1938年C.E.夏農就用布林代數解決繼電網路的組合綜合，後來用於電子計算機邏輯網路的綜合。40年代蘇聯學者В．И．舍斯塔科夫解決了數字自動機的結構綜合和部件綜合問題。到50年代S.C.克林和E.F.穆爾解決了抽象綜合問題，後來D.D.奧芬卡姆夫和 F.霍恩又進一步發展了抽象綜合。J.von諾伊曼解決了可靠性綜合問題。到60年代蘇聯學者B.M.格羅什科夫把抽象綜合和結構綜合結合起來，使結構理論的表達形式適合於解決任何數字自動機的綜合問題，建立了數字自動機綜合的一般數學理論。

由元自動機構造自動機的方法主要有兩類：

（1）級聯方法，即用串聯、並聯和混聯方法把若干臺元自動機聯成一臺自動機，它具有樹狀、星狀、網狀等多種拓撲結構。級聯方法的逆問題是級聯分解問題，自動機的級聯分解與大系統的分解等價。有限自動機的級聯分解問題與有限自動機的半群結構有關，可以根據半群的結構理論和群的整除性理論解決。已經證明有限自動機級聯分解定理。

（2）鄰域連線方法，現已發展成為細胞自動機理論，在一致結構的大規模積體電路和平行計算機中得到廣泛應用。

自組織理論

自動機的自組織理論是自動機的抽象理論和結構理論發展的結果。自組織理論涉及神經網路、人工智慧、模式識別等許多方面，有時還要應用協同學、耗散結構理論和超迴圈理論等方面的成就。1943年W.S.麥卡洛克和W.皮茨關於神經網路的先驅性工作，對發展神經網路理論有深遠的影響，促進了自組織理論的早期研究工作。1969年傅京孫、田中和E.S.桑托斯等人把模糊神經原的概念應用到自動機理論中來，使神經網路理論的研究工作得到新的發展，並使自動機理論開始用來研究複雜大系統的行為。

在自組織理論的研究中 J.von諾伊曼提出了一系列創造性的新概念。1948年他提出自繁殖機的概念。他所提出的關聯的有限自動機的迭代陣列可用來研究字元的模式識別。1952年他提出著名的冗餘技術，即用大量並行連線的可靠性低的自動機能構造出可靠性很高的自動機，後來發展成為容錯自動機理論。在此基礎上他又提出諾伊曼細胞空間的新概念，後來發展成為細胞自動機理論。

1958年F.羅森布拉特曾提出認知機的網路結構，模擬人的感受、認知和解題能力。50年代末到60年代初又在認知機的基礎上提出自適應機和自學習機。1963年蘇聯學者В．И．瓦爾沙烏斯基等人又提出變結構自動機。1969年M.明斯基等人證明這類自組織機器的模式識別能力有限。到70年代便轉向機器視覺的研究。

1968年E.F.古德提出的細胞自動機(即多元自動機)使自組織理論發展到一個新階段。細胞自動機是在諾伊曼細胞空間的概念上發展起來的，它由大量相同的細胞按鄰域連線方法關聯組成，可以形成各種拓撲配置格局。在細胞自動機中一個細胞就是一臺有限自動機，每一個細胞可以從相鄰的細胞或外界環境取得輸入資訊，每一個細胞的輸出資訊可以傳遞給相鄰的細胞或外界環境。因此，細胞自動機可以用來研究平行計算機的體系結構和大規模積體電路設計技術。有一種細胞自動機是二維無限棋盤格式的,每一方格代表一個細胞。它已被用來證明非平凡的自繁殖機的存在。如果每個細胞有三個狀態和四個相鄰細胞,並呈現園林格局（即除了時刻0以外在細胞空間中每一時刻細胞狀態的模式均不會增加），他就可以用來計算任何可計算函式。另一種細胞自動機是採用棋盤形空間，一個外部輸入可以傳遞到每一個細胞，一個細胞失去一個鄰近細胞可用一個專用的邊界訊號代替。這種細胞自動機專門用作模式識別器。有一種圖形細胞自動機只要求相鄰細胞的數目是固定的，而不要求它們與一個細胞有固定的幾何關係。這種細胞自動機比均勻關聯的細胞自動機具有更強的功能。1976年荷蘭生物學家林登邁耶提出動態細胞自動機，稱為林登邁耶系統,即L系統。動態細胞自動機允許把細胞劃分成子細胞而不管該細胞在細胞初始陣列中的位置。這種動態關聯格式受到理論生物學家的注意，可用作生命體的生長和發育模型。有一種米利型細胞允許任何兩個細胞之間進行瞬時通訊。上述各種細胞自動機如採用米利型細胞還會有其他新的功能。

參考書目

C.E.申南、J.麥克卡賽編，陳中基編譯：《自動機研究》，科學出版社，北京，1963。(C.E. Shannon and J.McCarthy(eds)， AutomataStudies，Princeton University Press,Princeton,N.J.,1956.)

M.A.Arbib，Theories of Abstract Automata，Printice-Hall,Englewood Cliffs,1969.